文章目录
概要说明
本文讲多重背包、混合背包以及二维费用背包，至于其他背包问题后续补充
01背包和完全背包问题：传送门
多重背包(朴素算法)
模板例题
思路
多重背包也是 0-1 背包的一个变式，与 0-1 背包的区别在于每种物品有 k 个，而非一个
那么我们可以在01背包的基础上，多加上一重循环，让循环遍量k从1开始循环，循环到总重W即可
code
void solve(){
int n,W;
cin >> n >> W;
for(int i=1;i<=n;++i){
cin >> w[i] >> v[i] >> s[i];
}
for(int i=1;i<=n;++i)
for(int j=W;j>=w[i];--j)
for(int k=1;k*w[i]<=j && k<=s[i];++k){
f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);
}
cout << f[W];
return ;
}
很明显，这个代码的时间复杂度为
O
（
n
W
k
）
O（nWk）
O（nWk）
当数据过大时，这个代码很容易超时
因此我们也就衍生出了二进制优化多重背包的算法
多重背包（二进制优化）
模板例题
思路
我们首先确认三点：
- 我们知道转化成01背包的基本思路就是：判断每件物品我是取了你好呢还是不取你好。
- 我们知道任意一个实数可以由二进制数来表示，也就是 2 0 2 k 2^0 2^k 202k其中一项或几项的和
- 这里多重背包问的就是每件物品取多少件可以获得最大价值
为什么可以进行二进制优化，我们拿苹果进行举例：
比如苹果总数为50，如果我们一个个拿，需要拿50次
假设说这时候有6个箱子，这6个箱子的容量为
1
,
2
,
4
,
8
,
16
,
19
1,2,4,8,16,19
1,2,4,8,16,19(为什么有19呢，因为剩下的总数不够32，所以将剩余的苹果单独拎出来)
那么我们就可以将这50个苹果分别装在这6个箱子里面，是不是比朴素的算法快很多？
二进制优化多重背包本质上就是将个数进行拆分，由于每个数都能用二进制数来表示，所以它的时间复杂度可以降低到
O
(
n
W
l
o
g
2
s
)
O(nWlog_2s)
O(nWlog2s)
基于上述思想，我们只需要将每次拆分的物品个数和价值存入到数组中，最后套用01背包的模板即可
code
const int N=1e4+1010,M=2e3+5;
int v[N],w[N],f[M];
void solve(){
int n,W;
cin >> n >> W;
int cnt=1;//统计数量
for(int i=1;i<=n;++i){
int a,b,s;
cin >> a >> b >> s;
for(int j=1;j<=s;j<<=1){
w[cnt]=j*a;//存入重量
v[cnt++]=j*b;//存入价值
s-=j;//总个数减去二进制的个数
}
if(s){//若还有剩余
w[cnt]=s*a;
v[cnt++]=s*b;
}
}
for(int i=1;i<cnt;++i) //01背包的模板
for(int j=W;j>=w[i];--j){
f[j]=max(f[j],f[j-w[i]]+v[i]);
}
cout << f[W];
return ;
}
二进制优化是将个数进行拆分，那么我们有没有其他更快的方法呢？
答案是有的：我们可以将体积进行拆分
多重背包(队列优化)
模板例题
思路
我们先来看一串数据：
从第二个物品开始，每个物品的价值跟物品的重量w有关系
就拿
f
[
9
]
来说，跟他有关的是
f
[
7
]
、
f
[
5
]
、
f
[
3
]
f[9]来说，跟他有关的是f[7]、f[5]、f[3]
f[9]来说，跟他有关的是f[7]、f[5]、f[3]，这不是跟物品重量为2有很大关系吗，每次都相差物品重量的k倍关系
为什么没有1呢，因为我们可选的数量为3，
2
∗
3
=
6
,
而
9
>
6
2*3=6,而9>6
2∗3=6,而9>6，说明9不可能由1转换而来，这时候队首的1就需要出队
那么我们就可以考虑用滑动窗口的思想来解决队首和队尾的问题
不了解滑动窗口可以先看这篇博客：传送门
首先定义两个指针hh(队首)，tt(队尾)
然后开3个数组
q
，
f
，
g
，
q
数组用于存下标，
f
数组存答案，
g
数组表示的是
f
数组每次转移的状态
q，f，g，q数组用于存下标，f数组存答案，g数组表示的是f数组每次转移的状态
q，f，g，q数组用于存下标，f数组存答案，g数组表示的是f数组每次转移的状态
当队首大于队尾时，说明队尾为空，不执行任何操作
若不为空，则需要判断当前重量k是否超出范围(个数s
∗
*
∗重量w),超出则需要将队首出队
接着判断**当前状态f[k]**是否比队首的状态(
g
[
q
[
h
h
]
]
)
+
(
k
−
q
[
h
h
]
)
/
w
∗
v
)
g[q[hh]])+(k-q[hh])/w*v)
g[q[hh]])+(k−q[hh])/w∗v)
k
−
q
[
h
h
]
代表剩余的体积，然后除以体积
w
乘上价值
v
k-q[hh]代表剩余的体积，然后除以体积w乘上价值v
k−q[hh]代表剩余的体积，然后除以体积w乘上价值v
然后判断当前状态
g
[
k
]
g[k]
g[k]是否比队尾元素大，若为真则将他们一一排除
然后将当前元素存入q数组中
每次循环都需要将f的状态转移为g数组，因此我们需要用到memcpy函数
看的不是很明白？接下来看代码慢慢食用
int q[N],g[N],f[N];
void solve(){
int n,W;
cin >> n >> W;
for(int i=1;i<=n;++i){
memcpy(g,f,sizeof f);//状态转移
int w,v,s;
cin >> w >> v >> s;
for(int j=0;j<w;++j){
int hh=0,tt=-1;//队首和队尾的指针
for(int k=j;k<=W;k+=w){//每次都相差w倍的关系
if(hh<=tt && q[hh]<k-s*w) hh++;//判断队首是否需要出队
if(hh<=tt) f[k]=max(g[k],g[q[hh]]+(k-q[hh])/w*v);//判断当前状态和队首状态加上新的价值哪个更大
while(hh<=tt && g[k]>=g[q[tt]]+(k-q[tt])/w*v) tt--;//判断当前状态是否比队尾的价值更大，更大的话将他们一一排出
q[++tt]=k;//入队
}
}
}
cout << f[W];
return ;
}
混合背包
模板例题
思路
这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了
我们可以将他们分为两类：
- 完全背包
- 多重背包(01背包相当于k为1)
那么我们只需要分别处理上面两种类型即可
遇上完全背包就套完全背包的模板，遇上01背包和多重背包就套多重背包的模板
（注意：多重背包的朴素算法会超时，因此我们在这里考虑用二进制优化和队列优化的方法来做）
接下来看代码：
code1
int f[N];
void solve(){
int n,W;
cin >> n >> W;
for(int i=1;i<=n;++i){
int w,v,s;
cin >> w >> v >> s;
if(s==0){//完全背包
for(int j=w;j<=W;++j){
f[j]=max(f[j],f[j-w]+v);
}
}
else{
if(s==-1) s=1;//01背包转换多重背包
for(int k=1;k<=s;k<<=1){//二进制优化
for(int j=W;j>=k*w;--j){
f[j]=max(f[j],f[j-k*w]+k*v);//直接进行循环，比较大小
}
s-=k;//减去个数
}
if(s){
for(int j=W;j>=s*w;--j){
f[j]=max(f[j],f[j-s*w]+s*v);
}
}
}
}
cout << f[W];
return ;
}
如果套队列优化的多重背包的模板，实际上不需要分完全背包和多重背包
我们只需要将背包个数s设置为无穷大，这样每次都不会将队首出队，相当于无限放入物品（即完全背包）
code2
int q[N],f[N],g[N];
void solve(){
int n,W;
cin >> n >> W;
for(int i=1;i<=n;++i){
memcpy(g,f,sizeof f);
int w,v,s;
cin >> w >> v >> s;
if(s==-1) s=1;
if(s==0) s=1e6;
for(int j=0;j<w;++j){
int hh=0,tt=-1;
for(int k=j;k<=W;k+=w){
if(hh<=tt && q[hh]<k-s*w) hh++;
if(hh<=tt) f[k]=max(g[k],g[q[hh]]+(k-q[hh])/w*v);
while(hh<=tt && g[k]>=g[q[tt]]+(k-q[tt])/w*v) tt--;
q[++tt]=k;
}
}
}
cout << f[W];
return ;
}
二维费用背包
模板例题
思路
这种题型很明显是 0-1 背包问题的变形，可是不同的是选一个物品会消耗两种价值（容量、重量），只需在状态中增加一维存放第二种价值即可。
注意：开三维存放物品编号就不合适了，因为容易 MLE，我们可以像01背包一样，将三维压缩成二维
code
int f[105][105];
void solve(){
int n,W,M;
cin >> n >> W >> M;
for(int i=1;i<=n;++i){
int w,m,v;
cin >> w >> m >> v;
for(int j=W;j>=w;--j)//和01背包一样，倒着遍历
for(int k=M;k>=m;--k){
f[j][k]=max(f[j][k],f[j-w][k-m]+v);//相当于滚动数组，每次都在原来的状态进行新状态的转移
}
}
cout << f[W][M];
return ;
}