コイン問題を動的計画法とC++で解く

AIZU_ONLINE_JUDGEのDPL_1_Aの問題を使用して、コイン問題を解きます。
コイン問題を以下に引用します。

問題

額面がc1, c2,..., cm　円の　m　種類のコインを使って、
n 円を支払うときの、コインの最小の枚数を求めて下さい。
各額面のコインは何度でも使用することができます。

入力

n m
C1C2・・・Cm

１行目に整数 n と整数 m が１つの空白区切りで１行に与えられます。
２行目に各コインの額面が１つの空白区切りで１行に与えられます。

出力

コインの最小枚数を1行に出力してください

制約

1 ≤ n ≤ 50,000
1 ≤ m ≤ 20
1 ≤ 額面 ≤ 10,000
額面はすべて異なり、必ず1を含む。

入力・出力例

15 6
1 2 7 8 12

2

解法

使用できるコインの額面が決まって入れば、額面が大きいものから引いていけば、
最小枚数を求めることができますが、今回の出力例でその方法を使用すると...

12 2 1
3

3となってしまい7,8を選んだ場合の最小値2となりません。
なので、貪欲法は使えません。

ここでは、以下のような配列の入れ物を定義し、
最小枚数を求めます

coin[m] : coin[i]をi番目のコインの額面とする配列
T[m][n + 1] : T[i][j]をi番目までのコインを使ってj円支払う時のコインの最小枚数とする2次元配列

コインの枚数をi,各iにおける支払う金額jを増やしていき、T[i][j]を更新していきます。
T[i][j]は、i番目のコインを使う場合と使わない場合の枚数を比べ、小さい方を選べばよいので、
次のような漸化式で求めることができます。

T[i][j] = min(T[i - 1][j],T[i][j - C[i]] + 1)

i枚目のコインを使わない場合は、ここまで計算したj円を払う最適解T[i - 1][j]となり、
使った場合は、現在の金額jからC[i]を引いた金額を払う最適解に1枚足した値になります。

配列の具体例

例題のように、支払う金額を15とし、コインの額面を1 2 7 8 12として
coin[m]とT[m][n + 1]の中身を見てみましょう

coin

1
2
7
8
12

T

0	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF	INF
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	1	1	2	2	3	3	4	4	5	5	6	6	7	7	8
0	1	1	2	2	3	3	1	2	2	3	3	4	4	2	3
0	1	1	2	2	3	3	1	1	2	2	3	3	4	2	2
0	1	1	2	2	3	3	1	1	2	2	3	1	2	2	2

例として、3枚目のコイン(額面8indexは０から)までのコインを使って15円を払う最適解は、
min(T[2][15],T[3][15-8] + 1)より2枚になります。
これは、先に述べたように3枚目のコインまでを使って7円払う最適解に1足したものです。

先の表からわかるように、コインの額面ごとに最適枚数を記録しておく必要はないので、
j円を支払うときのコインの最小枚数は1次元配列の要素T[j]として、次のように求めることができます。

T[j] = min[T[j],T[j - C[i]] + 1)

以上を踏まえて、c++を言語としてプログラムをみていきましょう

#include <iostream>
#include <algorithm>

using namespace std;

#define M_MAX 20
#define N_MAX 50000
#define INFTY 1 << 29

int main(){
    int n,m;
    int coin[21];
    int T[N_MAX + 1];
    
    cin >> n >> m;
    // コインに額面を代入する
    for(int i = 1;i <= m;++i){
        cin >> coin[i];
    }
    
    // 最大値で初期化
    for(int i = 0;i < N_MAX;++i){
        T[i] = INFTY;
    }
    T[0] = 0;
    for(int i = 1;i <= m;++i){
        for(int j = 0;j + coin[i] <= n;++j){
            T[j + coin[i]] = min(T[j + coin[i]],T[j] + 1);
        }
    }
    cout << T[n] << endl;
    return 0;
}

参考