首页 > 代码库 > [POJ 1787]Charlie's Change (动态规划)
[POJ 1787]Charlie's Change (动态规划)
题目链接：http://poj.org/problem?id=1787
题意：有4种货币分别是1元，5元，10元，20元。现在告诉你这四种货币分别有多少个，问你正好凑出P元钱最多可以用多少货币。每种货币要用多少钱。
据说此题有完全背包的写法。。
我是按照多重背包写的，速度也不是很慢。
然后记录了下前驱。
刚开始全都写挫了。。虽然现在也很挫。。
凑合着看吧 --
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using namespace std; 9 typedef long long LL;10 11 const int INF = 99999999;12 13 int P,c[10],v[10];14 int dp[11000];15 int fa[11000][10];16 17 int main(){18 v[1] = 1;19 v[2] = 5;20 v[3] = 10;21 v[4] = 25;22 while(1){23 scanf("%d",&P);24 for(int i=1;i<=4;i++) scanf("%d",&c[i]);25 if( P==0 && c[1]==0&&c[2]==0&&c[3]==0&&c[4]==0){26 break;27 }28 for(int j=0;j<11000;j++){29 dp[j] = -INF;30 }31 dp[0] = 0;32 memset(fa,0,sizeof(fa));33 for(int i=1;i<=4;i++){34 if( c[i]*v[i]>P ){35 for(int j=v[i];j<=P;j++) {36 if( dp[j]<dp[j-v[i]]+1){37 dp[j] = dp[j-v[i]]+1;38 if( dp[j]<=0 ) continue;39 for(int k=1;k<=4;k++){40 if( k==i ) fa[j][k] = fa[j-v[i]][k] + 1;41 else fa[j][k] = fa[j-v[i]][k];42 }43 }44 // dp[j] = max(dp[j],dp[j-v[i]]+1);45 }46 } else {47 int k = 1;48 while( k<c[i] ){49 for(int j=P;j>=v[i]*k;j--){50 if( dp[j]<dp[j-v[i]*k]+k ){51 dp[j] = dp[j-v[i]*k]+k ;52 // if( dp[j]>=0 ) fa[j][i] = fa[j-v[i]*k][i] + k;53 if( dp[j] <=0 ) continue;54 for(int e=1;e<=4;e++){55 if( e==i ) fa[j][e] = fa[j-v[i]*k][e] + k;56 else fa[j][e] = fa[j-v[i]*k][e];57 }58 }59 // dp[j] = max(dp[j],dp[j-v[i]*k]+k);60 }61 c[i] -= k;62 k <<= 1;63 }64 if( c[i]<=0 ) continue;65 for(int j=P;j>=v[i]*c[i];j--){66 if( dp[j]<dp[j-v[i]*c[i]] + c[i] ){67 dp[j] = dp[j-v[i]*c[i]] + c[i];68 if( dp[j] <=0 ) continue;69 for(int e=1;e<=4;e++){70 if( e==i ) fa[j][e] = fa[j-v[i]*c[i]][e] + c[i];71 else fa[j][e] = fa[j-v[i]*c[i]][e];72 }73 }74 // dp[j] = max(dp[j],dp[j-v[i]*c[i]] + c[i] );75 }76 }77 }78 if( dp[P] <=0 ) puts("Charlie cannot buy coffee.");79 else printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",fa[P][1],fa[P][2],fa[P][3],fa[P][4]);80 }81 return 0;82 }
[POJ 1787]Charlie's Change (动态规划)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。