跟着卡哥学算法Day 35：动态规划part3

二维 dp 数组 01 背包#

动规五部曲：

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

   需要定义二维数组：一个维度表示背包容量，一个维度表示表示物品，即 dp[i][j] 表示前 i 个物品放入容量为 j 的背包时的最大价值。

   1. 处理物品 0（重量 1，价值 15）

      当 j = 0（容量为 0）时，无法放入，价值为 0；若 j ≥ 1，可以放入物品 0，价值为 15。

      背包容量	0	1	2	3	4
      物品 0	0	15	15	15	15

   2. 处理物品 1（重量 3，价值 20）

      • 容量 1-2：无法放入物品 1，继承物品 0 的值 15

      • 容量 3：

        • 不放入物品 1：那么背包的价值应该是 dp[1][3] = dp[0][3] = 15，即容量为 3 的背包，只放物品 0 的情况
        • 放入物品 1：那么背包要先留出物品 1 的容量，目前容量为 3，物品 1 的重量为 3，背包剩余容量为 0 时的价值为 dp[0][0] = 0，所以 dp[1][3] = dp[0][3-3] + 20 = 0 + 20 = 20
        • 取最大值 20

      • 容量 4：

        • 不放入物品 1：那么背包的价值应该是 dp[1][4] = dp[0][4] = 15，即容量为 4 的背包，只放物品 0 的情况
        • 放入物品 1：目前容量为 4，物品 1 的重量为 3，背包剩余容量为 1，背包容量为 1 时的价值为 dp[0][1] = 15, 所以dp[1][4] = dp[0][4-3] + 20 = 15 + 20 = 35
        • 取最大值 35

        背包容量	0	1	2	3	4
        物品 0	0	15	15	15	15
        物品 1	0	15	15	20	35

   3. 处理物品 2（重量 4，价值 30）

      • 容量 1-3：无法放入物品 2，继承物品 1 的值。

      • 容量 4：

        • 不放入物品 2：dp[2][4] = dp[1][4] = 35，即容量为 4 的背包，放入物品 0 和 1 的情况
        • 放入物品 2：目前容量为 4，物品重量为 4，放入后背包剩余 0 的价值为 dp[0][0] = 0，所以dp[2][4] = dp[1][4-4] + 30 = 0 + 30 = 30
        • 取最大值 35

      背包容量	0	1	2	3	4
      物品 0	0	15	15	15	15
      物品 1	0	15	15	20	35
      物品 2	0	15	15	20	35

2. 确认递推公式

   通过上面的示例，我们可以得出不放入第 i 个物品和放入第 i 个物品的最大价值：

   1. 不放入第 i 个物品：背包容量为 j，里面不放物品 i 的最大价值是 dp[i][j] = dp[i-1][j]
   2. 放入第 i 个物品：背包空出物品 i 的容量后，背包容量为 j - weight[i]，dp[i-1][j-weight[i]] 为背包容量为 j - weight[i] 且不放物品 i 的最大价值， dp[i][j] = dp[i-1][j-weight[i]] + value[i] 就是背包放入物品 i 得到的最大价值

   两者取最大值：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

3. dp 数组初始化

   初始化一定要和 dp 数组的定义吻合，否则到递推公式的时候会越来越乱

   • 当 j = 0（背包容量为 0）时，背包价值为 0，即dp[i][0] = 0
   • 由状态转移方程可知，i 是由 i-1 推导出来的，所以 i 为 0 需要初始化
     • 当 j < weight[0] 时，dp[0][j] = 0，背包容量比编号 0 的物品重量小
     • 当 j >= weight[0] 时，dp[0][j] = value[0]，背包容量比编号 0 的物品重量大，可以放入，此时价值就是 value[0]

   此时，dp 数组初始化应该如下：

   背包容量	0	1	2	3	4
   物品 0	0	15	15	15	15
   物品 1	0
   物品 2	0

   由递推公式可以 dp[i][j] 都会由左上方的值决定，所以初始化任何数都可以，统一填充为 0

4. 确定遍历顺序

   有两个维度，物品和背包容量，先遍历物品还是先遍历背包容量呢？

   先遍历物品，再遍历背包容量，就类似于上面的推导过程，比较好理解

   1
   for (let i = 1; i < weight.length; i++) {
   2
     // 物品
   3
     for (let j = 0; j <= W; j++) {
   4
       // 背包容量
   5
       // 1. 不放入物品 i
   6
       if (j < weight[i]) {
   7
         dp[i][j] = dp[i - 1][j]
   8
       } else {
   9
         // 2. 放入物品 i
   10
         dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
   11
       }
   12
     }
   13
   }

5. 举例推导 dp 数组

   上述示例的 dp 数组应该是：

   1
   [
   2
     [0, 15, 15, 15, 15],
   3
     [0, 15, 15, 20, 35],
   4
     [0, 15, 15, 20, 35]
   5
   ]

代码#

1
function knapsack01(W, weight, value) {
2
  const n = weight.length
3
  const dp = new Array(n).fill().map(() => new Array(W + 1).fill(0))
4

5
  // 初始化 dp 数组
6
  for (let j = 0; j <= W; j++) {
7
    if (j >= weight[0]) {
8
      dp[0][j] = value[0]
9
    }
10
  }
11

12
  for (let i = 1; i < n; i++) {
13
    for (let j = 0; j <= W; j++) {
14
      if (j < weight[i]) {
15
        dp[i][j] = dp[i - 1][j]
16
      } else {
17
        dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
18
      }
19
    }
20
  }
21

22
  console.log(dp)
23
  return dp[n - 1][W]
24
}

代码#

1
function knapsack01(W, weight, value) {
2
  const dp = new Array(W + 1).fill(0) // 初始化一维数组
3
  const n = weight.length
4

5
  for (let i = 0; i < n; i++) {
6
    // 遍历物品
7
    for (let j = W; j >= weight[i]; j--) {
8
      // 逆序遍历容量
9
      dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
10
    }
11
    console.log(dp)
12
  }
13
  return dp[W]
14
}

二维 dp 数组#

动规五部曲：

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

   • 01 背包中，dp[i][j] 表示在[0, i - 1]范围内的物品放入容量为 j 的背包，所背物品的最大价值
   • 本题中，dp[i][j] 表示在[0, i - 1]范围内是否存在和为 j 的子集

2. 确定递推公式

   • 01 背包二维数组的递推公式为：dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]])
   • 此题的递推公式为：dp[i][j] = dp[i - 1][j]（不选） || dp[i - 1][j - nums[i]]（选择）

3. 初始化 dp 数组

   • 初始化所有dp[i][0]为 true，因为不选择任何元素时，和为 0 总是成立的
   • 初始化dp[0][nums[0]]为 true，只选第一个数字时，和为 nums[0] 总是成立的
   • 其他位置填充为 false

   

4. 确定遍历顺序

   先遍历数字，再遍历每一个可能的和 [1…sum/2]

   1
   for (let i = 1; i < nums.length; i++) {
   2
     // 数字
   3
     for (let j = 1; j <= sum / 2; j++) {
   4
       // 和
   5
       // 1. 不选择数字
   6
       // 不选择当前元素，继承上一行的结果
   7
       if (j < nums[i]) {
   8
         dp[i][j] = dp[i - 1][j]
   9
       } else {
   10
         // 2. 选择数字
   11
         // 如果当前元素的值小于等于j，则`dp[i][j]`取决于是否选择当前元素
   12
         dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num[i]]
   13
       }
   14
     }
   15
   }

   展开收起

5. 举例推导 dp 数组

   

1
function canPartition(nums) {
2
  const sum = nums.reduce((a, b) => a + b)
3
  if (sum % 2 !== 0) return false
4

5
  const target = sum / 2
6
  const len = nums.length
7
  const dp = new Array(len).fill().map(() => new Array(target + 1).fill(false))
8

9
  // 初始化第一列为true 不选择任何元素时和为0总是成立的
10
  for (let i = 0; i < len; i++) {
11
    dp[i][0] = true
12
  }
13
  // 只选第一个数字时，和为nums[0] 总是成立的
14
  if (nums[0] <= target) {
15
    dp[0][nums[0]] = true
16
  }
17

18
  for (let i = 1; i < len; i++) {
19
    const num = nums[i]
20
    for (let j = 1; j <= target; j++) {
21
      if (j < num) {
22
        dp[i][j] = dp[i - 1][j]
23
      } else {
24
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - num]
25
      }
26
    }
27
  }
28
  console.log(dp)
29

30
  return dp[len - 1][target]
31
}

滚动数组#

即 dp[sum/2] === sum/2。

按照上题，只要找出 dp[11] 等于 11，则返回 true。

动规五部曲：

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

   • 01 背包中，dp[j]指的是容量为 j 的背包，所背物品的最大价值为 dp[j]
   • 本题中， dp[j]指的是容量为 j 的背包，所背数字的最大和为 dp[j]

   当 dp[j] === j 时，表示背包容量为 j 时，背包刚好装满

   如 dp[6] === 1 + 5，表示容量为 6 的背包，放入 1 和 5 后，刚好装满，即和为 6

2. 确定递推公式

   • 01 背包的递推公式为：dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i])
   • 本题重量和价值都是数字本身，所以递推公式：dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])

3. dp 数组初始化

   • 根据 dp 的定义，dp[0] = 0
   • dp[1…sum/2]初始化也设为 0

4. 确定遍历顺序

   如果使用一维数组，需要先遍历物品，再遍历背包，且背包按逆序遍历

5. 举例推导 dp 数组

   输入[1,5,11,5]，得到的 dp 数组为：

   1
   // 1
   2
   dp = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
   3
   // 5
   4
   dp = [0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 6, 6]
   5
   // 11
   6
   dp = [0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 6, 11]
   7
   // 5
   8
   dp = [0, 1, 1, 1, 1, 5, 6, 6, 6, 6, 10, 11]

   最后 dp[11] === 11，返回 true