# （多重背包+记录路径）Charlie's Change （poj 1787）

http://poj.org/problem?id=1787

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 numbers and types of coins Charlie has and the coffee price. The coffee vending machines accept coins of values 1, 5, 10, and 25 cents. The program should output which coins Charlie has to use paying the coffee so that he uses as many coins as possible. Because Charlie really does not want any change back he wants to pay the price exactly.

Each line of the input contains five integer numbers separated by a single space describing one situation to solve. The first integer on the line P, 1 <= P <= 10 000, is the coffee price in cents. Next four integers, C1, C2, C3, C4, 0 <= Ci <= 10 000, are the numbers of cents, nickels (5 cents), dimes (10 cents), and quarters (25 cents) in Charlie‘s valet. The last line of the input contains five zeros and no output should be generated for it.输出For each situation, your program should output one line containing the string "Throw in T1 cents, T2 nickels, T3 dimes, and T4 quarters.", where T1, T2, T3, T4 are the numbers of coins of appropriate values Charlie should use to pay the coffee while using as many coins as possible. In the case Charlie does not possess enough change to pay the price of the coffee exactly, your program should output "Charlie cannot buy coffee.".

```12 5 3 1 2
16 0 0 0 1
0 0 0 0 0
```

```Throw in 2 cents, 2 nickels, 0 dimes, and 0 quarters.
Charlie cannot buy coffee.```

```#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;

#define met(a,b) (memset(a,b,sizeof(a)))
#define N 11000
#define INF 0x3f3f3f3f

int pre[N], v[5]={0,1,5,10,25}, dp[N];
int used[N];

/**

dp[i]   代表组成i元时需要的最多的硬币
used[i] 代表第i种硬币用了几次（感觉这点很好，能将多重背包转化为完全背包）
pre[j]  记录的是j从哪个状态转化过来的

*/

int main()
{
int p, num[5]={0};

while(scanf("%d%d%d%d%d", &p, &num[1], &num[2], &num[3], &num[4]), p+num[1]+num[2]+num[3]+num[4])
{
int i, j, ans[110]={0};

met(dp, -1);
met(pre, -1);
dp[0] = 0;
for(i=1; i<=4; i++)
{
memset(used, 0, sizeof(used));
for(j=v[i]; j<=p; j++)
{
if(dp[j-v[i]]+1>dp[j] && dp[j-v[i]]>=0 && used[j-v[i]]<num[i])
{
dp[j] = dp[j-v[i]]+1;
used[j] = used[j-v[i]]+1;
pre[j] = j-v[i];
}
}
}

if(dp[p]<0)
printf("Charlie cannot buy coffee.\n");
else
{
met(ans, 0);
i = p;
while(1)
{
if(pre[i]==-1) break;
ans[i-pre[i]]++;
i = pre[i];
}
printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[v[1]], ans[v[2]], ans[v[3]], ans[v[4]]);
}

}
return 0;
}```

（多重背包+记录路径）Charlie's Change （poj 1787）

## poj1787Charlie&#39;s Change(多重背包+记录路径+好题)

Charlie's Change Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 3720   Accepted: 1125 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 motore

## POJ - 1787　(多重背包还原路径|| 完全背包)

POJ  1787  Charlie'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

## poj 1787 背包+记录路径

http://poj.org/problem?id=1787 Charlie's Change Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 4512   Accepted: 1425 Description Charlie is a driver of Advanced Cargo Movement, Ltd. Charlie drives a lot and so he often buys coffee at co

## POJ 1293 Duty Free Shop(背包记录路径）

Description Pedro travelled to Europe to take part in the International Olympiad in Informatics and is coming back home. Since all his friends asked him to bring them some gift, he bought two big bags of chocolates (one of Mindt and one of Lilka). Ea

## poj1417 带权并查集 + 背包 + 记录路径

True Liars Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 2713   Accepted: 868 Description After having drifted about in a small boat for a couple of days, Akira Crusoe Maeda was finally cast ashore on a foggy island. Though he was exha

## UVA 624(01背包记录路径)

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=565 记录路径可以用一个二维数组,记录改变时的量.然后从后往前可以推得所有的值. #include <iostream> #include <string> #include <cstring> #include <cstdlib> #incl