โปรแกรมนับวิธีการรวมเหรียญมูลค่า 1,2,5,10 บาท ให้ได้จำนวนเงิน n ใน Python

มีเหรียญมูลค่า 1, 2, 5, 10 บาท จำนวนจำกัดตามอาร์เรย์ count (count[0] สำหรับ 1 บาท, count[1] สำหรับ 2 บาท, ... ) ต้องการหาจำนวนวิธีรวมเหรียญให้ได้เงิน n บาท

ตัวอย่าง: n=25, count=[7,3,2,2] ผลลัพธ์คือ 9

ขั้นตอนการแก้ปัญหา

ใช้ Dynamic Programming แบบ Knapsack พร้อมจำกัดจำนวนเหรียญ:

1. กำหนด denom = [1,2,5,10]
2. สร้างอาร์เรย์ A ขนาด n+1 เติม 0, B คัดลอกจาก A
3. เติมค่าเริ่มต้นสำหรับเหรียญ 1 บาท: A[i] = 1 สำหรับ i จาก 0 ถึง min(count[0], n)
4. สำหรับเหรียญแต่ละมูลค่า (i=1..3) และจำนวนเหรียญที่ใช้ (j=0..count[i]) อัปเดต B จาก A
5. คืนค่า A[n]

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

denom = [1, 2, 5, 10]

def solve(n, count):
    A = [0] * (n + 1)
    B = list(A)
    for i in range(min(count[0], n) + 1):
        A[i] = 1
    for i in range(1, 4):
        for j in range(count[i] + 1):
            for k in range(n + 1 - j * denom[i]):
                B[k + j * denom[i]] += A[k]
        for j in range(n + 1):
            A[j] = B[j]
            B[j] = 0
    return A[n]

# ทดสอบ
n = 25
count = [7, 3, 2, 2]
print(solve(n, count))  # ผลลัพธ์: 9

อินพุตตัวอย่าง

25, [7,3,2,2]

เอาต์พุตตัวอย่าง

9