多重背包转化成完全背包 E - Charlie's Change - Windows

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

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

这个题目我一看就觉得是一个多重背包，但是呢，我不知道怎么输出路径，所以无可奈何，我就只能看一下题解了。

看了题解发现居然是把多重背包转化成完全背包，昨天学习了多重背包转化成01背包求解，今天又学习了这个。

题目大意：就是给你一个数字n，和1分钱的数量，5分钱的数量，10分钱的数量，25分钱的数量，

让你求组成这个数字n需要1分钱5分钱10分钱25分钱的数量，输出。

思路：

dp[i]定义为组成 i 的硬币数量最多为多少。

这个题目就是把硬币的价格当作容量，把硬币的数量当作数量，每一个硬币的价值都是1.

所以这个因为必须装满，所以dp[0]=0,其他都是-inf，转移方程就很简单了，这个具体看代码

最后就是一个路径记录，因为这个是多重背包，所以需要一个数组对某一种硬币使用数量进行限制。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#include <vector>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5 + ;int dp[maxn], used[maxn], path[maxn];
int weight[] = { ,,, };int main()
{
int n, num[];
while(scanf("%d%d%d%d%d",&n,&num[],&num[],&num[],&num[])!=EOF)
{
if (n == && num[] == && num[] == && num[] == && num[] == ) break;
memset(dp, -inf, sizeof(dp));
memset(path, , sizeof(path));
dp[] = ;
path[] = -;
for(int i=;i<;i++)
{
memset(used, , sizeof(used));
for(int j=weight[i];j<=n;j++)
{
if(dp[j-weight[i]]+>dp[j]&&dp[j-weight[i]]>=&&used[j-weight[i]]<num[i])
{
dp[j] = dp[j - weight[i]] + ;
path[j] = j - weight[i];
used[j] = used[j - weight[i]] + ;
}
}
}
if (dp[n] < ) printf("Charlie cannot buy coffee.\n");
else
{
int ans[];
memset(ans, , sizeof(ans));
while(path[n]!=-)
{
ans[n - path[n]]++;
n = path[n];
}
printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[weight[]], ans[weight[]], ans[weight[]], ans[weight[]]);
}
}
return ;
}