title: "01背包详解"
author: Sun-Wind
date: October 27, 2021
本贴背景：蒟蒻突然被要求去讲题.............
什么是01背包
0-1 背包问题：给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi 。
问：应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
在上述例子中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的0和1，这类问题便被称为「0-1 背包问题」。
0-1背包问题实质上是一个动态规划问题，解决这个问题我们需要从前一个状态递推到下一个状态，最终递推到我们想要的状态
递推函数
考虑这样一个函数B(n,c)
这个函数表示从n个物品里面选择物品，背包容量为c所能达到的最大价值
既然是动态规划的问题，我们应该从上一个状态寻求思路，找寻两个状态之间的联系
状态转换
试想一下，假如我们需要从4个物品里面选择物品，我们应该先考虑前3个物品的状态，然后再考虑第4个物品是放还是不放
利用二进制的思想，如果四个物品都不放我们用状态表示为0000
都放用状态表示为1111，其他的状态可以类比推理
显然，要想得到最优解，对应这个最优解的状态就一定是0000~1111其中的一种
细节思考
假如，我们知道放前三个物品所对应的最优解是101，也就是取第1件和第3件，第2件不选，这样选让目前的背包能达到最大的价值
现在考虑第四件，第四件我们知道要么选要么就不选
如果要选第4件物品，并且这时候背包还能放第4件物品，那么显然我们应该把这件物品放入背包中
当然存在另外的一种矛盾的情况，就是这个时候背包的容量已经不够了，有些物品已经占据了背包的格子，但是把这些物品拿出来放第4个物品的价值反而要更大
就是说如果考虑第4件物品最好的状态可能是1001，0011，甚至可能是0001
如下图所示
当然，如果不拿这第4个物品的价值更大，那最优解当然是不拿
既然这样，我们的递推方程就可以自然地得出
B(n,c) = max(B(n-1,c),B(n-1,c-w) + v)
其中w指的是这个物品的体积，v指的是这个物品的价值。在之前的例子中指的是第4个物品的体积和价值
也就是说前面的某个物品可能会多>=w的容量
我们把之前的物品拿出来，然后放入现在考虑的物品，就像之前所讨论的物品4一样
核心代码
根据上述的推论，我们可以得到如下的代码
for(i = 1; i <= m; ++i)//枚举个数
for(j = 1; j <= n; ++j)//枚举容量
{
if(w[i] <= j)//如果能放
dp[i][j] = max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i]);
else//上一个物品的状态
dp[i][j] = dp[i - 1][j];
}
注意一点，这里在考虑每一个物品时我们列举了背包的每一份容量考虑，目的是保证考虑到每一个状态
这里的dp数组模拟的就是上述的B(n,c)函数
时间复杂度为O(NV)
例题讲解1
hdu2602
题目翻译
很多年前，在泰迪的故乡有一个被称为“骨头收集者”的人。这个男人喜欢收集各种各样的骨头，如狗，牛，鸟......
骨收集器有一个很大的袋子，沿着他收集的旅行有很多骨骼，显然，不同的骨骼有不同的价值和不同的体积，现在给出了每次骨头的价值和体积，你可以计算骨收集器可以获得的总价值的最大值最多？
输入
第一行包含整数T，案例的数量。
其次是T例，每种情况三行，第一行包含两个整数n，v，（n <= 1000，v <= 1000）表示骨骼的数量和他袋子的体积。第二行包含表示每个骨骼体积的n个整数。第三行包含表示每个骨骼的价值的n个整数。
输入
1
5 10
1 2 3 4 5
5 4 3 2 1
输出
14
显然，这是一道01背包的板子题，我们直接套上我们的核心代码就可以解决
代码如下
#include<iostream>
using namespace std;
const int N = 1e3+5;
int dp[N][N];//表示B函数
int w[N];//表示体积
int v[N];//表示价值
int n,m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 0; j <= m; ++j)
dp[i][j] = 0; //每一次要重新把数组更新为初始状态，防止被上一个样例影响
//输入
for(int i = 1; i <= n; ++i)
cin >> v[i];
for(int i = 1; i <= n; ++i)
cin >> w[i];
//核心代码
for(int i = 1; i <= n; ++i)
for(int j = 0;j <= m;j++)
if(j >= w[i])
dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);
else
dp[i][j] = dp[i-1][j];
cout << dp[n][m] << endl;//最后的结果，即递推到最后的状态是考虑n个物品，背包容量为m时能得到的最大价值
}
return 0;
}
01背包空间复杂度的优化
刚刚我们从二维的角度来思考B(n,c)函数，空间复杂度为O(nv),现在我们尝试把空间复杂度降到O(v)
这时我们的B函数只有一个参数C(背包的容量)
也就是说我们在每次遍历时，背包里面刚开始存的是上一个状态的，核心代码变成了这样
for(i = 1; i <= m; ++i)//枚举个数
for(j = w[i]; j <= n; ++j)//枚举容量
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
像我们之前的思考那样
如果j < w[i] 之前是dp[i][j] = dp[i-1][j]
这里就不考虑dp[j],所以dp[j]将保存上一次的状态，等价于上述的式子
如果j >= w[i],之前是dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);
现在是dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
两者都是在考虑i-1个物品时容量为j的最大价值和上一状态要把这个物品放进去这两个状态之间
得到的最大价值
既然都是等价的，理论上我们应该可以直接套用这个新的板子，而且还省了一点代码
细节思考
其实依然存在一些问题，等价但不完全等价，关键点在于循环顺序
试着考虑这样的一个问题，我们考虑j状态和2j状态
j状态的所面临的问题
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
2j状态所面临的问题
dp[2j] = max(dp[2j],dp[2j-w[i]] + v[i]);
当j=w[i]时我们可以看到
dp[j] = max(dp[j],dp[0] + v[i]);
dp[2j] = max(dp[2j],dp[j] + v[i]);
对于同一个物品，在循环到j=w[i]和2j时都要考虑放与不放的问题
所以我们可能在dp[j]时已经把这个物品放进去了，但是在dp[2j]时我们又放了一次
这就违背了题目中每个物品只有一件的题意
问题出在哪里？
理论上难道不是等价的吗
其实我们可以发现dp[2j] = max(dp[2j],dp[j] + v[i]);这里的dp[j]如果已经被更新过（也就是已经被放进去过一次了）那么它保存的就是这个状态，而不是上一个状态
真正的优化
所以我们重新考虑循环的顺序，我们采用倒序循环，也就是
for(i = 1; i <= m; ++i)//枚举个数
for(j = n; j >= w[i]; --j)//枚举容量
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
显然，这样我们就可以保证max中比较的状态都是上一个状态
空间优化迎刃而解
优化过后的代码
#include<iostream>
using namespace std;
const int N = 1e3+5;
int dp[N];//表示B函数
int w[N];//表示体积
int v[N];//表示价值
int n,m;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
cin >> n >> m;
for(int i = 0; i <= m; ++i)
dp[i] = 0; //每一次要重新把数组更新为初始状态，防止被上一个样例影响
//输入
for(int i = 1; i <= n; ++i)
cin >> v[i];
for(int i = 1; i <= n; ++i)
cin >> w[i];
//核心代码
for(int i = 1; i <= n; ++i)
for(int j = m;j >= w[i];--j)
dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
cout << dp[m] << endl;//最后的结果，即递推到最后的状态是考虑n个物品，背包容量为m时能得到的最大价值
}
return 0;
}
背景：之所以要写扩展是害怕到时候没到下课就把上面讲完了
01背包扩展之完全背包
什么是完全背包
完全背包问题：和01背包大致类似，唯一不一样的是每个物品不是只有一件了，而是有无限多件了，这时候问你背包所能获得的最大价值是多少
思路解析
既然很多地方都和01背包一样，那么我们可以从01背包中来获取思路
我们发现无限多件物品其实就等价于可以重复地放这个物品
想到什么了没
我们在讨论01背包问题的时候，其中就考虑了重复放置物品的问题
for(i = 1; i <= m; ++i)//枚举个数
for(j = w[i]; j <= n; ++j)//枚举容量
dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
还记得我们最初优化的那个错误的代码吗，没错，它讨论的就是完全背包的问题，每个物品可以重复的放在背包当中
所以其实我们在讨论01背包时已经顺带解决了完全背包的问题，上述代码就是完全背包的核心代码
例题讲解2
洛谷P1616
题目大意
一个人有m的时间采n种药，每种药可以无限次采摘，问在规定时间内所能采得药物得最大价值
输入
70 3
71 100
69 1
1 2
输出
140
这是一道完全背包的板子题
在题目中，时间相当于背包，药物相当于物品
#include<iostream>
using namespace std;
const int N = 1e7+5;
long long dp[N];
int w[10005],v[10005];
int main()
{
int n,m;
cin >> m >> n;
for(int i = 1; i <= n; ++i)
cin >> w[i] >> v[i];
for(int i = 1; i <= n; ++i)
for(int j = w[i]; j <= m; ++j)
dp[j] = max(dp[j],dp[j-w[i]] + v[i]);//这一段核心代码和之前解释的一样
cout << dp[m] << endl;
}
01背包扩展之多重背包
什么是多重背包
多重背包也是 0-1 背包的一个变式。与 0-1 背包的区别在于每种物品有ki个，而非一个,也不是无穷多个
多重背包和01背包，完全背包都不相同，关键在于它的每个物品都有上限
朴素做法
考虑一个朴素的做法，既然总的物品有数量限制，假设物品的数量和为sum
那么问题就转化为有sum个物品，每个物品只有一件的01背包问题
转化之后的代码
for(int i = 1; i <= sum; ++i)
for(int j = b; j >= w[i]; --j)
dp[j] = max(dp[j],dp[j - w[i]] + m);
时间复杂度为O(sum*V)
例题讲解3
Acwing4
此题是完全背包的模板题，上述解释看懂了应该就没有什么问题
#include<iostream>
using namespace std;
int w[105],v[105];
int dp[105];
int main()
{
int a,b;
cin >> a >> b;
while(a--)
{
int n,m,s;
cin >> n >> m >> s;
for(int i = 1; i <= s; ++i)//分割为01背包问题
for(int j = b; j >= n; --j)
dp[j] = max(dp[j],dp[j - n] + m);
}
cout << dp[b] << endl;
}
这是第一版的01背包
后续还有完全背包的二进制优化，分组背包和混合背包问题
有兴趣的同学可以看一下
如果支持过5，可以考虑写第二版
好吧，今天的分享就到这里，创作不易，感谢大家的支持