对于面试的话，其实掌握01背包，和完全背包，就够用了，最多可以再来一个多重背包。

image.png
至于背包九讲其其他背包，面试几乎不会问，都是竞赛级别的了，leetcode上连多重背包的题目都没有，所以题库也告诉我们，01背包和完全背包就够用了。
而完全背包又是也是01背包稍作变化而来，即：完全背包的物品数量是无限的。

所以背包问题的理论基础重中之重是01背包，一定要理解透！

一、01 背包

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

这是标准的背包问题，以至于很多同学看了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。
这样其实是没有从底向上去思考，而是习惯性想到了背包，那么暴力的解法应该是怎么样的呢？

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是背包理论之 01 背包 - 图2，这里的 n 表示物品数量。

所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

在下面的讲解中，我举一个例子：
背包最大重量为 4。
物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？
以下讲解和图示中出现的数字都是以这个例子为例。

1. 二维 dp 数组 —— 01 背包

动规五部曲分析

依然动规五部曲分析一波。

  1. 确定 dp 数组以及下标的含义

对于背包问题，有一种写法， 是使用二维数组，即 dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。
只看这个二维数组的定义，大家一定会有点懵，看下面这个图：
image.png

  1. 确定递推公式

再回顾一下 dp[i][j] 的含义：从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。
那么可以有两个方向推出来 dp[i][j]

  • 不放物品 i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]
    • 其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同
  • 放物品 i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]]为背包容量为j - weight[i]的时候不放物品 i 的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品 i 的价值），就是背包放物品 i 得到的最大价值

所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

  1. dp数组如何初始化

关于初始化，一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发，如果背包容量 j 为 0 的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为 0。如图：
image.png
在看其他情况。
状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) 可以看出 i 是由 i-1 推导出来，那么 i 为 0 的时候就一定要初始化。

dp[0][j]，即：i 为 0，存放编号 0 的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j]应该是 0，因为背包容量比编号 0 的物品重量还小
当j >= weight[0]时，dp[0][j]应该是value[0]，因为背包容量放足够放编号 0 物品。

  1. // 初始化 dp 数组，都设置为 0
  2. const dp = new Array(weight.length).fill(0).map(a => new Array(begWeight).fill(0))
  4. // 初始化 i = 0 时，dp[0][j]
  5. for (let j = weight[0]; j < begWeight; j++) {
  6.   dp[0][j] = value[0]
  7. }
  1. 确定遍历顺序

在如下图中，可以看出，有两个遍历的维度：物品与背包重量

那么问题来了，先遍历物品 还是 先遍历背包重量呢？ 其实都可以！！ 但是先遍历物品更好理解。

image.png

  1. for (let i = 1; i < weight.length; i++) {
  2.   for (let j = 0; j <= bagWeight; j++) {
  3.      if (j < weight[i]) {
  4.        dp[i][j] = dp[i - 1][j]
  5.      } else {
  6.        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
  7.      }
  8.   }
  9. }
  1. for (let j = 0; j <= begWeight; j++) {
  2.   for (let i = 1; i < weight.length; i++) {
  3.     if (j < weight[i]) {
  4.       dp[i][j] = dp[i - 1][j]
  5.     } else {
  6.       dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
  7.     }
  8.   }
  9. }

image.png

  1. 举例推到 dp 数组，来验证

image.png

做动态规划的题目，最好的过程就是自己在纸上举一个例子把对应的dp数组的数值推导一下，然后在动手写代码！

完整 JS 代码

  1. function WeightBagProblem(weight, value, begWeight) {
  2.   // 初始化
  3.   const dp = new Array(weight.length).fill(0).map(() => new Array(begWeight).fill(0))
  4.   for (let j = weight[0]; j <= begWeight; j++) {
  5.     dp[0][j] = value[0]
  6.   }
  8.   for (let i = 1; i < weight.length; i++) {
  9.     for (let j = 0; j <= begWeight; j++) {
  10.       if (j < weight[i]) {
  11.         dp[i][j] = dp[i - 1][j]
  12.       } else {
  13.         dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
  14.       }
  15.     }
  16.   }
  18.   return dp[weight.length - 1][begWeight]
  19. }
  22. function test() {
  23.   console.log(WeightBagProblem([1, 3, 4], [15, 20, 30], 4)) // 35
  24.   console.log(WeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6)) // 70
  25. }
  27. test();

2. 滚动数组 —— 01背包

滚动数组，就是把二维 dp 降为一维 dp。我们还是使用 01 背包这个题目，来讲。
在使用二维数组的时候，递推公式：
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

其实可以发现如果把**dp[i - 1]**那一层拷贝到**dp[i]**上，表达式完全可以是：
**dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])**

与其把**dp[i - 1]**这一层拷贝到**dp[i]**上，不如只用一个一维数组了，只用dp[j]

一维数组，也可以理解是一个滚动数组。 这就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。

读到这里估计大家都忘了 dp[i][j]里的i和j表达的是什么了，i是物品，j是背包容量。
dp[i][j] 表示从下标为 [0-i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

动规五部曲

动规五部曲分析如下：

  1. 确定 dp 数组的定义

在一维 dp 数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

  1. 一维dp数组的递推公式

dp[j]为容量为j的背包所背的最大价值，那么如何推导dp[j]呢？
dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

  1. dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
  1. 一维数组的初始化

dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]，那么dp[0]就应该是 0。
因为背包容量为 0，所背的物品的最大价值就是0。

  1. const dp = new Array(begWeight + 1).fill(0)
  1. 一维 dp 数组遍历顺序

二维 dp 遍历的时候，背包容量是从小到大，而一维 dp 遍历的时候，背包是从大到小。
为什么呢？
倒序遍历是为了保证物品 i 只被放入一次！但如果一旦正序遍历了，那么物品 0 就会被重复加入多次！

  1. // 遍历物品
  2. for (let i = 0; i < weight.length; i++) {
  3.   // 遍历背包
  4.   // j < weight[i] 的背包，已经找过最大值了。你想想从第一个物品开始，它重量最小，放入能承受的背包了。接着，物品从小到大
  5.   for (let j = begWeight; j >= weight[i]; j--) {
  6.     dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
  7.   }
  8. }

再来看看两个嵌套 for 循环的顺序，代码中是先遍历物品嵌套遍历背包容量，那可不可以先遍历背包容量嵌套遍历物品呢？
不可以！
因为一维 dp 的写法，背包容量一定是要倒序遍历。如果遍历背包容量放在上一层，那么每个dp[j]背包会放入多个 A 物品，实际上，A 物品只有一个。

  1. 举例推导dp数组

image.png

完整 JS 代码

  1. function WeightBagProblem(weight, value, begWeight) {
  2.   const dp = new Array(begWeight + 1).fill(0)
  4.   for (let i = 0; i < weight.length; i++) {
  5.     for (let j = begWeight; j >= weight[i]; j--) {
  6.       dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
  7.     }
  8.   }
  10.   return dp[begWeight]
  11. }
  13. function test() {
  14.   console.log(WeightBagProblem([1, 3, 4], [15, 20, 30], 4))
  15.   console.log(WeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6));
  16. }
  18. test();