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();
}