用一个结构体pre数组来记录前一步的信息
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int C,n[30],v[5]={ 0,1,5,10,25 }; int dp[15000]; struct PRE { int ID,NUM,P; } pre[15000]; int main() { int i,j,k,x; while(1) { scanf("%d%d%d%d%d",&C,&n[1],&n[2],&n[3],&n[4]); if(!(C|n[1]|n[2]|n[3]|n[4])) break; for(i=0;i<=C;i++){ dp[i]=-1; pre[i].ID=i; pre[i].NUM=pre[i].P=0; }dp[0]=0; for(i=1;i<=4;i++) { x=1; while(n[i]>0){ if(x>n[i]) x=n[i];n[i]-=x; for(j=C;j>=x*v[i];j--) if(dp[j-x*v[i]]>=0&&dp[j]<dp[j-x*v[i]]+x){ dp[j]=dp[j-x*v[i]]+x; pre[j].ID=j-x*v[i]; pre[j].NUM=x; pre[j].P=v[i]; } x*=2; } } // for(i=1;i<=C;i++) printf("%d ",pre[i].ID);printf("\n");//while(1); // for(i=1;i<=C;i++) printf("%d ",dp[i]);printf("\n"); if(dp[C]>0){ for(memset(n,0,sizeof(n)),x=C;x!=0;x=pre[x].ID) n[pre[x].P]+=pre[x].NUM; printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",n[1],n[5],n[10],n[25]); } else printf("Charlie cannot buy coffee.\n"); } return 0; }