Chương trình Python tìm số cách đổi tiền n rupee với các đồng xu cho trước

Giả sử chúng ta có các đồng xu mệnh giá (1, 2, 5 và 10). Chúng ta phải tìm có bao nhiêu cách để tạo thành n bằng các mệnh giá này. Chúng ta có một mảng gọi là count với 4 phần tử, trong đó count[0] chỉ số lượng đồng xu mệnh giá 1, count[1] cho mệnh giá 2, v.v.

Vì vậy, nếu đầu vào là n = 27 count = [8,4,3,2], thì đầu ra sẽ là 18, có 18 tổ hợp khả thi, một số trong đó:

• 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 + 4*2 + 4*1 = 27

và cứ thế...

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:

• denom := [1,2,5,10]
• A := mảng kích thước (n + 1) điền 0
• B := danh sách mới từ A
• với i từ 0 đến min(count[0], n), thực hiện A[i] := 1
• với i từ 1 đến 3, thực hiện
  • với j từ 0 đến count[i], thực hiện
    • với k từ 0 đến n + 1 - j * denom[i], thực hiện
      • B[k + j * denom[i]] := B[k + j * denom[i]] + A[k]
  • với j từ 0 đến n, thực hiện
    • A[j] := B[j]
    • B[j] := 0
• trả về A[n]

Ví dụ

Hãy xem triển khai sau để hiểu rõ hơn:

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))

Đầu vào

27, [8,4,3,2]

Đầu ra

18