HDU 2844 Coins (多重背包+二进制优化)
HDU 2844 Coins (多重背包+二进制优化)
Ch_Zaqdt
发布于 2019-01-10 11:14:29
发布于 2019-01-10 11:14:29
? ? ? ?首先这是一道多重背包的裸题，题意在代码中的注释里有。多重背包就是所给的物品是有限的(任意个)，我们则可以把多重背包的问题转换成01背包和完全背包来求解。首先我们先把01背包和多重背包的过程封装成函数，需要用的时候传参过去就好了，然后我来解释一下什么时候用01背包，什么时候用完全背包。我们先不考虑价值，假如说A的重量是3，有10个，B的重量是5，有2个，而你的背包的最大重量为15。对于A来说，3*10=30，它大于你的背包的最大重量，可以夸张的当成A物品是有无限个的，因为在你背包重量的允许下A物品是想装多少就装多少的，这时候就把A物品当成完全背包来装，而B物品就需要当成两个01背包来装了。这就是多重背包的大致思路，当然对于多重背包还有一个二进制优化，因为如果一个物品在你的背包最大承重范围内的个数太多，这就要装好几次01背包，所以用二进制优化可以缩短同一物品使用01背包的次数。下面我就大致解释一下二进制优化过程。
? ? ? ?比如一个物品需要装37次我们可以拆成1，2，4，8，16，32，用这些数我们可以组合成1-36的任意一个数，要组成37的话，我们就需要再加一个37-32=5，这样我们就把循环了37次的01背包优化成循环7次就好了。如果要装13次，那么就传进去1*val，4*val，8*val就行了(和13*val等价)。具体过程结合代码中的二进制优化部分看一下，还是挺好理解的。
AC代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#define INF 0x3f3f3f3f // 用于完全背包初始化
#define MAX(a,b) a>b?a:b
using namespace std;
const int MAXN = 100050;
int dp[MAXN];
int val[MAXN]; // 硬币重量
int num[MAXN]; // 硬币数量
int n,m,sum;
void ZeroPack(int v){ // 01背包
for(int i=m;i>=v;i--){
dp[i] = MAX(dp[i],dp[i-v]+v);
}
}
void CompletePack(int v){ // 完全背包
for(int i=v;i<=m;i++){
dp[i] = MAX(dp[i],dp[i-v]+v);
}
}
void MutiplePack(int v,int num){
if(v * num > m){ // 当这个硬币价值*数量大于m的时候可以看作硬币数量为无限个
CompletePack(v);
}
else{
int k = 1;
while(k<=num){ // 二进制优化
ZeroPack(k * v);
num -= k;
k *= 2;
}
ZeroPack(num*v); // 当k<num时，需要再加一个背包
}
}
int main()
{
while(~scanf("%d%d",&n,&m)){
if(n==0&&m==0) break;
sum = 0;
for(int i=0;i<n;i++){
scanf("%d",&val[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&num[i]);
}
memset(dp,-INF,sizeof(dp)); // 完全背包初始化
dp[0] = 0; // 背包容量为0时符合情况
for(int i=0;i<n;i++){
MutiplePack(val[i],num[i]);
}
for(int i=0;i<=m;i++){
if(dp[i] > 0) sum++; // 当背包被定义说明情况存在
}
cout<<sum<<endl;
}
return 0;
}
/***
[来源] HDU 2844
[题目] Coins
[大意]
这是一道多重背包的模板题，多组输入输出，先输入n,m表示有n种硬币，背包容量为m，这道题最后让求从1到m，
你可以组合出多少种方案，换个方向去思考就是有容量为m的背包，现在给你分别都有数量限制的物品的重量让你
去装，问最终装的物品的重量不大于m的方法有多少种。
[输入]
3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0
[输出]
8
4
*/本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年02月10日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读