poj 1787 求达到总钱数的选硬币的最大数量(硬币有个数限制)

本文主要是介绍poj 1787 求达到总钱数的选硬币的最大数量(硬币有个数限制)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<cstdio>
#include<cstring>
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)>(y)?(y):(x))
int dp[10010],path[10010],u[10010];
int main()
{int v[]={1,5,10,25};int n[5],col,ans[26];while(~scanf("%d%d%d%d%d",&col,&n[0],&n[1],&n[2],&n[3])){if((col+n[0]+n[1]+n[2]+n[3])==0)break;memset(dp,-1,sizeof(dp));path[0]=-1; dp[0]=0;for(int i=0;i<4;i++){memset(u,0,sizeof(u));for(int j=v[i];j<=col;j++){if(dp[j-v[i]]>=0&&dp[j-v[i]]+1>dp[j]&&u[j-v[i]]<n[i]){u[j]=u[j-v[i]]+1;dp[j]=dp[j-v[i]]+1;path[j]=j-v[i];}}}if(dp[col]<0)printf("Charlie cannot buy coffee.\n");else{memset(ans,0,sizeof(ans)); while(path[col]!=-1){ans[col-path[col]]++;col=path[col];}printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",ans[1],ans[5],ans[10],ans[25]);}} 
} 

这篇关于poj 1787 求达到总钱数的选硬币的最大数量(硬币有个数限制)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---