概述
今天大年初一，在这里祝广大love_leraning新年快乐！
多重背包
定义：给定n种物品和一背包。物品i的重量是wi，其价值为vi，每件物品的数量为xi，背包的容量为m。
思路：即在01背包的基础上加上一遍数量的循环，把每个物品的每件都看成不同的即可。
伪代码：
for(i=0;i<n;i++)
for(j=m;j>=w[i];j--)
for(k=1;k<=xi;k++){
if(k*w[i]>j) break;
dp[j]=max{dp[j],dp[j-k*w[i]]+k*v[i]};
}时间复杂度 O(k*m*n)。。。
优化多重背包
其实上面的方法就是把n个i物品看成n个不同的物品，对于每一个都01背包做一遍，分法不同，时间复杂度上k就不同。
对于k件物品i，我们要找一个分法使分完后的几个部分可以组成1~k，这里考虑参考二进制对k进行分割，把k分成1，2，4……2^n，k-(1+……+2^n)这几个部分。对于这几个部分的取与不取，便可代替对i物品取1~k中任意数量。（对于1~(1+……+2^n)部分可以由二进制部分表示，(1+……+2^)~k部分可以由总和减去二进制部分表示）
代码实现：
D dp[100100];
void ZeroOne_Pack(int cost,int weight,int n)
{
for(int i=n; i>=cost; i--)
dp[i] = max(dp[i],dp[i-cost] + weight);
}
void Complete_Pack(int cost,int weight,int n)
{
for(int i=cost; i<=n; i++)
dp[i] = max(dp[i],dp[i-cost] + weight);
}
int Multi_Pack(int c[],int w[],int num[],int n,int m)
{
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++)
{
if(num[i]*c[i] > m)
Complete_Pack(c[i],w[i],m);
else
{
int k = 1;
while(k < num[i])
{
ZeroOne_Pack(k*c[i],k*w[i],m);
num[i] -= k;
k <<= 1;
}
ZeroOne_Pack(num[i]*c[i],num[i]*w[i],m);
}
}
return dp[m];
}
解析：
对于每件物品，如果每件的大小 * 件数 > 总背包大小，就可以视为完全包了（没有了数量的限制），else 就把k件i按照二进制分成几件物品，对这几件物品逐一01背包，时间复杂度降为O(logk*n*m)。
例题
原题：Big Event in HDU
题意：n种设备，每种有nu[i]件，价值为val[i]，要求把所以设备分成两边，使两边的总价值相差最小。
解析：如果不是在学这个专题的时候看这个，我可能真的想不到用背包做。其实就是一个大小为sum/2（向下取整，因为这里先算小的那部分），努力塞满这个包，那么和剩下的那部分相差一定最小。
这道题边吐血边AC，只能怪我太粗心（题目说的是负数输入结束，我while里面写的是~n，只看到案例就以为-1结束。。。）
input里面说N小于50，开数组大小应该为50*50*100/2。
首先是直接套模板ac，时间为156MS
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#define D long long
#define F double
#define MAX 0x7fffffff
#define MIN -0x7fffffff
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define pill pair<int, int>
#define for1(i,a,b) for(int i=a;i<=b;i++)
#define for2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
#define N 2500000
#define MOD ((int)1e9+7)
const string el="n";
const string elel="nn";
const string sp=" ";
const string spsp=" ";
const string tab="t";
int n;
int dp[N],val[N],nu[N];
int sum,big;
void ZeroOne_Pack(int cost,int weight,int n)
{
for(int i=n; i>=cost; i--)
dp[i] = max(dp[i],dp[i-cost] + weight);
}
void Complete_Pack(int cost,int weight,int n)
{
for(int i=cost; i<=n; i++)
dp[i] = max(dp[i],dp[i-cost] + weight);
}
int Multi_Pack(int c[],int w[],int num[],int n,int m)
{
memset(dp,0,sizeof(dp));
for(int i=1; i<=n; i++)
{
if(num[i]*c[i] > m)
Complete_Pack(c[i],w[i],m);
else
{
int k = 1;
while(k < num[i])
{
ZeroOne_Pack(k*c[i],k*w[i],m);
num[i] -= k;
k <<= 1;
}
ZeroOne_Pack(num[i]*c[i],num[i]*w[i],m);
}
}
return dp[m];
}
int main(){
while(scanf("%d",&n),n>=0){
if(n==0){cout<<0<<sp<<0<<el;continue;}
mmm(dp,0);mmm(val,0);mmm(nu,0);sum=0;
for1(i,1,n){
scanf("%d%d",&val[i],&nu[i]);sum+=val[i]*nu[i];
}
big=sum>>1;
Multi_Pack(val,val,nu,n,big);
printf("%d %dn",sum-dp[big],dp[big]);
}
}
//我自己按照题目的架构写了一遍，并且在01包分割的时候保存了物品的原始数量。时间为140MS
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#include<functional>
#define D long long
#define F double
#define MAX 0x7fffffff
#define MIN -0x7fffffff
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define pill pair<int, int>
#define for1(i,a,b) for(int i=a;i<=b;i++)
#define for2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
#define N 125000
#define MOD ((int)1e9+7)
const string el="n";
const string elel="nn";
const string sp=" ";
const string spsp=" ";
const string tab="t";
int n;
int dp[N],val[N],nu[N];
int sum,big;
void Z(int i,int k){//对k件i看成一件01包
for2(j,big,val[i]*k){
dp[j]=max(dp[j],dp[j-k*val[i]]+k*val[i]);//此题cost==weight
}
}
void C(int i){//对i完全包
for1(j,val[i],big){
dp[j]=max(dp[j],dp[j-val[i]]+val[i]);
}
}
void M(){
for1(i,1,n){
if(val[i]*nu[i]>=big)C(i);
else{
int b=1;
while(2*b-1<=nu[i]){
Z(i,b);b<<=1;
}
b>>=1;
if(nu[i]-2*b+1>0)Z(i,nu[i]-2*b+1);
}
}
}
int main()
{
while(scanf("%d",&n),n>=0){
mmm(dp,0);mmm(val,0);mmm(nu,0);sum=0;
for1(i,1,n){
scanf("%d%d",&val[i],&nu[i]);sum+=val[i]*nu[i];
}
big=sum>>1;
M();
printf("%d %dn",sum-dp[big],dp[big]);
}
return 0;
}完全背包优化
最后这个是对于完全包的优化
思路：因为完全包就是不用考虑数量而已，所以你只要对他取一个数量的上限，即最多的可以装的数量（因为dp的for循环是到背包容量为止的，所以这个极限数量就可以看成无限），再按照优化多重包的思想，把这个极限数量用二进制分割，时间就从O(n*k)降到到了O(n*logk)，时间优化为93MS。
代码：
void UPC(int i){//优化完全包
nu[i]=big/val[i]+1;
int b=1;
while(2*b-1<=nu[i]){
Z(i,b);b<<=1;
}
b>>=1;
if(nu[i]-2*b+1>0)Z(i,nu[i]-2*b+1);
} 最后
以上就是默默小刺猬为你收集整理的多重背包及完全背包优化今天大年初一，在这里祝广大love_leraning新年快乐！的全部内容，希望文章能够帮你解决多重背包及完全背包优化今天大年初一，在这里祝广大love_leraning新年快乐！所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复