0%

背包问题分析

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 时,若 xtrue ,则说明可以恰好将背包装满,若为 false,则说明不能恰好将背包装满。

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

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

所以根据此定义,我们最终想求的答案就是 dp[N][sum/2]base case 就是dp[...][0] = truedp[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 casedp[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]