C言語で解くコイン両替問題：合計金額を作る組み合わせの総数を求める方法

コイン両替問題とは

この問題では、金額 n が与えられ、その n ルピーを両替する方法を考えます。使用できるのは、1 から m の範囲の価値を持つ複数種類の硬貨です。求めるのは、合計がちょうど n になる硬貨の組み合わせの総数です。

例

入力 : N = 6 ; coins = {1, 2, 4}
出力 : 6
説明 : 合計が 6 になる組み合わせは以下の 6 通りです。
{1,1,1,1,1,1} ; {1,1,1,1,2} ; {1,1,2,2} ; {1,1,4} ; {2,2,2} ; {2,4}

C言語での実装（動的計画法）

以下のプログラムは、動的計画法（DP）を用いて組み合わせの総数を効率的に計算します。二次元テーブル table[i][j] は「j 番目までの硬貨を使って金額 i を作る組み合わせの数」を格納します。

#include <stdio.h>
int coins( int S[], int m, int n ) {
    int i, j, x, y;
    int table[n+1][m];
    /* 金額 0 を作る方法は常に 1 通り（何も選ばない） */
    for (i=0; i<m; i++)
        table[0][i] = 1;
    for (i = 1; i < n+1; i++) {
        for (j = 0; j < m; j++) {
            /* S[j] を使う場合の組み合わせ数 */
            x = (i-S[j] >= 0)? table[i - S[j]][j]: 0;
            /* S[j] を使わない場合の組み合わせ数 */
            y = (j >= 1)? table[i][j-1]: 0;
            table[i][j] = x + y;
        }
    }
    return table[n][m-1];
}
int main() {
    int arr[] = {1, 2, 3};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = 4;
    printf("The total number of combinations of coins that sum up to %d",n);
    printf(" is %d ", coins(arr, m, n));
    return 0;
}

アルゴリズムのポイント

• 初期化： 金額 0 を作る方法は常に 1 通り（硬貨を一切使わない）なので、テーブルの 0 行目をすべて 1 に設定します。
• 遷移： 各セルは「現在の硬貨 S[j] をもう 1 枚使う場合（x）」と「S[j] を使わずにそれ以前の硬貨だけで作る場合（y）」の和として計算されます。
• 計算量： 時間計算量は O(n × m)、空間計算量も O(n × m) となり、全列挙よりも大幅に高速です。

出力結果

The total number of combinations of coins that sum up to 4 is 4

この例では、硬貨 {1, 2, 3} を使って金額 4 を作る組み合わせが 4 通り（{1,1,1,1}、{1,1,2}、{2,2}、{1,3}）存在することを示しています。