Chương trình tìm số cách chúng ta có thể nhận được n R.s bằng cách sử dụng mệnh giá Ấn Độ trong Python

Giả sử chúng ta có giới hạn tiền xu có mệnh giá (₹ 1, ₹ 2, ₹ 5 và ₹ 10). Chúng ta phải tìm xem có bao nhiêu cách có thể tính tổng chúng với tổng là ₹ n? Chúng tôi có số lượng mảng có kích thước 4, trong đó số lượng [0] cho biết số tiền ₹ 1, số lượng [1] chỉ ra số tiền có giá trị ₹ 2, v.v.

Vì vậy, nếu đầu vào là n =25 count =[7,3,2,2], thì đầu ra sẽ là 9.

Để 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 để hiểu rõ hơn -

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(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 = 25
count = [7,3,2,2]
print(solve(n, count))

Đầu vào

25, [7,3,2,2]

Đầu ra

9