[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 (动态规划)

时间: 10-22

[POJ 1787]Charlie's Change (动态规划)的相关文章

POJ 1787 Charlie&#39;s Change

POJ 1787 Charlie's Change 背包系列 + 路程记录 乍一看.多重背包. 再乍.转化01背包?nonono,每样物品的数量达到了10^4,肯定会T. 再乍.看不出来了.去看大牛的题解吧. 哦——转化成完全背包. 怎么转?一般的完全背包是不限个数的.现在我们每一次枚举物品时记录一下取了多少个然后限制一下不要超过个数就好了. 恩.. 路程记录的话完全背包加一个path记录父亲..然后多重背包加一个num数组在dp的时候直接算一算..具体看代码..完全背包的那版路径记录感觉十分巧

POJ 1787 Charlie&amp;#39;s Change

多重背包 可行性+路径记录 题意是说你要用很多其它的零钱去买咖啡.最后输出你分别要用的 1,5 ,10 .25 的钱的数量. 多重背包二进制分解.然后记录下 这个状态.最后逆向推就可以. #include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #

zoj 2156 - Charlie&#39;s Change

题目:钱数拼凑,面值为1,5,10,25,求组成n面值的最大钱币数. 分析:dp,01背包.需要进行二进制拆分,否则TLE,利用数组记录每种硬币的个数,方便更新. 写了一个 多重背包的 O(NV)反而没有拆分快.囧,最后利用了状态压缩优化 90ms: 把 1 cents 的最后处理,其他都除以5,状态就少了5倍了. 说明:貌似我的比大黄的快.(2011-09-26 12:49). #include <stdio.h> #include <stdlib.h> #include <

Charlie&#39;s Change(完全背包+路径记忆)

Charlie's Change Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 3176   Accepted: 913 Description Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at coffee vending machines at motores

POJ1787——背包DP(特定状态+回溯)——Charlie&#39;s Change

Description Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at coffee vending machines at motorests. Charlie hates change. That is basically the setup of your next task. Your program will be given

POJ 1160 Post Office (动态规划)

Post Office Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 15412   Accepted: 8351 Description There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each villa

poj1787 Charlie&#39;s Change

思路: 完全背包,记录路径. 实现: 1 #include <bits/stdc++.h> 2 using namespace std; 3 const int INF = 0x3f3f3f3f; 4 int v[4] = {1, 5, 10, 25}; 5 int c[4], m; 6 int dp[10005], used[10005], path[10005]; 7 int main() 8 { 9 while (cin >> m >> c[0] >>

poj 3267 The Cow Lexicon 动态规划

题目链接:http://poj.org/problem?id=3267 给一个字典 求原串中至少去掉多少个字母可以让已给字典可以完整覆盖原串 在跟字典作匹配时 注意原串是“可跳跃的” 即存在“删掉某个字母后 该字母的前后两部分拼起来组成单词” 针对这种情况 考虑使用两个指针 匹配时:同时往后滑1格 不匹配时:仅指向原串的指针往后滑1格 之所以网上大部分题解都是从原串的最后往前推 是因为这样写起来下标容易控制 最外层循环的原串从后往前 则匹配过程可以较自然地从前往后 而匹配过程明显更为复杂 所以这

poj 1160 Post Office (区间动态规划)

Post Office Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 15966   Accepted: 8671 Description There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each villa