dp技巧思路总结——背包
0-1背包相关题目可以参考上一篇文章,这篇开始介绍一些其他的背包问题例如多重背包等。
子集背包问题
这题在0-1背包那边已经讲过了,这里重新讲一次:
这个问题看上去和背包并没有太大的关系,实际上我们可以先回忆一下背包问题的大致描述:
载重 W
的背包和 N
个物品,每个物品有重量和价值两个属性。其中第 i
个物品重量是 wt[i]
,价值为 val[i]
,现在让背包去装物品,能装的最大的价值是?
这个子集问题就可以转换为载重量为 sum/2
的背包,和 N
个物品,每个物品重量为 nums[i]
。现在让你去装物品,是否存在一种装法,能够恰好装满背包?
解法分析
- 先来确定状态和选择。
背包问题的状态就是“背包的容量”和“可选择的物品”,选择就是 “装进背包” 或 “不装进背包”。
- 明确 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
,因为背包没空间的时候,相当于是装满了,而没有物品选择的时候,肯定没办法装满背包。
- 根据选择,去思考状态转移方程
- 如果不把
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 | const solve = (arr) => { |
状态压缩
考虑到 dp[i][j]
都是通过 dp[i-1][...]
转移过来的,之前的数据都不会再使用了。
所以,可以进行一个状态压缩,将二维 dp 压缩成一维的。
1 | const solve = (arr) => { |
需要注意的是 j
应该从后往前反向遍历,因为每个物品(或者说数字)只能用一次,以免之前的结果影响其他的结果。
完全背包问题
参考这个题目:https://leetcode-cn.com/problems/coin-change-2/ 零钱兑换2号
转换成背包的描述形式:
有个最大容量为 amount
背包,有一系列物品 conis
,每个物品的重量为 conis[i]
,每个物品的数量是无限的。这里同0,1
背包区别在于物品可以无限量的选择,状态转移方程式有一丢丢不同而已。
思路
- 确定状态和选择:
状态还是分为背包容量和可选择的物品,选择就是是否装进背包。
明白了状态和选择,那么这个问题就基本上解决了,套框架即可:
1 | for 状态1 in 状态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 | int dp[N+1][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 | for (let i = 1;i<=n;i++) { |