दिए गए सेट

Question

से दिए गए नंबर (दोहराए गए दोहराव के साथ) के सभी तरीकों का पता लगाएं एन तत्वों (जैसे [1,2]) एन तत्वों और एक संख्या 'के' (उदाहरण के लिए 6) को देखते हुए, सभी उत्पादन के तरीके खोजने के लिए योग = k

दिए गए उदाहरण उत्तर के लिए किया जाएगा 4 क्योंकि

1 1 1 1 1 1 
1 1 1 1 2 
1 1 2 2 
2 2 2 

एल्गोरिथ्म मैं है जानवर बल द्वारा, हम सब संभव परिदृश्यों अनुकरण के बारे में सोच सकता है, और रोक जब दिए गए राज्य से हम परिणाम नहीं पहुँच सकते हैं ।

arr[] = [1,2] 
    k = 6 
    globalCount =0; 
    function findSum(arr,k) 
    { 
     if(k ==0) 
     globalCount++ 
     return 
     else if(k<0) 
     return 

     for each i in arr{ 
     arr.erase(i) 
     tmp = k 
     findSum(arr,tmp) 
     while(k>=0){ 
      findSum(arr,tmp -= i) 
     } 
    } 

मुझे यकीन नहीं है कि मेरा समाधान वहां सबसे कुशल है या नहीं। कृपया बेहतर समाधान के लिए पॉइंटर्स टिप्पणी/सही या दिखाएं।

संपादित करें: अगर कोई मुझे मेरे कोड और उनके सोलन कोड की रनटाइम जटिलता दे सकता है तो वास्तव में सराहना करेगा। :) खान कोड जटिलता मुझे लगता है कि w = k/औसत बिग-O (n^डब्ल्यू) है (आगमन [0] .. आगमन [एन 1])

Answer 1

यदि आप फैंसी लिनक्स चाल का बहाना करने के इच्छुक हैं, तो आपको यह सी # समाधान उपयोगी लगेगा। सौभाग्य से linq अंग्रेजी की तरह पढ़ता है। विचार k 0 से शुरू होता है और वृद्धि तब तक बढ़ता है जब तक कि यह सही मूल्य तक नहीं पहुंच जाता। k का प्रत्येक मान पिछले समाधानों पर बनाता है। हालांकि आपको यह देखने के लिए एक चीज है कि नए "तरीके" जिन्हें आप ढूंढ रहे हैं वे दूसरों के पुन: क्रमिक नहीं हैं। मैंने हल किया कि अगर उन्हें क्रमबद्ध किया जाता है तो उन्हें केवल वैध मानते हुए। (जो था केवल एक ही तुलना)

void Main() { 
    foreach (int[] way in GetSumWays(new[] {1, 2}, 6)) { 
     Console.WriteLine (string.Join(" ", way)); 
    } 
} 

int[][] GetSumWays(int[] array, int k) { 
    int[][][] ways = new int[k + 1][][]; 
    ways[0] = new[] { new int[0] }; 

    for (int i = 1; i <= k; i++) { 
     ways[i] = (
      from val in array 
      where i - val >= 0 
      from subway in ways[i - val] 
      where subway.Length == 0 || subway[0] >= val 
      select Enumerable.Repeat(val, 1) 
       .Concat(subway) 
       .ToArray() 
     ).ToArray(); 
    } 

    return ways[k]; 
} 

आउटपुट:

1 1 1 1 1 1 
1 1 1 1 2 
1 1 2 2 
2 2 2 

यह एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करता है और तेजी से एक अनुभवहीन पुनरावर्ती दृष्टिकोण से किया जाना चाहिए। मुझे लगता है। मुझे पता है कि कुछ मिलीसेकंड में डॉलर तोड़ने के तरीकों की संख्या को गिनने के लिए यह तेज़ है। (242)

Answer 2

यह विभाजन समस्या का एक दिलचस्प सबसेट है। वास्तव में इसके लिए एक बंद-फॉर्म समाधान है (here और here देखें) यदि आप सभी पूर्णांकों को अनुमति देते हैं।

"प्रतिबंधित विभाजन फ़ंक्शन" के लिए कुछ googling करना मुझे कुछ लीड देता है। This paper इस समस्या के कुछ समाधानों की एक सुंदर गणितीय कठोर चर्चा देता है, जैसा this one करता है।

दुर्भाग्य से मैं इन्हें कोड करने के लिए बहुत आलसी हूं। वे बहुत गहन समाधान हैं।