पायथन में सिक्कों के दिए गए सेट के साथ परिवर्तन करने के लिए आवश्यक सिक्कों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास विभिन्न मूल्यवर्ग के सिक्के हैं और कुल राशि की राशि है। हमें उस राशि को बनाने के लिए आवश्यक सिक्कों की सबसे कम संख्या की गणना करने के लिए एक फ़ंक्शन को परिभाषित करना होगा। जब सिक्कों के किसी भी संयोजन से उस राशि को समायोजित नहीं किया जा सकता है, तो वापसी -1। तो अगर इनपुट [1,2,5] है, और राशि 64 है, तो आउटपुट 14 है। यह 12*5 + 2 + 2 =64 का उपयोग करके बनाया गया है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

यदि राशि =0 है, तो 0 वापस करें
यदि न्यूनतम सिक्के सरणी> राशि है, तो -1 लौटाएं
dp नामक एक सरणी परिभाषित करें, आकार राशि + 1 की, और इसे -1 से भरें
मैं श्रेणी के सिक्कों की श्रेणी में
- यदि i> dp-1 की लंबाई है, तो अगले भाग को छोड़ दें, अगले पुनरावृत्ति के लिए जाएं
- dp[i] :=1
- j श्रेणी में i + 1 से राशि के लिए
  - अगर dp[j – 1] =-1, तो अगले भाग को छोड़ दें, अगले पुनरावृत्ति के लिए जाएं
  - अन्यथा यदि dp[j] =-1, तो dp[j] :=dp[j - i] + 1
  - अन्यथा dp[j] :=न्यूनतम dp[j] और dp[j – i] + 1
रिटर्न डीपी[राशि]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution(object):
   def coinChange(self, coins, amount):
      if amount == 0 :
         return 0
      if min(coins) > amount:
         return -1
      dp = [-1 for i in range(0, amount + 1)]
      for i in coins:
         if i > len(dp) - 1:
            continue
         dp[i] = 1
         for j in range(i + 1, amount + 1):
            if dp[j - i] == -1:
               continue
            elif dp[j] == -1:
               dp[j] = dp[j - i] + 1
            else:
               dp[j] = min(dp[j], dp[j - i] + 1)
      return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5],64))

इनपुट

[1,2,5], 64