这篇主要介绍了01背包问题理论内容，下一篇是对问题的实践。

01背包

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将物品装入背包里物品价值总和最大是多少。

先从二维dp数组说起

1. 定义dp[i][j]为从下标为0到i物品中任意取，装入容量为j的背包最大的价值，这么定义是因为题目求的就是价值总和最大是多少；

2. 递推公式

   01背包是物品只能使用一次，存在放或者不放两种情况。

   • 放物品：此时dp[i][j] = dp[i-1][j-weight[i]] + value[i]
   • 不放物品：那么就直接是上一次的dp[i-1][j]

​ 上面存在两种情况，但当j>=weight[i]的时候才能够放入物品，此时选择结果最大的一个Max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])；而j < weight[i]时就只能从dp[i-1][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])
}

3. 初始化

   定义dp[i][j]为从下标为0到i物品中任意取，装入容量为j的背包最大的价值

   从dp数组定义出发，

   • dp[i][0]代表把物品编号为0-i的任意选择装入容量为0的背包最大价值是多少，容量为0显然总价值为0；

   • dp[0][j]代表把编号为0的物品装入容量为j的背包，由于只能装一次，那么当容量j能够装入物品0那么就一定要装的，此时初始化为物品0的价值，所以初始化如下：

for j := bagWeight; j >= weight[0]; j-- {
    dp[0][j] = value[0]
}

4. 遍历顺序

   应该先遍历背包还是先遍历物品？都可以。

   dp数组定义不变

   对于先遍历物品再遍历背包，就是按行遍历。简单理解是对每一个物品尝试装入不同容量的背包，这个背包可能装入了之前的物品，也可能没有装入，反正是求最大价值，用物品一个个地去尝试。

   对于先遍历背包再遍历物品，就是按列遍历。简单理解是容量固定的背包，按序尝试装入所有物品，肯定是能装才装，依然是选择能装入最大的。

   那么为什么两种都可以勒，可以从递推公式来理解：

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

   不论是什么情况，dp[i][j]都是依赖矩阵上面或者左上推出来的（dp[i-1]），而不论是什么遍历顺序都会提前计算出当前dp[i][j]左上位置的信息，所以遍历顺序就不影响了。

   从递推公式的递推方向看遍历顺序非常重要，后面也会有很多地方用到。

一维滚动数组

相对于二维数组来说，一维看着更加简洁，但要求更加严格了，不易理解。

通过对二维dp数组的分析，已经理解了从递推方向来看可行性，那么回到先遍历物品再遍历背包的情况，可以发现对行遍历只会依赖上一行的信息，而更上层的信息就完全没用了，所以滚动数组就是借助这一点，将上一层用完或无用信息不断覆盖，变成当前层的信息。

而对于先遍历背包再遍历物品我们可以知道是按列遍历，第i列的仍可能会依赖第1列的数据，所以没法只用一维的数组保存更多信息，因为你也不知道哪一个后面会用到。

1. dp[j]定义为容量为j的背包能装物品的最大价值

2. 递推公式

   和二维类似，只是去掉了物品维度的信息，所以如下

   for i := range weight {
       for j := 0; j <= bagWeight; j++ {
           if j < weight[i] {
               dp[j] = dp[j]
           } else {
               dp[j] = Max(dp[j], dp[j-weight[i]]+value[i])
           }
   	}
   }
   

   （上面这个是二维情况直接去掉物品维度的结果）

3. 初始化

   dp[0]就是容量为0，那么没法装任何东西所以dp[0]=0，而对于其他容量的情况因为是求最大值，应该初始为一个较小的值便于后续比较替换，而又不会低于0，所以也初始化为0就可以了。

   go无需特别处理，初始化不赋值默认为0。

4. 遍历顺序

   一个关键问题是对于背包的遍历我们只能倒序，也就是从大到小遍历。

   为什么？还是从递推方向来看，因为我们需要依赖上一层左边的信息，如果从前往后遍历那么左边的会被不断覆盖，后面使用的就有可能*不是上一层原本的了，那不是原本的是什么？可能是这个物品已经加入后的最优结果（满足max条件），如果此时又成功被max选中了就相当于多次加入了同一物品。

   *：为什么是有可能呢，因为结果不一定是最大的，max函数选择的是原本的那个值。

   也就是说如果坚持从左往右遍历，对同一物品遍历的时候可能会多次加入，那么就不是01背包了。

   所以上面那个不是最终版本，对于背包的遍历是从后往前的，而且从后往前可以直接在遍历边界时避免j < weight[i]的情况出现。

   for i := range weight {
       for j := bagWeight; j >= weight[i]; j-- {
           dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
       }
   }
   

   内层的背包容量坚持从左往右可以发现同一物品可能会多次放入，

   另一个问题是先遍历容量还是先遍历物品

   如果我们先遍历容量再遍历物品（容量倒序）会发生什么？每个dp[i]都只会放进一个能装入的最大价值物品。

   详细的代码可以查看这里

小结

对于01背包问题：

• 二维的dp数组：遍历的前后顺序和物品容量层次顺序都可以交换顺序。因为二维保留了很多上下文信息能够推出结果（这里将物品和容量分别看作一维，容量本身可能是多维的也笼统看作一维）

• 一维的dp数组（滚动数组）：只能是先遍历物品，再遍历容量，而且内层容量的遍历只能是倒序的。

• ← Previous Post
• Next Post →