# [POJ 1787]Charlie's Change (动态规划)

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

## POJ 1787 Charlie&#39;s Change

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

## 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

## 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