गतिशील प्रोग्रामिंग इष्टतम सिक्का बदलें

Question

मैं कुछ गतिशील प्रोग्रामिंग समस्याओं की समीक्षा कर रहा हूं, और परिवर्तन करने के लिए छोटी संख्या में सिक्के खोजने के संबंध में मुझे कुछ कोड के आसपास अपने सिर को लपेटने में कठिनाई हुई है।

कहें कि हमारे पास 25, 10, और 1 के सिक्के हैं, और हम 30 के लिए परिवर्तन कर रहे हैं। लालची 25 और 5 (1) वापस आ जाएगी जबकि इष्टतम समाधान 3 (10) वापस आ जाएगा।

def dpMakeChange(coinValueList,change,minCoins): 
    for cents in range(change+1): 
     coinCount = cents 
     for j in [c for c in coinValueList if c <= cents]: 
      if minCoins[cents-j] + 1 < coinCount: 
       coinCount = minCoins[cents-j]+1 
     minCoins[cents] = coinCount 
    return minCoins[change] 

किसी को भी मदद कर सकता है, तो मुझे इस कोड के आसपास मेरे सिर लपेटो (लाइन 4 वह जगह है जहाँ मैं उलझन में पाने के लिए शुरू), कि बहुत अच्छा होगा: यहाँ इस समस्या पर किताब से कोड है। धन्यवाद!

Answer 1

ऐसा लगता है कि कोड लक्ष्य केंद्र मूल्य तक प्रत्येक प्रतिशत मूल्य के लिए समस्या को हल कर रहा है। लक्ष्य मूल्य v और सिक्कों C का एक सेट को देखते हुए, आप जानते हैं कि इष्टतम सिक्का चयन S रूप union(S', c), जहां cC और S' से कुछ का सिक्का है v - value(c) के लिए इष्टतम समाधान है (मेरे अंकन बहाना) का हो गया है। तो समस्या optimal substructure है। गतिशील प्रोग्रामिंग दृष्टिकोण हर संभव उपप्रोबल को हल करना है। यह cents * size(C) चरणों को लेता है, जो कि कुछ और तेजी से उड़ाता है यदि आप सीधे समाधान को बलपूर्वक बल देने की कोशिश करते हैं।

def dpMakeChange(coinValueList,change,minCoins): 
    # Solve the problem for each number of cents less than the target 
    for cents in range(change+1): 

     # At worst, it takes all pennies, so make that the base solution 
     coinCount = cents 

     # Try all coin values less than the current number of cents 
     for j in [c for c in coinValueList if c <= cents]: 

      # See if a solution to current number of cents minus the value 
      # of the current coin, with one more coin added is the best 
      # solution so far 
      if minCoins[cents-j] + 1 < coinCount: 
       coinCount = minCoins[cents-j]+1 

     # Memoize the solution for the current number of cents 
     minCoins[cents] = coinCount 

    # By the time we're here, we've built the solution to the overall problem, 
    # so return it 
    return minCoins[change] 

Answer 2

मुझे लगता है कि चौथी लाइन भ्रामक है क्योंकि, जबकि अजगर एक सूची समझ (transform(x) for x in iterable if condition(x)) में/फिल्टर का चयन कर सकते हैं, यह अपने मानक for x in iterable: अभिव्यक्ति में एक ही नहीं कर सकते।

तो एक (चीसी आईएमओ) जिस तरह से लोग चारों ओर घूमते हैं, दोनों को एक साथ जोड़ना है। वे एक सूची समझ बनाते हैं जो वास्तव में कोई ट्रान्सफॉर्मेशन नहीं करता है (इस प्रकार c for c in coinValueList) बस वे if c <= cents खंड जोड़ सकते हैं। और फिर इसे मानक for x in iterable: अभिव्यक्ति के लिए पुनरावर्तनीय के रूप में उपयोग करें। मुझे संदेह है कि वह जगह है जहां से आपका कुछ भ्रम आ रहा है।

एक वैकल्पिक तरीका है कि लाइन हो सकता है लिखा है करने के लिए:

... 
for eachCoinValue in filter(lambda x: x <= cents, coinValueList): 
... 

या और भी अधिक स्पष्ट रूप से, एक "इरादा खुलासा चर" के साथ होगा:

... 
smallEnoughCoins = filter(lambda each: each <= cents) 
for each in smallEnoughCoins: 
    ... 

Answer 3

यहाँ के लिए एक रास्ता है सिक्का बदलने वाली समस्या के बारे में सोचें जो उपयोगी हो सकता है, यदि आप ग्राफ सिद्धांत के साथ सहज हैं।

मान लें कि आप एक ग्राफ निम्नलिखित तरीके से परिभाषित किया गया है:

• पैसे के हर इकाई के लिए एक नोड 0 से (जैसे, पैसे) मूल्य आप (उदाहरण के लिए, 39 सेंट में रुचि रखते हैं करने के लिए नहीं है , या जो भी हो।)
• किसी भी दो नोड्स के बीच एक चाप है जो आपको उपयोग किए जाने वाले सिक्का के मूल्य से अलग होता है (उदाहरण के लिए, यदि आपको निकल का उपयोग करने की अनुमति है तो 34 सेंट और 2 9 सेंट के बीच नोड।)

अब आप सिक्का बदलने की समस्या को सबसे कम पी के रूप में सोच सकते हैं आपकी रुचि के मूल्य से शून्य तक की समस्या, क्योंकि सिक्कों की संख्या आपके पथ में आर्क की संख्या के बराबर होगी।

एल्गोरिदम ग्राफ़ सिद्धांत शब्दावली का उपयोग नहीं करता है, लेकिन यह मूल रूप से वही काम कर रहा है: बाहरी पाश सभी "सेंट" (या नोड्स, ग्राफ़ सिद्धांत ढांचे में) और आंतरिक लूप पर है वर्तमान चाप से अगले चाप तक सभी arcs (coinValueList में मूल्य) से लेकर। सभी एक साथ, वे शून्य से आपके ब्याज के मूल्य तक सबसे कम पथ की तलाश में हैं। (शून्य से नीचे, शून्य तक शून्य, कोई फर्क नहीं पड़ता। परंपरागत रूप से हम नीचे शून्य की खोज करते हैं।)

मुझे केवल गतिशील प्रोग्रामिंग को समझना शुरू हो गया जब मुझे एहसास हुआ कि कई समस्याओं को ग्राफ समस्याओं के रूप में डाला जा सकता है। (सावधान रहें, हालांकि - उनमें से सभी नहीं कर सकते हैं। कुछ हाइपरग्राफ हैं, और कुछ शायद यह भी नहीं हैं। लेकिन इससे मुझे बहुत मदद मिली।)