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

Giả sử chúng ta đã đưa ra một đồng tiền có mệnh giá (1, 2, 5 và 10). Chúng ta phải tìm xem có bao nhiêu cách mà chúng ta có thể sắp xếp n bằng cách sử dụng các ưu thế này. Chúng ta có một mảng được gọi là count với 4 phần tử, trong đó count [0] cho biết số lượng xu của 1, count [1] cho biết số lượng xu của 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 nên có 18 kết hợp có thể có, một số trong số chúng là

• 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à như vậy ...

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

• denom:=[1,2,5,10]
• A:=một mảng có kích thước (n + 1) và điền bằng 0
• B:=một danh sách mới từ A
• đối với tôi trong phạm vi từ 0 đến (tối thiểu là số [0] và n), hãy thực hiện
  • A [i]:=1
• đối với tôi trong phạm vi từ 1 đến 3, hãy thực hiện
  • cho j trong phạm vi 0 để đếm [i], thực hiện
    • đối với k trong phạm vi từ 0 đến n + 1 - j * denom [i], thực hiện
      • B [k + j * denom [i]]:=B [k + j * denom [i]] + A [k]
  • đối với j trong phạm vi từ 0 đến n, thực hiện
    • A [j]:=B [j]
    • B [j]:=0
• trả về A [n]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để 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