プログラミングトレーニング-両替問題(ダイナミックプランニングで)

タイトル
//mを入力すると、m種類の紙幣があることを示します;//base[1]~base[m]を入力すると、各紙幣の額面が表示されます.//nを入力します.n元をこれらの額面に両替したいことを意味します.両替枚数が一番少ない場合、一番少ない枚数と額面ごとに必要な枚数を求めます.//base[1]が必ず1であると仮定すると、両替方法が見つからない場合はありません.どんな額面でも1元を何枚も両替できるからです.
サンプル入力

3
1 3 4
100

m=3は、3種類の紙幣があることを示し、額面はそれぞれbase[1]=1、base[2]=3、base[3]=4元で、n=100元を両替する必要がある.制限mとnは最大100を超えない.
サンプル出力

25
0 0 25

その結果、最小25枚の紙幣が必要で、それぞれ0枚1元、0枚3元、25枚4元だった.
アルゴリズム#アルゴリズム#
動的に計画する.2つのdp配列を用いる必要があり、m o n e y[i]money[i]money[i]はi元を両替するのに必要な最小限の紙幣数を表し、M i n n u m[i][j]MinNum[i][j]MinNum[i][j]MinNum[i][j]はi i i i元を両替するのに必要な額面b a s e[j]base[j]の枚数を表す.
m o n e y[0]=0 money[0]=0 money[0]=0 money[0]=0に初期化されます.なぜなら、どんな額面があっても、0 0 0 0 0元を両替するには紙幣が必要ないからです.同様にM i n N u m[0][j]=0 MinNum[0][j]=0 MinNum[0][j]=0であり、0 0 0 0元を両替するのに必要な任意の額面値は0 0 0 0枚である.
m o n e y[i]money[i]money[i]money[i]money[i]money[i]money[i]money[i]money[i]money[i−b a s e[1]+1 money[i−base[1]]+1 money[i−base[1]+1 money[i−base[2]+1 money[i−base[2]+1,…,m o n e[i−b a s e[m]+1 money[i−base[m]+1 money[i−base[m]+1 money[m]+1 money[b−base[m]+1 money[m]+1 moneyの最小値でいいです(注意判断i≧b a s e[j]  f o r   j = 1 ∼ m i≥base[j]\for\j=1\sim{m} i≥base[j] for j=1〜m);i≧b a s e[j]i≧base[j]i≧base[j]i≧base[j]が存在し、問題はいかなる数値も両替できると仮定しているため、j j j jが存在する.
M i n n N u m[i][j]MinNum[i][j]MinNum[i][j]MinNum[i][j]を更新するのは少し面倒ですが、上記のようにm o n e y[i]money[i]money[i−b a s e[j]+1 money[i]+1 money[j]+1(j=1～m j=1～m j=1～m)の最小値であることがわかります.このj 0 j_0 j 0に対しては、額面b a s e[j 0]base[j 0]base[j 0]+1 money[j 0]+1 money[j 0]+1 money[j 0]base[j 0]base[j 0]は必ずi i i i i i i元を両替するために選択しなければならないという意味である.したがって、M i n n N u m[i]=M i n n N u m[i−b a s e[j 0][j 0][j 0]ではない]MinNum[j 0]=MinNum[j_0]=MinNum[j_0][j_0]ではない[j_0]=MinNum[j_0]ではない]Min[j 0ではない]=MinNum[i−base[j 0]][j 0ではない],M i n n N u m[i]=M i n N u m[i−b a−b a s e[j 0][j 0]+1 MinNum[j 0]+1 MinNum[j 0]=MinNum[j_0]=MinNum[j_i−base[j_0]][j_0]+1 MinNum[i]=MinNum[i][j 0]=MinNum[i−base[ j 0]][j 0]+1.(ここでは必ずi≧b a s e[j 0]i≧base[base[j 0]i≧base[base[j 0]i≧base[j 0]i≧e[j 0])
リファレンスコード

#include

#define maxm 105
#define maxn 105

int main(){
    int base[maxm+1], money[maxn+1], MinNum[maxn+1][maxm+1];
    int n, m;
    int temp = 0;
    while(scanf("%d", &m)==1){
    	//       
        for(int i = 1;i <= m;i++){
            scanf("%d", &base[i]);
        }
        scanf("%d", &n);

        //    dp  
        money[0] = 0;
        for(int j = 1;j <= m;j++){
            MinNum[0][j] = 0;
        }
        
        for(int i = 1;i <= n;i++){

            //   money[]
            for(int j = 1;j <= m;j++){
                if(i>=base[j]){
                    temp = (money[i-base[1]]<money[i-base[j]]) ? 1 : j;
                }
            }
            money[i] = money[i-base[temp]] + 1;

            //   MinNum[][]
            for(int j = 1;j <= m;j++){
                MinNum[i][j] = MinNum[i-base[temp]][j];
            }
            MinNum[i][temp] = MinNum[i][temp] + 1;
        }

        //     
        printf("%d
", money[n]);
        for(int j = 1;j < m;j++){
            printf("%d ", MinNum[n][j]);
        }
        printf("%d
", MinNum[n][m]);
    }

     return 0;
}