当前位置：首页 > news >正文

背包进一步（多重背包、混合背包）

news 2025/7/30 12:18:28

卫士不语功，唯时代尔
持光不畏暗，无而蔽安

背包进一步（多重背包、混合背包）

前情提要背包初步（0-1背包、完全背包）-CSDN博客

多重背包

多重背包问题，相比于完全背包，他的每个物品不像完全背包一样可以无限使用，而是有各自的数量限制；

朴素算法

4. 多重背包问题 I - AcWing题库

可以转化为01背包问题：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为∑n[i]的01背包问题，直接求解；复杂度是O(V*∑n[i])。

多了一层k的循环，来枚举每件物品的选取的数量；

for(int i=1;i<=n;i++)
for(int j=v;j>=a[i];j--)
for(int k=1;k<=n[i]&&k*a[i]<=j;k++)
dp[j]=max(dp[j],dp[j-k*a[i]]+k*b[i]);

二进制优化（倍增思想拆分）

5. 多重背包问题 II - AcWing题库

假设有50个苹果，现在要取n个苹果 $(n⩽50)(n\leqslant50)$ ,如何取？

朴素的做法

应该是将苹果一个一个拿出来，直到n个苹果被取出来。

再假设有50个苹果和6只箱子，利用箱子进行某些预备工作，可以在每个箱子中放 $2k(k⩾0){2}^{\mathrm{k} }(k\geqslant 0)$ 个苹果 , 也就是 1、 2、4、8、16、19（剩余的数 ) , 取任意n个苹果时 , 只要推出几只箱子就可以了。（这里用到的就是倍增思想，可以证明，这样子分组能拼凑出50以内的任何一个数（很经典的砝码问题），具体证明可以看巴协（Bachet）砝码问题）；

二进制拆分思想（拆分的是每个物品的数量s）

所以整体的思想其实就是先把已有的物品（按倍增思想）分好组，转换成了若干新的物品，在对这些新的物品去01背包求解就行了！

将第i种物品拆分成若干件物品，每件物品的体积和价值乘以一个拆分系数( $2^1, 2^2. . . 2^{\mathrm{k- 1}}, s_i$ - $2^k$ + 1),转化成01背包的物品求解。

例如，si=12,拆分系数为1,2,4,5,转化成4件01背包的物品： $v_{i}$ , $w_{i}$ ) , $2_{\mathrm{v_{i}} }, 2_{\mathrm{w_{i}} }) , ( 4_{\mathrm{v_{i}} }, 4_{\mathrm{w_{i}} }) , ( 5_{\mathrm{v_{i}} }, 5_{\mathrm{w_{i}} })$

这样时间复杂度就能降低到 $O(mΣlogsi)O(m\Sigma logs_i)$ ；大大加快！

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int a[N],b[N],dp[N];
void slove(){int n,v;cin>>n>>m;int nn=1; /// 记录拆分后物品的数量for(int i=1;i<=n;i++){int v,w,s;cin>>v>>w>>s;for(int j=1;j<=s;j<<=1){ /// 二进制拆分a[nn]=j*v;b[nn]=j*w;nn++;s-=j;}if(s){ /// 如果有剩余a[nn]=s*v;b[nn]=s*w;nn++;}}for(int i=1;i<nn;i++){ /// 直接套用01背包for(int j=m;j>=a[i];j--)dp[j]=max(dp[j],dp[j-a[i]]+b[i]);}cout<<dp[m];
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

单调队列优化

6. 多重背包问题 III - AcWing题库

单调队列优化用到的也是拆分思想，和二进制拆分不同的是，他拆分的是背包的总容量m；

举个例子：

比如一件物品的v=3，w=5，s=3；背包的总容量m=10；

按照朴素的做法，我们观察他的状态转移，我们会去循环选取的物品的数量k。所以选取的物品的总体积为k*v；

所以我们在倒序遍历的时候，比如遍历到了dp[9]受到的影响肯定和前面的k*v有关系，也就是dp[6],dp[3],dp[0]；

到dp[10]的时候，会和前面的dp[7],dp[4],dp[1]的时候有关；

我们就能发现，更新的时候的能影响当前状态的dp的差值一定是当前物品体积v的整数倍！（_{物品是一个一个放的所以肯定是整数倍}）

所以我们可以发现 $dp\mathbf{dp}$ 数组是按类更新的，可以把 $dp[0.....m]\mathbf{dp}[0.....m]$ 按每个物品的体积 $v\mathbf{v}$ 的余数拆分成 $v\mathbf{v}$ 个类。

$dp[0],dp[v],dp[2v],…,dp[kv];\mathbf{dp}[0],\mathbf{dp}[v],\mathbf{dp}[2v],\dots,\mathbf{dp}[kv];$

$dp[1],dp[1+v],dp[1+2v],…,dp[1+kv];\mathbf{dp}[1],\mathbf{dp}[1+v],\mathbf{dp}[1+2v],\dots,\mathbf{dp}[1+kv];$

$dp[2],dp[2+v],dp[2+2v],…,dp[2+kv];\mathbf{dp}[2],\mathbf{dp}[2+v],\mathbf{dp}[2+2v],\dots,\mathbf{dp}[2+kv];$

$dp[j],dp[j+v],dp[j+2v],…,dp[j+kv];\mathbf{dp}[j],\mathbf{dp}[j+v],\mathbf{dp}[j+2v],\dots,\mathbf{dp}[j+kv];$

其中 $j$ 是 $v\mathbf{v}$ 的余数， $0 <= j <= v - 1$ 。例如v=2的时候：

$dp[0],dp[2],dp[4],dp[6],dp[8];\mathbf{dp}[0],\mathbf{dp}[2],\mathbf{dp}[4],\mathbf{dp}[6],\mathbf{dp}[8];$

$dp[1],dp[3],dp[5],dp[7],dp[9]。\mathbf{dp}[1],\mathbf{dp}[3],\mathbf{dp}[5],\mathbf{dp}[7],\mathbf{dp}[9]。$

所以我们可以发现

dp[j]是由前面不超过数量s的同类值递推得到的。（因为物品的数量只有s件）

这就相当于从前面宽度为s的窗口挑选最大值来更新当前值。

所以，我们用单调队列来维护窗口最大值，从而把更新dp[j]的次数缩减为1次。

这就需要顺序更新f值，怎么办呢？只需要增加一个备份数组g即可！

我们先来队朴素做法进行小更改；

for(int i=1;i<=n;i++){memcpy(g,dp,sizeof dp);int v,w,s;cin>>v>>w>>s;for(int j=v;j>=a[i];j--){for(int k=1;k<=s&&k*v<=j;k++){dp[j]=max(g[j],g[j-k*v]+k*w);}}
}

现在要做的就是将里面的两个内循环换成单调队列的方法去实现，进而去压缩时间；

1.检查队头合法性，把小于 $k - s \times v$ 的下标出队。

2.取队头为最优决策，更新 $d p [k]$ 。

3.把新下标 $k$ 插入队尾，入队前检查队尾单调性，排除无用决策。

注意：根据上面的分析，dp[k]是通过前面的旧值g[q[l]]更新的，所以我们的窗口是在g数组上滑动的；我们直接套用单调队列(滑动窗口)的模板即可！单调队列的队头存的是当前区间的最大值；

和模板一样里面数组q模拟队列存的是下标，q[l]就是区间内已经dp的值（也就是g的值，因为复制了）的下标，(k-q[l])/v就是对这个物品选取的数量，所以(k-q[l])/v*w就是提供的价值；直接用stl里的队列也可以；

for(int i=1;i<=n;i++){memcpy(g,dp,sizeof dp); /// 备份一下int v,w,s;cin>>v>>w>>s;for(int j=0;j<v;j++){ /// 分成v类(就是上面说的按余数分的类，这个j就是枚举的余数)int l=0,r=-1;for(int k=j;k<=m;k+=v){ /// 分别对每一类进行单调队列while(l<=r&&q[l]<k-s*v) l++; /// 队首不在队中就弹出if(l<=r) /// 每次都选用队头的最大值更新dp数组dp[k]=max(g[k],g[q[l]]+(k-q[l])/v*w);while(l<=r&&g[k]>=g[q[r]]+(k-q[r])/v*w) r--; /// 当前价值比队尾大就把队尾弹出q[++r]=k; /// 当前下标入队}}
}

内层循环控制f[0…m]进队出队各一次，次数为O(m),外层循环次数为n，所以时间复杂度为O(mn)；

整个算法的时间复杂度为 O(NM)！真是天雷滚滚，妙不可言；

多重背包时间复杂度:

朴素算法: $\Sigma s_i)$

二进制优化: $\Sigma \log s_i)$

单调队列优化: $O (mn)$

两种优化方法都应用了拆分思想，

二进制优化拆分的是物品数量s，s件拆分成log(s)件；

单调队列优化拆分的是背包容量m，根据v的余数，把dp[0…m]拆分成v个类，使dp[0…m]在O(m)内完成更新。

混合背包

7. 混合背包问题 - AcWing题库

如果将前面学的三种背包混合起来。也就是说，有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。应该怎么求解呢？

这种题目看起来很吓人，可是只要领悟了前面几种背包的中心思想，并将其合并在一起就可以了。

整体可以看做

for (循环物品种类) {if (是 0 - 1 背包)套用 0 - 1 背包代码;else if (是完全背包)套用完全背包代码;else if (是多重背包)套用多重背包代码;
}

二进制优化的写法

因为有多重背包的参与，所以我们依然可以进行去优化，比如用二进制优化转换成01背包；这样就是两类背包和混合了；

分类处理的思想：

1.利用多重背包的二进制优化，可以先将多重背包转化为多个01背包。

2.用a，b,c三个数组来记录转化之后的所有
背包的体积、价值、类型，c[i]==0表示完全背包，c[i]=1表示01背包。

3.最后做一遍，以c的值分为两类，做完全背包，和01背包。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int a[N],b[N],c[N];
int dp[N];
void slove(){int nn,m;cin>>nn>>m;int n=1;for(int i=1;i<=nn;i++){int v,w,s;cin>>v>>w>>s;if(s==0){a[n]=v;b[n]=w;c[n]=0;n++;}else{if(s==-1)s=1;for(int j=1;j<=s;j<<=1){a[n]=j*v;b[n]=j*w;c[n]=1;s-=j;n++;}if(s){a[n]=s*v;b[n]=s*w;c[n]=1;n++;}}}for(int i=1;i<n;i++){if(c[i]){for(int j=m;j>=a[i];j--)dp[j]=max(dp[j],dp[j-a[i]]+b[i]);}else{for(int j=a[i];j<=m;j++)dp[j]=max(dp[j],dp[j-a[i]]+b[i]);}}cout<<dp[m]<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

单调队列优化的写法

当然我们也可以采取队列优化的多重背包的模板

这样我们就不需要分完全背包和多重背包

我们只需要将完全背包中的个数s设置为无穷大，这样每次都不会将队首出队，相当于无限放入物品

这样做只用套用一个队列优化的多重背包模板，更加简洁！

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int inf=0x3f3f3f3f;
const int N=1e5+5;
int dp[N],g[N],q[N];
void slove(){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){memcpy(g,dp,sizeof dp);int v,w,s;cin>>v>>w>>s;if(s==-1) s=1;if(s==0) s=inf;for(int j=0;j<v;j++){int l=0,r=-1;for(int k=j;k<=m;k+=v){while(l<=r&&q[l]<k-s*v) l++;if(l<=r)dp[k]=max(g[k],g[q[l]]+(k-q[l])/v*w);while(l<=r&&g[k]>=g[q[r]]+(k-q[r])/v*w) r--;q[++r]=k;}}}cout<<dp[m]<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}