समझौता परिवर्तन बनाने एल्गोरिथ्म

Question

मैं Change-making problem के लिए एक अच्छा समाधान के लिए देख रहा था और मैं इस कोड (अजगर) में पाया गया:

target = 200 
coins = [1,2,5,10,20,50,100,200] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin,target+1): 
     ways[i]+=ways[i-coin] 
print(ways[target]) 

मैं कोई समस्या नहीं समझ कोड सचमुच करता है, लेकिन मैं नहीं कर सकता समझें कि यह क्यों काम करता है। कोई भी मदद कर सकता है?

Answer 1

सभी संभव सेट है कि तत्वों 'a' या 'बी' या 'सी' (हमारे सिक्के) 'एक्स' अप करने के लिए उस राशि आप कर सकते हैं के बराबर हैं पाने के लिए:

• इस तरह के सभी सेट ले लो कि Xa तक योग करें और प्रत्येक को एक अतिरिक्त 'ए' जोड़ें।
• एक्स-बी तक के सभी ऐसे सेट ले लो और प्रत्येक को अतिरिक्त 'बी' जोड़ें।
• ऐसे सभी सेट लें जो एक्स-सी तक जोड़ते हैं और प्रत्येक को अतिरिक्त 'सी' जोड़ते हैं।

तो एक्स प्राप्त करने के तरीकों की संख्या एक्स-ए और एक्स-बी और एक्स-सी प्राप्त करने के तरीकों की संख्या है।

ways[i]+=ways[i-coin] 

बाकी सरल पुनरावृत्ति है।

अतिरिक्त संकेत: शुरू में कि वास्तव में आप एक ही रास्ता (खाली सेट)

ways = [1]+[0]*target 

Answer 2

यह dynamic programming के एक शास्त्रीय उदाहरण है में योग शून्य के साथ सेट कर सकते हैं। यह 3 + 2 = 5 दो बार (अन्य संभावित समाधान के कारण: 2 + 3) की गिनती के गड़बड़ी से बचने के लिए कैशिंग का उपयोग करता है। एक रिकर्सिव एल्गोरिदम उस गड़बड़ी में पड़ता है। आइए एक साधारण उदाहरण पर ध्यान दें, जहां target = 5 और coins = [1,2,3]।कोड का टुकड़ा आप गिनती पोस्ट:

1. 3 + 2
2. 3 + 1 + 1
3. 2 + 2 + 1
4. 1 + 2 + 1 + 1
5. 1 + 1 + 1 + 1 + 1

जबकि पुनरावर्ती संस्करण ही गिना जाता:

1. 3 + 2
2. 2 + 3
3. 3 + 1 + 1
4. 1 + 3 + 1
5. 1 + 1 + 3
6. 2 + 1 + 2
7. 1 + 1 + 2
8. 2 + 2 + 1
9. 2 + 1 + 1 + 1
10. 1 + 2 + 1 + 1
11. 1 + 1 + 2 + 1
12. 1 + 1 + 1 + 2
13. 1 + 1 + 1 + 1 + 1

रिकर्सिव कोड:

coinsOptions = [1, 2, 3] 
def numberOfWays(target): 
    if (target < 0): 
     return 0 
    elif(target == 0): 
     return 1 
    else: 
     return sum([numberOfWays(target - coin) for coin in coinsOptions]) 
print numberOfWays(5) 

गतिशील प्रोग्रामिंग:

target = 5 
coins = [1,2,3] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin, target+1): 
     ways[i]+=ways[i-coin] 
print ways[target] 

Answer 3

कोड के पीछे मुख्य विचार यह है निम्नलिखित: " प्रत्येक चरण पर waysi को दिए गए पैसे की राशि [1,...coin] "बदलने के तरीके हैं।

तो पहले पुनरावृत्ति पर आपके पास 1 के मूल्य के साथ केवल एक सिक्का है। मेरा मानना ​​है कि यह देखना स्पष्ट है कि किसी भी लक्ष्य के लिए केवल इन सिक्कों के साथ बदलाव करने का एक ही तरीका है। इस चरण पर ways सरणी [1,...1] की तरह दिखेगी (0 से target तक सभी लक्ष्यों के लिए केवल एक ही रास्ता)।

अगले चरण में हम सिक्कों के पिछले सेट में 2 के मूल्य के साथ एक सिक्का जोड़ते हैं। अब हम गणना कर सकते हैं कि प्रत्येक लक्ष्य के लिए 0 से target तक कितने परिवर्तन संयोजन हैं। जाहिर है, संयोजन की संख्या केवल लक्ष्यों के लिए बढ़ेगी> = 2 (या सामान्य मामले में नया सिक्का जोड़ा गया)। तो एक लक्ष्य के लिए 2 बराबर संयोजनों की संख्या ways[2](old) + ways[0](new) होगी। आम तौर पर, हर बार जब i एक नया सिक्का पेश किया जाता है, तो हमें संयोजनों की पिछली संख्या में 1 जोड़ने की आवश्यकता होती है, जहां एक नया संयोजन केवल एक सिक्का से ही होगा।

target>2 के लिए, जवाब है "target राशि के सभी संयोजनों coin से भी कम समय सभी सिक्के होने" और "coin राशि के सभी संयोजनों सभी सिक्के coin खुद की तुलना में कम होने" की राशि शामिल होंगे।

यहां मैंने दो बुनियादी चरणों का वर्णन किया है, लेकिन मुझे उम्मीद है कि इसे सामान्य बनाना आसान है।

मुझे आप target = 4 और coins=[1,2] के लिए एक कम्प्यूटेशनल पेड़ दिखा:

तरीके [4] को देखते हुए सिक्के = [1,2] =

तरीके [4] को देखते हुए सिक्के = [1] + तरीके [2] को देखते हुए सिक्के = [1,2] =

1 + तरीके [2] को देखते हुए सिक्के = [1] + तरीके [0] को देखते हुए सिक्के = [1,2] =

1 + 1 + 1 = 3

तो परिवर्तन देने के तीन तरीके हैं: [1,1,1,1], [1,1,2], [2,2]।

ऊपर दिया गया कोड रिकर्सिव समाधान के बराबर है। यदि आप the recursive solution समझते हैं, तो मुझे लगता है कि आप ऊपर दिए गए समाधान को समझते हैं।

Answer 4

आपके द्वारा पोस्ट किया गया समाधान इस कोड का सारांश सारांशित है।

/// <summary> 
    /// We are going to fill the biggest coins one by one. 
    /// </summary> 
    /// <param name="n"> the amount of money </param> 
    public static void MakeChange (int n) 
    { 
     int n1, n2, n3; // residual of amount after each coin 
     int quarter, dime, nickel; // These are number of 25c, 10c, 5c, 1c 
     for (quarter = n/25; quarter >= 0; quarter--) 
     { 
      n1 = n - 25 * quarter; 
      for (dime = n1/10; dime >= 0; dime--) 
      { 
       n2 = n1 - 10 * dime; 
       for (nickel = n2/5; nickel >= 0 && (n2 - 5*nickel) >= 0; nickel--) 
       { 
        n3 = n2 - 5 * nickel; 
        Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, n3); // n3 becomes the number of cent. 
       } 
      } 
     } 
    }