一文搞懂经典0-1背包问题
背景
记得在大学课程中，修过《算法和数据结构》，其中的0-1背包问题，是非常经典的算法题目，当时上课时，听老师讲完后，懂了个大概，工作若干年后，已经都忘记得差不多了，印象深刻的就是往背包里面塞东西，有个重量限制，问能取得的最大价值是多少。当时最naive的想法是，贪心不就完了，用价值/重量比最高的往里面塞就可以了，但其实这个贪心解法在0-1背包问题上是不work的。对于0-1背包问题，贪心选择之所以不能得到最优解是因为：它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。（原因引用出处）最近，我想看看0-1背包问题，到底有什么算法求解，是最合适的，也是最合理的，所以开始翻阅了资料，自己动手实现了代码，也就有了此文。
问题
说了这么多，在这篇文章中，您将看到以下内容：
- 0-1背包问题的三种实现，时间复杂度和空间复杂度分析；
- 针对上述的代码实现，构建实际测试用例，看实际case下的benchmark数据；
讨论
0-1背包问题（NP-Complete）
问题定义，给定N个物品，w[i]表示第i件物品的重量，v[i]表示第i件物品的价值。给你一个背包，总重量限制为W。求这个背包可以装下物品的最大价值和，注意，每个物品最多用一次。
解法1. 组合搜索
使用一个长度为n的二进制string，表示x0x1……xn。其中xi要么是0要么是1，0表示该物品不放入背包，1表示放入背包。尝试所有的可能组合。时间复杂度O(2^n),空间复杂度O(n)。该实现时间复杂度较高，一般只能在n很小的时候使用，一般为n <= 20，而且v,W >> 10^6。
代码实现如下：
func knapsack01C(v []int, w []int, W int) int {
defer time_cost(time.Now(), "knapsack01C")
r := 0
var help func(s int, c_w int, c_v int)
help = func(s int, c_w int, c_v int) {
if c_v > r {
r = c_v
}
for i := s; i < len(v); i++ {
if c_w+w[i] <= W {
help(i+1, c_w+w[i], c_v+v[i])
}
}
}
help(0, 0, 0)
return r
}
解法2. 记忆化递归
定义dp(i,j)为使用前i个物品，在重量为j获取到的最大价值，dp(*,0) = 0。关键是把(i,j)看作一个状态(state)，这个state下最大的价值作为值记忆化存起来，再此求解到相同状态，直接返回之前求解的值即可。
举个实例：
v = {1, 2, 4, 5}
w = {1, 1, 2, 2}
解法2的时间复杂度，O(NW)，空间复杂度，O(NW)，如果重量w = {1, 2, 4, 8……, 2^n}，那么会退化为解法1，不会有上图中重复子问题的出现，可见记忆化递归和下面要讲的动态规划，都是基于问题是否存在大量的重复子问题，如果没有，意义不大。
代码实现如下：
func knapsack01R(v []int, w []int, W int) int {
defer time_cost(time.Now(), "knapsack01R")
n := len(v)
dp := make(map[[2]int]int)
var help func(i int, l_w int) int
help = func(i int, l_w int) int {
if i == 0 {
return 0
}
k := [2]int{i, l_w}
t, ok := dp[k]
if ok {
return t
}
l, r := 0, 0
if l_w >= w[i-1] {
l = help(i-1, l_w-w[i-1]) + v[i-1]
}
r = help(i-1, l_w)
ret := 0
if l > r {
ret = l
} else {
ret = r
}
dp[k] = ret
return ret
}
r := 0
for i := 0; i <= n; i++ {
t := help(i, W)
if t > r {
r = t
}
}
return r
}
解法3. 动态规划
这个方式与方法2记忆化递归方法类似。
定义dpi为使用前i个物品，在重量为j时获取到的最大价值。状态转移方程：
dpi = dpi-1 j < w[i] or max{dpi-1]+v[i], w[i] <= j <= W}
ans = max{dpN}
时间复杂度为O(NW)，空间复杂度O(NW)。空间复杂度通过滚动数组，可以降维到O(W)。什么时候使用此解法？一般n > 20并且N、W在10^6~10^7数量级。
代码实现如下：
func knapsack01D(v []int, w []int, W int) int {
defer time_cost(time.Now(), "knapsack01D")
n := len(v)
var dp [][]int
for i := 0; i <= n; i++ {
row := make([]int, W+1)
dp = append(dp, row)
}
for i := 0; i <= n; i++ {
dp[i][0] = 0
}
for j := 0; j <= W; j++ {
dp[0][j] = 0
}
for i := 1; i <= n; i++ {
for j := 0; j <= W; j++ {
dp[i][j] = dp[i-1][j]
if j >= w[i-1] && dp[i-1][j-w[i-1]]+v[i-1] > dp[i][j] {
dp[i][j] = dp[i-1][j-w[i-1]] + v[i-1]
}
}
}
r := 0
for i := 0; i <= W; i++ {
if dp[n][i] > r {
r = dp[n][i]
}
}
return r
}空间复杂度可以从O(NW)降低到O(W)，使用的是动态规划最常规的方案，滚动数组，注意复值的顺序，应该从数组尾端到头部赋值，代码如下：
func knapsack01D2(v []int, w []int, W int) int {
defer time_cost(time.Now(), "knapsack01D")
n := len(v)
dp := make([]int, W+1)
for j := 0; j <= W; j++ {
dp[j] = 0
}
for i := 1; i <= n; i++ {
for j := W; j >= w[i-1]; j-- {
if dp[j-w[i-1]]+v[i-1] > dp[j] {
dp[j] = dp[j-w[i-1]] + v[i-1]
}
}
}
r := 0
for j := 0; j <= W; j++ {
if dp[j] > r {
r = dp[j]
}
}
return r
}性能测试的benchmark
虽然上述3种解法都是可以work的，但是在性能上差别颇大，并且解法1在物品数量N<10时(W为10^5~10^6)，耗时较动态规划和记忆化递归更小，但是随着N的变大，特别是N>20开始，极速衰减性能（果然和理论值匹配），具体benchmark性能图表如下：
结束
到这里，对经典0-1背包问题的讨论暂告一个段落，可以看到0-1背包作为一个NPC问题，算法时间复杂度还是比较高的，所以一般的搜索组合算法，现在在物品数量>20时，在实际工作中是不太可行的，这个递归搜索的代码实现，唯一的优势是，代码简单易懂。但到了这里，还是不够，我后面也想在深入思考下，0-1背包问题的2个变种问题，即unbounded背包和bounded背包，这两个问题会更复杂些，但基于0-1背包问题的讨论基础上，或许会更容易理解。
1
555