Acwing 背包问题
背包问题
首先，什么是背包问题？
-
- 给定N个物品和一个容量为V的背包，每个物品有体积和价值两种属性，在一些限制条件下，将一些物品放入背包，使得在不超过背包体积的情况下，能够得到的最大价值。根据不同的限制条件，分为不同类型的背包问题。
1. 0-1背包问题
-
- 给定N个物品和一个容量为V的背包，每个物品有两个属性，分别是它的体积v_i,和它的价值w_i,每件物品只能使用一次，问往背包里放入哪些物品，能够使得物品的总体积不超过背包的容量，且总价值最大。
- 给定N个物品和一个容量为V的背包，每个物品有两个属性，分别是它的体积v_i,和它的价值w_i,每件物品只能使用一次，问往背包里放入哪些物品，能够使得物品的总体积不超过背包的容量，且总价值最大。
f(i,j)可以分为两个更小的集合，一种是不包含第i个物品，一种是包含第i个物品
- 不包含第i个物品：就是从物品
1-i中选择，但是不能包含第i个物品的最大价值，换句话就是从物品1-i-1中选择，总体积不超过j的最大价值，即f(i - 1, j)- 包含第i个物品：就是从物品
1-i中选择，但是必须包含第i个物品的最大价值，那么可以认为最开始直接把i塞进背包，此时背包的容量变成了j - vi，价值变成了wi，由于第i个物品已经装进背包了，那么从1-i选就变成了从1-i-1选了，因此此时的最大价值就是f(i - 1, j - vi) + wi
f(i, j)取两种情况的最大值，因此f(i, j)= max(f(i - 1, j), f(i - 1, j - vi) + wi)
Acwing 2.0-1背包问题
实现思路：求f(i,j)，i从0开始枚举到n件物品，再用j从0开始枚举到最大体积m，由于包含i的集合可能不存在，因此先计算不包含i的集合，即f(i,j)=f(i-1,j)，若当前的状态可以划分包含i的状态，即j>=v[i],那么就计算当前枚举的f(i,j)最终值，即max(f((i-1),j),f(i-1,j-v[i])+w[i]))，当全部枚举结束后，计算的就是f[n][m]，即前n个物品中总体积不超过m的最大价值。
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];//存状态
int main(){
cin >> n >> m;
for(int i = 1 ; i <= n; i ++) cin >> v[i] >> w[i] ;
for(int i = 1; i <= n ; i++){//f[0][j]都默认为0
for(int j = 0 ; j <= m; j ++){//f[i][0]都默认为0
f[i][j] = f[i-1][j];//不包含物品i的情况
if(j >= v[i]) f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]);//包含物品i，直接先放进去
}
}
cout << f[n][m] << endl;
return 0;
}
优化：滚动数组优化为一维
将状态f[i][j]优化到一维f[j],实际上只需要做一个等价变形。
为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，即放前i个物品在体积为j时的最大价值（很多个状态都可以得到），但题目只需要求得最终状态f[n][m]（只要一个状态，不用求那么多状态），因此我们只需要一维的空间来更新状态。
- 状态f[j]定义：N件物品，背包容量j下的最优解（最大价值）；
- 注意枚举背包容量
j必须从m开始，即逆序遍历处理不同体积。
为什么一维情况下枚举背包容量需要逆序？
在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
那我们可以看看不倒序会怎样？
正序更新：
for (int j = v[i]; j <= m; j++) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
倒序更新的好处：为了防止物品被重复选择，我们使用倒序循环，从背包最大容量 m 逐渐递减到 v[i]，这样在更新 f[j] 时，之前的 f[j - v[i]] 是上一轮未更新的旧值，这保证了每个物品只被使用一次。
for (int j = m; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m; // n: 物品数量, m: 背包容量
int v[N], w[N]; // v[i]: 第i个物品的重量, w[i]: 第i个物品的价值
int f[N]; // f[j]: 容量为j时的最大价值
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i];
// 动态规划过程
for (int i = 1; i <= n; i++) {
// 倒序循环，防止物品被重复选择，j逆序，到v[i]为止（小于vi就没意义，装不下vi）
for (int j = m; j >= v[i]; j--) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
2. 完全背包问题
相比0-1背包问题，完全背包问题的各个物品是无限个的，即放入背包的物品i可以不限数量（即可以重复使用i）
Acwing 3.完全背包问题
实现思路：和0-1背包问题的区别在状态计算中的集合划分，不是只有0和1，而是可以选k个
朴素做法：与0-1背包思路相同，只是在集合划分上有所区别，以f[i,j]为例，对其进行下一步划分，考虑以取k个i物品划分集合，若k=0，则相当于f[i-1,j]；若k不等于0，则采取01背包类似的办法，先确定取k个物品i，不影响最终选法的求解，即求f[i-1,j-k*v[i]],再加上k*w[i]，即f[i-1,j-k*v[i]]+k*w[i],不难发现k=0情况可以与之合并，最终就是取从0枚举到k，最终状态转移方程为f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])的最大值，k的最大值可以通过j>=k*v[i]求解。有三重for循环，时间复杂度最差为O(n*m^2)
注意：这里max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])，而不是类似0-1背包那样取max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i])。因为k=0时，即物品i不取的情况，完全背包方程就为max(f[i][j],f[i-1][j])，实质上就涵盖了f[i-1][j]的情况
具体实现代码：
#include <iostream>
#include <alforithm>
using namespace std;
const int N=1010;
int w[N],v[N],f[N][N];
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=0;k*v[i]<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}
但是现在数据加强了，会超时！那就进行优化！
二维优化版：改为二重循环，降低时间复杂度
像0-1背包那样考虑分成两种情况看待，
第一种情况：从i物品一个都不取开始；
第二种情况：从至少取一份i物品开始，即j-v
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
观察上面两式，括号中对应部分只相差一个w，可得出如下递推关系：
f[i][j]=max( f[i-1][j],f[i,j-v]+w )
所以可以去掉k，即去掉第三重循环
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int main(){
cin >> n >> m;
for(int i = 1 ; i <= n ; i ++) cin >> v[i] >> w[i];
for(int i = 1; i <= n ; i ++){
for(int j = 0 ; j <= m ; j ++){
f[i][j] = f[i-1][j];//不取物品i
if(j >= v[i]) f[i][j] = max(f[i][j],f[i][j - v[i]] + w[i]);//至少取一份物品i
}
}
cout << f[n][m] << endl;
return 0;
}
滚动数组优化
观察可以发现可0-1背包的代码很像，所以可以像0-1背包那样用滚动数组优化。
区别在于：第二部分是i-1，还是i，即需要的值是上一轮的i-1还是本轮的i
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包 需要i-1轮的值来更新
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题 需要i轮的值来更新
相比0-1背包，进行滚动优化区别：j是正序遍历处理了（而0-1背包的j是逆序）
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m; // n表示物品数量，m表示背包的最大容量
int v[N], w[N]; // v[i]表示第i个物品的体积，w[i]表示第i个物品的价值
int f[N]; // f[j]表示容量为j时的最大价值
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
// 动态规划求解完全背包问题
for(int i = 1; i <= n; i++) { // 遍历每一个物品
// 完全背包问题：每件物品可以被选择多次，因此体积从小到大遍历
for(int j = v[i]; j <= m; j++) {
// 对于容量为j的背包，判断是否选择第i个物品，取最大价值
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
我们可以发现，完全背包问题和0-1背包问题就是差了一个体积的遍历顺序哦~（背包从小到大，0-1从大到小）
3.多重背包问题
每件物品的个数是不同的，比如，每件物品的个数是si个。
相比完全背包问题，只是每个物品的个数有了上限，不再是无限
Acwing 4.多重背包问题
朴素版本：和完全背包问题基本一样，只是k多了个上限限制，用数组s[]表示某个物品的上限。时间复杂度为O(NVS)，数据量小的情况下可以AC。
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N],w[N],s[N];
int f[N][N];
int n,m;
int main(){
cin >> n >> m;
for(int i = 1 ;i <= n ; i ++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1 ;i <= n ; i ++){
for(int j = 0 ; j <= m ; j ++){
for(int k = 0; k <= s[i] && k * v[i] <= j ; k ++){//多一个上限的判断
f[i][j] = max(f[i][j],f[i-1][j - k * v[i]] + k * w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}
利用二进制拆分将多重背包问题转换为多个01 背包问题，从而将原来的三重循环优化成两重循环。每个物品可以看作若干个不同的物品，这些物品的数量分别为 1, 2, 4, …, 直到总数不超过 s[i]。
Acwing 5.多重背包问题 II
优化步骤：
- 将数量拆分为若干份：每种物品 i 有 s[i] 个，将其数量拆分为若干个 1、2、4、8… 的二进制份数，直到剩下的数量不足再处理。这种拆分方式保证了在所有的数量限制 s[i] 内完成计算，同时减少了重复的计算步骤。
- 01背包的思想：每一份物品数量被视作一次01背包问题来处理，即将这份物品的体积和价值加入到状态转移中；
- 状态转移
-
- 设 f[j] 为背包容量为 j 时，能够获得的最大价值。
-
- 对于物品 i 的第 k 份（二进制拆分后），其体积为 x * v[i]，价值为 x * w[i]，我们需要在背包容量允许的情况下更新状态，即 f[j] = max(f[j], f[j - x * v[i]] + x * w[i])。
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2010;
int v[N], w[N], s[N]; // v[] 存储物品的体积，w[] 存储物品的价值，s[] 存储物品的数量
int f[N]; // f[] 存储当前背包容量对应的最大价值
int n, m;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
// 使用二进制拆分对多重背包进行优化
for (int i = 1; i <= n; i++) {
int count = s[i]; // 当前物品 i 的数量限制
for (int k = 1; count > 0; k = k * 2) { // 通过二进制拆分处理数量
int x = min(k, count); // 每次拆分的数量为 1, 2, 4, 8,... 或不足的部分
count -= x; // 减去这次已经处理的物品数量
// 类似于 01 背包问题的更新方式，倒序更新背包状态
for (int j = m; j >= x * v[i]; j--) {
f[j] = max(f[j], f[j - x * v[i]] + x * w[i]);
}
}
}
cout << f[m] << endl;
return 0;
}
4.分组背包问题
有 N 组物品，每一组中有若干个物品，每一组中至多选择一个。
分组背包问题的思考方式和前面的类似。不同的地方仅仅在于状态转移。
Acwing 9.分组背包问题
分组背包问题的思考方式和前面的类似。不同的地方仅仅在于状态转移。
01背包的状态转移，是枚举第i个物品选或者不选；
完全背包和多重背包，是枚举第i个物品，选0,1,2,3,4,.... 个，无限个或有上限个
而分组背包，枚举的是第i个分组，选哪一个，或者一个都不选
- 这里的体积数组v和价值数组w就要开成二维，表示某一组的某一个物品
- 与01背包思路一致，集合划分为不包含i组，包含i组第1个物品，包含i组第2个物品，…包含i组第k个物品（k表示第i组的物品数量），…，包含第i组最后一个物品。因此若不包含第i组，则f(i,j)=f(i-1,j),若包含第i组第k个物品，则计算方法类似01背包（只是多了一重循环从i组里面选第k个物品），先除去第i组的第k个物品再进行计算的取法不变；
- 分组背包的状态转移方程为：
f[i][j]=max(f[i−1][j],f[i−1][j−v[i][k]]+w[i][k])， 1<k<s[i]。其中 v[i,k] 表示第 i 组中的第 k 个物品的体积，w [ i , k ] 同理。同样可以优化为一维：f[j]=max(f[j],f[j−v[i][k]]+w[i][k])，主要这里更新需要上一组的（和完全背包一样），j要逆序 -
j逆序枚举的最小值是1，不是0-1背包那样的v[i]，因为i组里面的物品各自的体积都无法提前判断，不知道最小值
具体实现代码（详解版）：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int n, m; // n: 物品种类数, m: 背包容量
int v[N][N], w[N][N], s[N]; // v[i][j]: 第 i 种物品的第 j 个子物品的体积, w[i][j]:
//第 i 种物品的第 j 个子物品的价值, s[i]: 第 i 种物品的子物品数量
int f[N]; // 动态规划数组，f[j]: 容量为 j 的背包的最大价值
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> s[i];
for (int j = 0; j < s[i]; j++) {
cin >> v[i][j] >> w[i][j];
}
}
// 动态规划更新过程
for (int i = 1; i <= n; i++) { // 遍历每种物品
for (int j = m; j >= 0; j--) { // 从背包容量 m 开始逆序遍历到 0
for (int k = 0; k < s[i]; k++) { // 遍历当前物品组的每个子物品
if (v[i][k] <= j) { // 判断当前子物品的体积是否可以放入背包
// 更新最大价值：选择放入或不放入当前子物品
f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
}
}
}
}
cout << f[m] << endl;
return 0;
}
以上就是各种背包问题，要学会分析状态表示和状态计算，推导出状态转移公式（这是关键）！