Videos
上期节目中我们对动态规划做了一个总结，这期节目我们来聊聊背包问题。
背包问题是一个NP-complete的组合优化问题，Search的方法需要O(2^N)时间才能获得最优解。而使用动态规划，我们可以在伪多项式（pseudo-polynomial time）时间内获得最优解。
0-1 Knapsack Problem 0-1背包问题
Problem
Given N items, w[i] is the weight of the i-th item and v[i] is value of the i-th item. Given a knapsack with capacity W. Maximize the total value. Each item can be use 0 or 1 time.
0-1背包问题的通常定义是：一共有N件物品，第i件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够获得的最大价值是多少？每件物品可以使用0次或者1次。
例子：
重量 w = [1, 1, 2, 2]
价值 v = [1, 3, 4, 5]
背包承重 W = 4
最大价值为9，可以选第1,2,4件物品，也可以选第3，4件物品；总重量为4，总价值为9。
动态规划的状态转移方程为：
|
1 |
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]) |
Solutions
Search
|
1 2 3 4 5 6 7 8 9 10 |
def knapsack01DFS(w, v, W): def dfs(s, cur_w, cur_v, ans): ans[0] = max(ans[0], cur_v) if s == N: return for i in range(s, N): if cur_w + w[i] <= W: dfs(i + 1, cur_w + w[i], cur_v + v[i], ans) ans = [0] dfs(0, 0, 0, ans) return ans[0] |
DP2
|
1 2 3 4 5 6 7 |
def knapsack01(w, v, W): dp = [[0] * (W + 1) for _ in range(N+1)] for i in range(1, N + 1): dp[i] = dp[i-1].clone() for j in range(w[i], W + 1): dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]) return max(dp[N]) |
DP1/tmp
|
1 2 3 4 5 6 7 8 |
def knapsack01R(w, v, W): dp = [0] * (W + 1) for i in range(0, N): tmp = list(dp) for j in range(w[i], W + 1): tmp[j] = max(tmp[j], dp[j - w[i]] + v[i]) dp = tmp return max(dp) |
DP1/push
|
1 2 3 4 5 6 |
def knapsack01R2(w, v, W): dp = [0] * (W + 1) for i in range(0, N): for j in range(W, w[i] - 1, -1): dp[j] = max(dp[j], dp[j - w[i]] + v[i]) return max(dp) |
DP1/pull
|
1 2 3 4 5 6 |
def knapsack01R1(w, v, W): dp = [0] * (W + 1) for i in range(0, N): for j in range(W - w[i], -1, -1): dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]) return max(dp) |
Unbounded Knapsack Problem 完全背包
完全背包、多重背包是常见的变形。和01背包的区别在于，完全背包每件物品可以使用无限多次，而多重背包每件物品最多可以使用n[i]次。两个问题都可以转换成01背包问题进行求解。
但是Naive的转换会大大增加时间复杂度：
完全背包：“复制”第i件物品到一共有 W/w[i] 件
多重背包：“复制”第i件物品到一共有 n[i] 件
然后直接调用01背包进行求解。
时间复杂度：
完全背包 O(Σ(W/w[i])*W)
多重背包 O(Σn[i]*W)
不难看出时间复杂度 = O(物品数量*背包承重)
背包承重是给定的，要降低运行时候，只有减少物品数量。但怎样才能减少总的物品数量呢？
这就涉及到二进制思想：任何一个正整数都可以用 (1, 2, 4, …, 2^K)的组合来表示。例如14 = 2 + 4 + 8。
原本需要放入14件相同的物品，现在只需要放入3件（重量和价值是原物品的2倍，4倍，8倍）。大幅降低了总的物品数量从而降低运行时间。
完全背包：对于第i件物品，我们只需要创建k = log(W/w[i])件虚拟物品即可。
每件虚拟物品的重量和价值为：1*(w[i], v[i]), 2*(w[i], v[i]), …, 2^k*(w[i], v[i])。
多重背包：对于第i件物品，我们只需要创建k + 1件虚拟物品即可，其中k = log(n[i])。
每件虚拟物品的重量和价值为：1*(w[i], v[i]), 2*(w[i], v[i]), …, 2^(k-1)*(w[i], v[i]), 以及 (n[i] – 2^k – 1) * (w[i], v[i])。
例如：n[i] = 14, k = 3, 虚拟物品的倍数为 1, 2, 4 和 7，这4个数组合可以组成1 ~ 14中的任何一个数，并且不会>14，即不超过n[i]。
二进制转换后直接调用01背包即可
时间复杂度：
完全背包 O(Σlog(W/w[i])*W)
多重背包 O(Σlog(n[i])*W)
空间复杂度 O(W)
其实完全背包和多重背包都可以在 O(NW)时间内完成，前者在视频中有讲到，后者属于超纲内容，以后有机会再和大家深入分享。
Bounded Knapsack Problem 多重背包
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment