โปรแกรมหาจำนวนเหรียญน้อยที่สุดสำหรับการแลกเงิน (เหรียญคงที่ 1,5,10,25) ใน Python

สมมติว่าเรามีเหรียญมูลค่าคงที่ [1, 5, 10, 25] และจำนวนเงิน amount หาจำนวนเหรียญน้อยที่สุดที่รวมเป็น amount

ตัวอย่าง: amount = 64 ผลลัพธ์ 7 (25+25+10+1+1+1+1=64)

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

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, amount):
        coins = [1, 5, 10, 25]
        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(64))  # Output: 7

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

Input: 64

Output: 7