PKU 2818 Making Change
http://poj.org/problem?id=2818
25セント硬貨、10セント硬貨、5セント硬貨、1セント硬貨の枚数と、払わなくてはいけないお金が入力される。
最も少ない枚数で支払うときの方法を求めろというような問題。
DP+経路復元的な問題。
経路復元というと微妙な感じがしますね。
経路復元の順番を間違えてWAをもらいました。
int dp[1000]; int mo[4],c; int ce[]={25,10,5,1}; void solve(){ rep(i,c+1)dp[i]=1000000; dp[0]=0; rep(i,4){ for(int cc=c;cc;--cc) rep(j,mo[i]) if(cc-(j+1)*ce[i]>=0) dp[cc]=min(dp[cc],dp[cc-(j+1)*ce[i]]+(j+1)); } if(dp[c]==1000000){ cout<<"Cannot dispense the desired amount."<<endl; return; } int an[4]={0}; for(int i=3;i>=0;--i){ for(int j=mo[i]-1;j>=0;--j) if(c-(j+1)*ce[i]>=0 && dp[c]==dp[c-(j+1)*ce[i]]+j+1){ an[i]=j+1; c=c-(j+1)*ce[i]; break; } } printf("Dispense %d quarters, %d dimes, %d nickels, and %d pennies.\n", an[0],an[1],an[2],an[3]); } main(){ while(cin>>mo[0]>>mo[1]>>mo[2]>>mo[3]>>c, mo[0]|mo[1]|mo[2]|mo[3]|c) solve(); }