动态规划之01背包

首要

由于自己的个人原因(说白了就是懒)，忙于各种事情，实在忙不过来(哭)，只能把发文分享的事情一推再推，直到某天良心发现产生了想发文的想法，于是就写下了这篇文章，请各位大佬轻喷

背包问题

 背包问题是一种经典的dp了，有01背包，完全背包，多重背包和分组背包

我们今天讲的01背包就是最初始最基础的模型

概念讲述

假设我们现在有一个容量为bagweight的背包，有n件物品可以被我们携带，而这n件物品各有他们的价值v和重量w，求当背包装了i件物品时的最大价值，每件物品只能被带一次

假设

物品0，重量1，价值10

物品1，重量3，价值20

物品2，重量4，价值25

背包容量为4

我当时看见这种题目第一时间想的是是否可以暴力求解，但貌似会超时

于是回归到主线，动态规划

这种题目属于动态规划中的背包问题，并且是最为基础的01背包问题

在写动态规划问题时，最好将动态规划五部曲再回想一遍

dp数组及其下标的含义-------->非常重要，其他几项都是围绕着这一项进行展开

dp数组的递推式--------->建议：可以随便举出例子，然后试着找到影响这个例子的子问题或者因素

dp数组的初始化-------->就是找出不用任何条件就可以得出结论的数据

确定dp数组的遍历顺序--------->从前向后还是从后向前遍历?

dp数组打印日志检查----------->debug的好办法

这里涉及到了许多信息，背包容量限制，物品数量限制，这些限制也会是我们进行数据筛选的条件

dp数组及其下标的含义

每个物品只有两种状态，一是拿取，二是不拿

这里采用二维dp数组，dp[i][j]，这分别代表了两个维度：物品和背包容量

i代表物品，j代表背包容量

dp[0][0]就是：现背包容量为0的情况下，对于物品0的处理，当然，只有拿和不拿

由于背包容量为0，那么说明只有不拿这种情况，dp[0][0]=0，同理，当j为0时，dp[i][0]的i不管取何值都会使其变为0，即此时最大价值只能为0

dp数组递推式

我们先随便取出一个数组元素dp[2][3]，这说明背包容量为3时，在下标0到2之间选择物品得到的最大价值是多少

对于物品2，我们可以进行考虑选还是不选，

如果选，那么我们就要腾出物品2的空间进行存放物品2，然后背包容量变为了0，此时转到了dp[1][0]，即背包容量为0的情况下，在下标0和1的商品之间进行拿取，得到的最大价值是多少，dp[1][0]=0，所以得出此时的背包价值为25,注意：此时代表的不是最大价值，只是背包的某种情况下的价值

 如果不选，那么我们就要在下标0和1中进行选择即dp[1][3]，但这个dp[1][3]我们已经求出结果，此时只需要将其与上面得出的值进行比较得出最大即可

最后得出递推式dp[ i ][ j ]=max(dp[ i - 1 ][ j - weight[ i ] ]+value[ i ],dp[ i -1 ][ j ])//前者代表选择，后者代表没选

由于已经经过选择，那么就需要将下标进行移动，在下标0到i-1中再次进行选择吧

dp数组初始化

上面已经讲到：当背包容量为0时，此时的最大价值就一定是0，dp[i][0]=0

然后根据递推式可以知道，i由i-1推导得出，这是从前往后推导得出，那么就需要知道i=0时的情况

当j<weight[0]时，即此时的背包容量不足以装载物品0，此时的最大值也就是0

当j>=weight[0]时，dp[0][j]=weight[0]，因为此时背包只能从下标0中进行选择，并且此时背包已经可以装下物品0，那么为了最大起见，就要选择将物品0装入背包

剩下的部分初始化为我们在得到的结果中绝对不可能出现的值，如果出现了可能出现的值，那么不能确定此时的值是已经更改过的值还是原本就有的值

dp数组的遍历顺序

遍历顺序从背包重量过来和物品过来都可以

背包问题的状态都可以进行压缩实现

滚动数组的实现条件：上一层可以重复利用，可以直接拷贝到当前层

dp数组一维滚动数组实现

 首先，我们知道根据上文dp[i][j]=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j]);

我们可以知道i都是从i-1过来的，那么直接从i-1这里进行拷贝即可

dp[i][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])

此时我们可以很直观的感受到，这个dp数组是一层套着一层逐级移动，一遍又一遍的覆盖，那还用什么二维数组，直接一维数组即可解决

dp[j]=max(dp[j-weight[i]]+value[i],dp[j])

这样我们的dp数组就变成了一维状态

dp[i][j]表示的是在下标0到i之间，背包容量为j时得到的最大价值

现在是dp[j]，背包容量为j的情况下所得到的最大价值

一维滚动数组初始化

当j为0时，容量为0不能存东西，dp[0]=0

其他下标所对应元素直接初始化为0即可

如果对初始化没有思路时，请直接看向递推式，千万不要凭感觉就往上写

一维数组的遍历方式(很重要(其实每个步骤都很重要！))

特别注意！ 

注意这里的遍历是倒序进行书写

for(int i = 0; i < weight.size(); i++) { // 遍历物品for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}
}
//此处代码转载自代码随想录

变化更慢的是先遍历的变量

先遍历物品后遍历背包容量 

如果正序进行书写，就会出现以下情况

此时i=0,j=1

dp[1]=max(dp[1],dp[1-weight[0]]+value[0])

dp[1]经过初始化后为0，得dp[1]=15

dp[2]=max(dp[2],dp[2-weight[0]]+value[0])

dp[2]经过初始化后为0，dp[2]=30  ???

出现问题了，我们将weight[0]重复计算了一遍！

由于在遍历背包容量的过程中，我们的物品尚未被改变，那么只要后面的容量大于weight[0]，我们便会将当前的dp[i]从后往前迭代一个value[0]，从而引发错误

所以我们需要倒序书写

假设bagweight=4

此时i=0，j=4

dp[4]=max(dp[4],dp[4-weight[0]]+value[0])

此时dp[4]经过初始化后为0，dp[4]=dp[3]+value[0]=15

dp[3]=max(dp[3],dp[3-weight[0]]+value[0])

dp[3]=15

这样取得的状态不会与之前重叠，顺利完成遍历

思考，我们是否可以先遍历背包容量再遍历物品

这是不可以的

上面说了dp[j]代表了背包容量为j的情况下，能够得到的最大价值

如果我们先遍历背包容量，那么我们的背包容量就是从大到小的过程，此时背包中只会放入一个物品