コイン交換のためのPythonプログラム

この記事では、以下に示す問題ステートメントの解決策について学習します。

問題の説明 − N枚のコインが与えられ、Sに各値が無限に供給されるように、それらのコインを変更したいと考えています。順序に関係なく、変更できる方法がいくつあるかを表示する必要があります。

動的計画法の概念を使用して問題ステートメントを解決し、時間の複雑さを軽減します。

次に、以下の実装のソリューションを見てみましょう-

例

# dynamic approach
def count(S, m, n):
   # base case
   table = [[0 for x in range(m)] for x in range(n+1)]
   # for n=0
   for i in range(m):
      table[0][i] = 1
   # rest values are filled in bottom up manner
   for i in range(1, n+1):
      for j in range(m):
         # solutions including S[j]
         x = table[i - S[j]][j] if i-S[j] >= 0 else 0
         # solutions excluding S[j]
         y = table[i][j-1] if j >= 1 else 0
         # total
         table[i][j] = x + y
   return table[n][m-1]
# main
arr = [1, 3, 2, 4]
m = len(arr)
n = 5
print(“Number of coins:”,end=””)
print(count(arr, m, n))

出力

Number of coins:6

すべての変数はローカルスコープで宣言されており、それらの参照は上の図に示されています。

結論

この記事では、コイン交換用のPythonプログラムを作成する方法について学びました