Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Python

โปรแกรมค้นหาจำนวนเหรียญที่จำเป็นในการเปลี่ยนแปลงด้วยชุดเหรียญที่กำหนดใน Python


สมมติว่าเรามีเหรียญหลายนิกายและจำนวนเงินรวม เราต้องกำหนดหนึ่งฟังก์ชันเพื่อคำนวณจำนวนเหรียญน้อยที่สุดที่เราต้องใช้ในการคำนวณจำนวนนั้น เมื่อเงินจำนวนนั้นไม่สามารถใช้ร่วมกับเหรียญได้ ให้คืน -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
  • ผลตอบแทน dp[จำนวน]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

ผลลัพธ์

14