【蓝桥杯速成】| 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];
}