与えられたコインでnルピーを取得する方法を見つけるPythonプログラム

金種（1、2、5、10）の硬貨を渡したとします。これらの支配を使用して、nをどのように配置できるかを見つける必要があります。 4つの要素を持つcountという配列があります。ここで、count [0]は1のコインの数を示し、count[1]は2のコインの数を示します。

したがって、入力が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

など...

これを解決するには、次の手順に従います-

• denom：=[1,2,5,10]
• A：=サイズ（n + 1）の配列で、0で埋めます
• B：=Aからの新しいリスト
• 0から（count [0]およびnの最小値）の範囲のiの場合、do
  • A [i]：=1
• 1〜3の範囲のiについては、
  • 範囲0からcount[i]のjの場合、実行
    • 0〜n +1の範囲のkの場合-j*denom [i]、do
      • B [k + j * denom [i]]：=B [k + j * denom [i]] + A [k]
  • 0からnの範囲のjについては、
    • A [j]：=B [j]
    • B [j]：=0
• return 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]

出力

18