zoomdong's blog
0%

背包问题分析

Posted on Edited on

dp技巧思路总结——背包

0-1背包相关题目可以参考上一篇文章，这篇开始介绍一些其他的背包问题例如多重背包等。

子集背包问题

这题在0-1背包那边已经讲过了，这里重新讲一次：

Leetcode 416题

这个问题看上去和背包并没有太大的关系，实际上我们可以先回忆一下背包问题的大致描述：

载重 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品重量是 wt[i]，价值为 val[i]，现在让背包去装物品，能装的最大的价值是？

这个子集问题就可以转换为载重量为 sum/2 的背包，和 N 个物品，每个物品重量为 nums[i] 。现在让你去装物品，是否存在一种装法，能够恰好装满背包？

解法分析

  1. 先来确定状态和选择。

背包问题的状态就是“背包的容量”和“可选择的物品”，选择就是 “装进背包” 或 “不装进背包”。

  1. 明确 dp 数组的含义

按照背包问题的套路，可以给出如下的定义：

dp[i][j] = x ，表死前i个物品，当前背包容量为 j 时，若 x 为 true ，则说明可以恰好将背包装满，若为 false，则说明不能恰好将背包装满。

例如：dp[4][9] = true 表示取前四个数能能装满一个容量为 9 的背包。

对于本题来说，若只选择前四个数字，存在一个子集里面的和可以凑出来数字 9。

所以根据此定义，我们最终想求的答案就是 dp[N][sum/2]，base case 就是dp[...][0] = true和dp[0][...]=false,因为背包没空间的时候，相当于是装满了，而没有物品选择的时候，肯定没办法装满背包。

  1. 根据选择，去思考状态转移方程
  • 如果不把nums[i] 放入背包，那么就有 dp[i][j] = dp[i-1][j]。
  • 如果把 nums[i] 放入背包，就有 dp[i][j] = dp[i-1][j-nums[i-1]]

因为数组下标是从0开始的，所以上面第二个就是 nums[i-1]

dp[i-1][j-nums[i-1]]表示装了第 i 个物品，就要看背包的剩余重量 j-nums[i-1]限制下能否能够被装满。

最后一步直接写代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const solve = (arr) => {
  let sum = arr.reduce((prev, next) => prev + next)
  if (sum & 1) {
    return false;
  }
  let len = arr.length;
  let dp = []
  for (let i = 0; i<=len; i++) {
    dp[i] = [];
    for (let j = 0; j<=sum/2; j++) {
      dp[i][j] = false;
      dp[i][0] = true;
    }
  }
  for (let i = 1;i<=len;i++) {
    for (let j = 1;j<=sum / 2;j++) {
      if (j >= nums[i-1]) {
        dp[i][j] = dp[i-1][j] || dp[i-1][j- nums[i-1]];
      } else {
        dp[i][j] = dp[i-1][j]
      }
    }
  }
  return dp[len][sum/2]
}

状态压缩

考虑到 dp[i][j] 都是通过 dp[i-1][...] 转移过来的，之前的数据都不会再使用了。

所以，可以进行一个状态压缩，将二维 dp 压缩成一维的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const solve = (arr) => {
  let sum = arr.reduce((prev, next) => prev + next)
  if (sum & 1 || arr.length <= 2) {
    return false;
  }
  let dp = Array.from(sum + 1, false)
  dp[0] = true;
  for (let i = 0;i<arr.length;i++) {
    for (let j = sum;j >= 0 ;j--) {
      if(j >= nums[i]) {
        dp[j] = dp[j] || dp[j - nums[i]]
      }
    }
  }
  return dp[sum]
}

需要注意的是 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。

完全背包问题

参考这个题目：https://leetcode-cn.com/problems/coin-change-2/ 零钱兑换2号

转换成背包的描述形式：

有个最大容量为 amount 背包，有一系列物品 conis ，每个物品的重量为 conis[i] ，每个物品的数量是无限的。这里同0,1背包区别在于物品可以无限量的选择，状态转移方程式有一丢丢不同而已。

思路

  1. 确定状态和选择：

状态还是分为背包容量和可选择的物品，选择就是是否装进背包。

明白了状态和选择，那么这个问题就基本上解决了，套框架即可：

1
2
3
4
for 状态1 in 状态1的所有取值
 for 状态2 in 状态2的所有取值
  for ...
    dp[状态1][状态2][...] = 计算(选择1,选择2...)
  1. 明确 dp 数组的定义。

这题的状态也是两个，使用前i 种物品，当背包容量为 j 时，有 dp[i][j] 种方法可以装满背包。

那就是使用coins 数组的前 i 个硬币，想要凑出 j 金额，有 dp[i][j] 中凑法。

经过以上的定义，可以得到：

base case 为 dp[0][...] = 0, dp[...][0] = 1。因为如果不使用任何硬币面值，就无法凑出任何金额；如果凑出的目标金额为0，那么“无为而治”就是唯一的一种凑法。

那么我们最后要的结果就是 dp[N][amount]，其中 N 为 conis 数组的大小。

大致的代码思路为：

1
2
3
4
5
6
7
8
9
int dp[N+1][amount+1];
dp[0][...] = 0;
dp[...][0] = 1;

for i in [1...N]:
  for j in [1...amount]:
    物品 i 放进背包,
    物品 i 不放进背包
return dp[N][amount];
  1. 根据选择来确定状态转移的逻辑

这个问题的特殊之处在于物品的数量是无限的，所以这里和之前的背包问题有一丢丢不同。

这里如果不把 i 物品装入背包，也就是说不使用 coins[i] 这个面值的硬币，凑出面额 j 的方法数dp[i][j] 应该为 dp[i-1][j]

如果 i 物品装入了背包，也就是说使用了 coins[i] 这个面值的硬币，那么 dp[i][j] 应该等于 dp[i][j-conis[i-1]]

这里的索引仍然是从1开头，所以上面是conis[i-1]

综上两种选择，我们要求的 dp[i][j] 是 “共有多少种凑法”，所以 dp[i][j] 的值应该是以上两种选择的结果之和：

1
2
3
4
5
6
7
8
for (let i = 1;i<=n;i++) {
  for (let j = 1;j<=amount;j++) {
    if (j >= coins[i-1]) {
      dp[i][j] = dp[i-1][j] + dp[i][j-conis[i-1]];
    }
  }
}
return dp[N][amount]