โปรแกรมหาจำนวนเหรียญน้อยที่สุดสำหรับการแลกเงินด้วยชุดเหรียญกำหนดใน Python

สมมติว่าเรามีเหรียญมูลค่าต่างๆ และจำนวนเงิน amount หาจำนวนเหรียญน้อยที่สุดที่รวมเป็น amount ถ้าไม่สามารถทำได้ คืนค่า -1

ตัวอย่าง: coins = [1,2,5], amount = 64 ผลลัพธ์ 14 (12×5 + 2 + 2 = 64)

ขั้นตอนการแก้ปัญหา (Dynamic Programming - Coin Change)

1. ถ้า amount == 0 คืนค่า 0
2. ถ้า min(coins) > amount คืนค่า -1
3. สร้าง dp ขนาด amount+1 เติม -1
4. สำหรับแต่ละ i ใน coins:
   • ถ้า i > len(dp)-1: ข้าม
   • dp[i] = 1
   • สำหรับ j จาก i+1 ถึง amount:
     • ถ้า dp[j-i] == -1: ข้าม
     • ถ้า dp[j] == -1: dp[j] = dp[j-i] + 1
     • อื่นๆ: dp[j] = min(dp[j], dp[j-i] + 1)
5. คืนค่า dp[amount]

ตัวอย่างโค้ด Python

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))  # Output: 14

อินพุต / เอาต์พุต

Input: [1,2,5], 64

Output: 14