手持ちのコインでnルピーを作る組み合わせの数を求めるPythonプログラム

1ルピー、2ルピー、5ルピー、10ルピーという4種類の額面のコインが与えられているとします。このとき、これらのコインを使って合計 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 + 2×4 + 1×4 = 27

など、他にも多数の組み合わせがあります。

解き方のアプローチ

この問題は動的計画法（DP）を用いて効率的に解くことができます。手順は以下のとおりです。

1. 額面のリストを用意する：denom = [1, 2, 5, 10]
2. サイズ n + 1 の配列 A を作り、すべて0で初期化する
3. A をコピーした作業用リスト B を用意する
4. i を 0 から min(count[0], n) まで繰り返し、A[i] = 1 とする（1ルピーコインだけで作れる金額の初期化）
5. i を 1 から 3 まで繰り返し、各額面について以下を処理する：
   • j を 0 から count[i] まで繰り返し、さらに k を 0 から n + 1 - j * denom[i] まで繰り返して、B[k + j * denom[i]] += A[k] を行う
6. 処理後、j を 0 から n まで繰り返し、A[j] = B[j] として結果を反映し、B[j] = 0 でリセットする
7. 最後に A[n] を返す

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

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

まとめ

このプログラムでは、まず1ルピーコインだけで作れる金額のパターンを初期化し、その後2ルピー、5ルピー、10ルピーのコインを順に加えながら、各金額に対する組み合わせの数を累積的に更新していきます。コインの枚数に上限がある制約付きの組み合わせ問題に対して、動的計画法が有効であることを示す良い例といえます。