背包问题总结

背包问题

背包问题 (Knapsack problem x ) 有很多种版本，常见的是以下三种：

0-1 背包问题

0-1背包中一种物体只有一个，放入数量为0或者1

定义状态 dp[i][j]，表示“把前 i 种物品装进重量限制为 j 的背包可以获得的最大价值”

v[i]表示物品i的价值，w[i]表示物品i的重量，j为背包的重量限制

0/1背包问题状态转移方程便是：

dp[i][j] = max{dp[i − 1][j], dp[i − 1][j − w[i]] + v[i]}

两项分别代表物品i不选择或者选择的情况 (减去的代表选择的)

时间复杂度是O(nb),空间也是O(nb)，假设有n种物品，重量限制为b

可以简化为:

d[j]=max{d[j],d[j-w[i]]+v[i]};

注意：遍历j时务必从右到左，因为d[j]只依赖于上一阶段的结果，从右到左避免覆盖上阶段有用结果

完全背包问题

完全背包中一种物体可以有多个，可以放满背包为止

完全背包问题状态转移方程是：

dp[i][j] = max{dp[i − 1][j], dp[i][j − w[i]] + v[i]}

两项分别代表物品i不选择或者选择，由于对物品i没有限制，故后一项为dp[i]而非上面的dp[i-1]

或用以下递推式（上面的效率要高一点）：

dp[i][j] = max( dp[i-1][j-k*w[i]] + k*v[i] ), k为选择物品的个数， k=0,1,2...j/w[i] (0 ≤ k ∗ w[i] ≤ j)

基于前i-1个物品，在选择不同个数的物品i的方案中选择最大的那个

（和问题coin change 比较相似）

可以简化为：

d[j] = max{d[j], d[j-k*w[i]] + k*v[i]}

注意：遍历j时务必从右到左，原因同上

多重背包问题

多重背包中一种物体可以有多个，个数有人为限定（也不能超过背包容量）

多重背包问题状态转移方程是：

dp[i][j] = max( dp[i−1][j−k∗w[i]] + k∗v[i] ) 0 ≤ k ≤ n[i],0 ≤ k ∗ w[i] ≤ j

n[i]为物品i限制的个数

基于前i-1个物品，在选择不同个数的物品i的方案中选择最大的那个

可以简化为：

d[j] = max{d[j], d[j-k*w[i]] + k*v[i]}

注意：遍历j时务必从右到左，原因同上

参考：