주어진 동전으로 n 루피를 얻는 방법을 찾는 Python 프로그램

<시간/>

우리가 교단의 동전(1, 2, 5, 10)을 주었다고 가정합니다. 우리는 이러한 지배를 사용하여 n을 배열할 수 있는 방법을 찾아야 합니다. count[0]은 1의 동전 수를 나타내고 count[1]은 2의 동전 수를 나타내는 식으로 4개의 요소가 있는 count라는 배열이 있습니다.

따라서 입력이 n =27 count =[8,4,3,2]와 같으면 출력은 18이므로 18개의 가능한 조합이 있습니다.

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

등등...

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

데놈 :=[1,2,5,10]
A :=크기(n + 1)의 배열이고 0으로 채워짐
B :=A의 새 목록
0에서 (count[0] 및 n의 최소값) 범위에 있는 i에 대해
- A[i] :=1
1~3 범위의 i에 대해 다음을 수행합니다.
- 범위 0의 j가 [i]를 계산하려면 다음을 수행합니다.
  - 0 ~ n + 1 - j *denom[i] 범위의 k에 대해, do
    - B[k + j * denom[i]] :=B[k + j * denom[i]] + A[k]
- 0에서 n 사이의 j에 대해 다음을 수행합니다.
  - A[j] :=B[j]
  - B[j] :=0
반환 A[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))

입력

27, [8,4,3,2]