โปรแกรมหาจำนวนวิธีแลกเงิน n บาทด้วยเหรียญที่กำหนดใน Python

การหาจำนวนวิธีแลกเงินด้วยเหรียญ 1, 2, 5, 10 บาท

กำหนดจำนวนเงิน n และจำนวนเหรียญแต่ละชนิด (count[0]=1บาท, count[1]=2บาท, count[2]=5บาท, count[3]=10บาท) หาจำนวนวิธีแลกเงิน

อัลกอริทึม (Dynamic Programming)

1. denom = [1,2,5,10]
2. A[i] = จำนวนวิธีทำเงิน i บาท (เริ่ม A[0]=1)
3. สำหรับเหรียญแต่ละชนิด ใช้ bounded knapsack (จำกัดจำนวนเหรียญ)
4. ใช้ array B ช่วยคำนวณ

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

denom = [1, 2, 5, 10]

def solve(n, count):
    A = [0 for _ in range(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(0, count[i] + 1):
            for k in range(n + 1 - j * denom[i]):
                B[k + j * denom[i]] += A[k]
        for j in range(0, n + 1):
            A[j] = B[j]
            B[j] = 0
    return A[n]

n = 27
count = [8, 4, 3, 2]
print(solve(n, count))

ผลลัพธ์

18

ตัวอย่างวิธีแลก 27 บาท

• 10×2 + 5×1 + 2×1 = 27
• 10×2 + 2×3 + 1×1 = 27
• 10×1 + 5×3 + 2×1 = 27
• 10×1 + 5×1 + 2×4 + 1×4 = 27