【蓝桥杯速成】| 6.背包问题(01版)
01 背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
接下来让我们从题目入手，看看这个背包到底是怎么个事
题目：携带研究材料
问题描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的空间，并且具有不同的价值。
小明的行李空间为 N，物品种类为M，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料只能选择一次，并且只有选与不选两种选择，不能进行切割。
解题思路
二维数组版
第一次看到背包问题，我的想法是：从N开始，放一个东西进去就减对应空间，加上相应价值，每次放需要对所有物品做一次尝试，确定是最合适的再放进去，但总觉得这样想好像有漏洞，没有办法同时考虑到空间和价值，也不知道如何组织代码，但其实这个想法就比较趋近于暴力解法，一共就这么多种物品，每个只有选与不选两种情况，根据排列组合的原则，我们实际上也能得到答案，就是时间复杂度为O(2^n)，非常低效的代码呢
但明确背包问题实际上是动态规划中的一类题目，那么它的每一个状态必然是和之前的状态相关的（或许是直接取之前的状态，或许是利用前一状态再加上些什么）
我们仍然可以从动态规划五部曲着手，慢慢思考：
1.确定dp数组含义
因为题目涉及到两个变量：背包空间和物品价值，
那么我们完全可以用一个二维数组对这两个变量进行同时考虑
dp[ i ][ j ] i 表示物品，j 表示背包
物品有序号，价值，占用空间 3个属性，背包则只有背包容量一种属性
那么很显然，让j代表背包空间，那么i 具体表示什么呢？
我们最后要得到的一定是：装入背包里物品价值的最大总和，即dp [ M ][ N ]是价值
这个结果一点是从前状态延续过来的，那么结合之前做的走方格之类 题目中的二维图，
不难想到 i 具体来说应该表示：在 0~i 中，任取物品
所以我们再明确一下
vector<vector<int>> dp(M,vector<int>(N+1))
//从下标为[0-i]的物品里任意取，放进容量为j的背包，最大价值总和
2.确定遍历顺序
对 i 来说，那肯定是从0号到M-1号待选物品
对 j 来说，就是0到N的背包容量大小
for(int i=0;i<M;i++){
for(int j=0;j<=N;j++){
but 请注意我们还没有初始化，所以这个遍历开始值应该待定，
等我们做完初始化再来修改一下！
3.确定递推公式
dp [ i ][ j ] 走到这一格，我们就有两个选择，选i号物品和不选i号物品
和不同路径中，是从上面走下来还是左边走过来一个意思
那么选和不选肯定就是两种方案，我们的dp要取最大值
dp [ i ][ j ] =max(选,不选)
不选i号物品，那么最大值肯定延续之前的取值 dp [ i-1 ][ j ]
选择i号物品，那么需要腾够位置，再加上这一个物品的价值 dp [ i-1 ][ j - weight[ i ] ]+value[ i ]
整合一下就是
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
4.初始化
考虑带0的dp[ i ][ 0 ]，不管你有啥宝贝，咱背包没位置啥也不能装了嘛，
所以第一列应该全部初始化为0
for(int i=0;i<M;i++){
dp[i][0]=0;
}
列考虑完再想想行，第一行，对于0号物品，only one的情况下，应该可以直接给出dp值
能放进来，那这个背包就值这么多，
for(int j=weight[0];j<=N;j++){//从能放进来开始
dp[0][j]=value[0];//后续就这个价值
}
ok，还记得遍历顺序需要改一下不？
结合之前经验，为了使每一格都能被推导出来，
我们的遍历顺序和初始化要打好配合，不能有漏洞，不然肯定会崩溃
从递推关系来看，我们推导每一个dp依靠的是上面一格和左上方的一格（看情况，并不确定，但方位绝对是）初始化已经对第一行第一列赋值，形成了半包围结构，
那么我们的i就从1开始，j从0开始即可，
那么外层循环和内层循环能否调换一下位置呢？
这里是可以的，因为这个半包围结构非常贴心的屏蔽了出错因素，
不会使我们在先遍历行，或者先遍历列的时候出现前面的元素还没填上的情况
此外，还可以在内循环里再加上
if (j < weight[i]) dp[i][j] = dp[i - 1][j];// 放不进来不要逞强那么完整代码在下面可以看到哦
因为递推我们只是在某一格的时候需要使用先前的状态，但先前状态并不需要保留，
所以这个二维数组能否压缩变为一维数组呢？
答案是：当然可以啦！
接下来我们研究一下
一维数组版（滚动数组）
还是执行动态规划五部曲
1.确定dp数组含义
dp[ j ]就指的是背包容量为 j 时的最大价值
这个值会在遍历每一个物品时进行更新
2.确定递推公式
参照二维dp的推理
dp[ j ]=max(dp[j],dp[j-weight[i]]+value[i])
就只是除掉 i ,不把它体现在dp数组的索引上，改用的值还是用
dp[j]就是指不把第 i 个值放进去，那么保持不动
dp[j-weight[i]]+value[i]就是指放入第 i 个值，那么dp值应该发生改变
但是最后我们取最大值，故dp[ j ]要使用max函数在两个方案中选择最大的那一个
3.初始化
这里我们只需要确定dp[0]=0,背包没空肯定没价值啦
剩下的也可以一起初始化为0，只要不是一个其它正数值
因为其他值可以从dp[0]=0开始逐个往后推算得到，
如果初始化为一个正数值，不能确保在max函数选择时它不会脱颖而出
所以保险起见，全部为0是没有风险的
4.确定遍历顺序
同样，我们要用一层循环来遍历物品，一层循环遍历背包容量
根据二维数组的经验，应该写为
for(int i=0;i<M;i++){//遍历物品
for(int j=0;j<=N;j++){//遍历背包
但是这样在一维数组中同样可行吗？？？
我们试验一趟看看
i=0时，
dp[0]=0,
dp[1]=dp[1-1]+15//放入物品0，价值为15
dp[2]=dp[2-1]+15=dp[1]+15=30//再放入物品0
这明显就不符合题目要求了，我们只有一个物品0
但这里的dp[2]使用了dp[1]的结果，也就是放了两个物品0
也就是说正推会导致多次使用同一个物品
那我们试试逆推嘞！
假设背包最大容量就是2
dp[2]=dp[2-1]+15=dp[1]+15=0+15=15//dp[1]被初始化时就是0，背包容量为2时，加入一个0号，现在最大价值为15
dp[1]=dp[1-1]+15=dp[0]+15=15//背包容量为1时，加入一个0号，价值15
这样就完全符合规则啦！
所以我们应该将遍历顺序改为
for(int i=0;i<M;i++){//遍历物品
for(int j=N;j>=weight[i];j--){//遍历背包,如果当前背包容量不够放入当前物品就停止
那么还有一个问题，就是这种情况下，内外层循环还能换位置吗？？
倒序遍历背包大小，在每一种情况下遍历物品，这样的话就只能选择一个物品放入，显然是不符合题意的！
同样整合一下就是完整代码啦！可以参考下方给出的全部代码
我认为一维数组的方式更贴近我们往背包里放东西，容量减少，价值升高这个实际动作，
每次遍历就是在想包还有这么大，这个东西装不装
code
二维数组版
#include <bits/stdc++.h>
using namespace std;
int main() {
int M, N;
cin >> M >> N;
vector<int> weight(M,0);
vector<int> value(M,0);
for(int i=0;i<M;i++){
cin>>weight[i];
}
for(int i=0;i<M;i++){
cin>>value[i];
}
vector<vector<int>> dp(M,vector<int>(N+1));
for(int i=0;i<M;i++){
dp[i][0]=0;
}
for(int j=weight[0];j<=N;j++){
dp[0][j]=value[0];
}
for(int i=1;i<M;i++){
for(int j=0;j<=N;j++){
if(j<weight[i]) dp[i][j]=dp[i-1][j];
else{
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
}
}
}
cout<<dp[M-1][N];
}一维数组版
#include <bits/stdc++.h>
using namespace std;
int main() {
int M, N;
cin >> M >> N;
vector<int> weight(M,0);
vector<int> value(M,0);
for(int i=0;i<M;i++){
cin>>weight[i];
}
for(int i=0;i<M;i++){
cin>>value[i];
}
vector<int> dp(N+1,0);
for(int i=0;i<M;i++){
for(int j=N;j>=weight[i];j--){
dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);
}
}
cout<<dp[N];
}