01背包
问题描述
有 $n$ 个物品，第 $k$ （$k=1,2,3,\cdots,n$）个物品有一个重量 $weight(k)$ 和一个价值 $value(k)$ 。现在有一个小偷，他有一个容量为 $W$ 的背包，问小偷如何选择物品放入背包，使得背包中的总价值最大。
状态定义
我们假设小偷从第 $k$ 个物品开始往前偷（为了方便，我们假设 $k$ 从 $1$ 开始而不是 $0$ ），当前的背包容量为 $w$ ，此时能偷的最大价值为 $dp(k,w)$ 。那么有两种情况：
-
如果 $w<weight\left( k \right) $，代表背包放不下第 $k$ 个物品，此时 $dp(k,w)=dp(k-1,w)$ 。
-
如果 $w\geqslant weight\left( k \right) $，代表背包可以放下第 $k$ 个物品，此时：
- 可以偷这个物品：$dp\left( k,w \right) =dp\left( k-1,w-weight\left( k \right) \right) +value\left( k \right) $
- 也可以不偷：$dp\left( k,w \right) =dp\left( k-1,w \right) $
因此，$dp\left( k,w \right) =max\left( 偷, 不偷 \right) $
递归+记忆化搜索实现
我们可以用最直观的方式，用递归+记忆化搜索实现：
1public class Solution {
2 private static Integer[][] memo;
3 // 用Integer数组而不用int数组，是因为int数组默认初始化为0，而Integer数组默认初始化为null
4
5 public static int knapsack(int[] weight, int[] value, int W) {
6 int n = weight.length;
7 memo = new Integer[n + 1][W + 1];
8 return dfs(weight, value, W, n);
9 }
10
11 private static int dfs(int[] weight, int[] value, int W, int k) {
12 if (k == 0) return 0;
13 if (memo[k][W] != null) return memo[k][W];
14 if (W < weight[k - 1]) {
15 memo[k][W] = dfs(weight, value, W, k - 1);
16 } else {
17 memo[k][W] = Math.max(dfs(weight, value, W, k - 1), dfs(weight, value, W - weight[k - 1], k - 1) + value[k - 1]);
18 }
19 return memo[k][W];
20 }
21
22 public static void main(String[] args) {
23 int[] weight = {2, 3, 4, 5};
24 int[] value = {3, 4, 5, 6};
25 int W = 5;
26 System.out.println(knapsack(weight, value, W));
27 }
28}
二维数组实现
1public int knapsack(int[] weight, int[] value, int W) {
2 int n = weight.length;
3 int[][] dp = new int[n + 1][W + 1];
4 // Java 默认初始化数组为 0
5
6 // 注意，k对应前面假设中的1,2,...，对应weight和value数组中的k-1下标
7 // 定义中weight(1)对应weight[0]，value(1)对应value[0]
8 for (int k = 1; k <= n; k++) {
9 for (int w = 1; w <= W; w++) {
10 if (w < weight[k - 1]) {
11 dp[k][w] = dp[k - 1][w];
12 } else {
13 dp[k][w] = Math.max(dp[k - 1][w], dp[k - 1][w - weight[k - 1]] + value[k - 1]);
14 }
15 }
16 }
17
18 return dp[n][W];
19}
假设我们有5个物品，重量和价值分别如下：
| k | 重量 | 价值 |
|---|---|---|
| 1 | 2 | 1 |
| 2 | 3 | 2 |
| 3 | 4 | 3 |
| 4 | 5 | 2 |
| 5 | 6 | 4 |
我们可以看一下dp数组的每个值：
| k\w | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 0 | 1 | 2 | 2 | 3 | 3 | 3 |
| 3 | 0 | 1 | 2 | 3 | 3 | 4 | 5 |
| 4 | 0 | 1 | 2 | 3 | 3 | 4 | 5 |
| 5 | 0 | 1 | 2 | 3 | 3 | 4 | 5 |
一维数组实现
一维数组实现主要是为了节省空间，并没有减少时间复杂度。我们把k消去，只留下w，这样一来，二维数组实现需要 $O(nW)$ 的空间，而一维数组实现只需要 $O(W)$ 的空间。
1public int knapsack(int[] weight, int[] value, int W) {
2 int n = weight.length;
3 int[] dp = new int[W + 1];
4 // Java 默认初始化数组为 0
5
6 for (int k = 1; k <= n; k++) {
7 for (int w = W; w >= weight[k - 1]; w--) {
8 // w >= weight[k - 1]：当背包可以放下第k个物品时才更新
9 // 内层应该从后往前遍历，因为dp[w]依赖于dp[w - weight[k - 1]]，如果从前往后遍历，dp[w - weight[k - 1]]会被先更新，导致dp[w]的结果不正确
10 // dp[w] (更新前) 相当于二维 DP 中的 dp[k-1][w] (不放物品 k 的情况)
11 // dp[w - weights[k]] (更新前) 相当于二维 DP 中的 dp[k-1][w - weights[k]]
12 dp[w] = Math.max(dp[w], dp[w - weight[k - 1]] + value[k - 1]);
13 }
14 // 经过内层 w 循环后，dp 数组已经更新，
15 // 此时 dp[w] 存储的就是考虑前 k 个物品、容量为 w 的最大价值
16 }
17
18 // 或者可以简写成这样，方便记忆：
19 for (int k = 0; k < n; k++) {
20 for (int w = W; w >= weight[k]; w--) {
21 dp[w] = Math.max(dp[w], dp[w - weight[k]] + value[k]);
22 }
23 }
24
25 return dp[W];
26}
完全背包
问题描述
有 $n$ 个物品，第 $k$ （$k=1,2,3,\cdots,n$）个物品有一个重量 $weight(k)$ 和一个价值 $value(k)$ 。现在有一个小偷，他有一个容量为 $W$ 的背包，每个物品可以选择无数次放入背包，问小偷如何选择物品放入背包，使得背包中的总价值最大。
状态定义
这个问题和01背包问题很相似，区别在于每个物品可以选择无数次放入背包，即允许重复选择。因此，我们只需要更改“放”的逻辑，从“放一个”改为“放多个”。
我们假设小偷从第 $k$ 个物品开始往前偷（为了方便，我们假设 $k$ 从 $1$ 开始而不是 $0$ ），当前的背包容量为 $w$ ，此时能偷的最大价值为 $dp(k,w)$ 。那么有两种情况：
-
如果 $w<weight\left( k \right) $，代表背包放不下第 $k$ 个物品，此时 $dp(k,w)=dp(k-1,w)$ 。
-
如果 $w\geqslant weight\left( k \right) $，代表背包可以放下第 $k$ 个物品，此时：
- 可以偷这个物品：$dp\left( k,w \right) =dp\left( k,w-weight\left( k \right) \right) +value\left( k \right) $（唯一区别：dp的第一个参数使用k而不是k-1，表示当前物品k可以被重复选择）
- 也可以不偷：$dp\left( k,w \right) =dp\left( k-1,w \right) $
因此，$dp\left( k,w \right) =max\left( 偷, 不偷 \right) $
二维数组实现
1public int knapsack(int[] weight, int[] value, int W) {
2 int n = weight.length;
3 int[][] dp = new int[n + 1][W + 1];
4 // Java 默认初始化数组为 0
5
6 for (int k = 1; k <= n; k++) {
7 for (int w = 1; w <= W; w++) {
8 if (w < weight[k - 1]) {
9 dp[k][w] = dp[k - 1][w];
10 } else {
11 dp[k][w] = Math.max(dp[k - 1][w], dp[k][w - weight[k - 1]] + value[k - 1]);
12 }
13 }
14 }
15
16 return dp[n][W];
17}
一维数组实现
一维数组消去了k，只保留w，这样一来，其核心运算代码与01背包的一维数组实现完全相同，唯一不同的是内层遍历顺序从后往前变成了从前往后，来确保每个物品可以被多次选择。
1public int knapsack(int[] weight, int[] value, int W) {
2 int n = weight.length;
3 int[] dp = new int[W + 1];
4 // Java 默认初始化数组为 0
5 // 注意，k对应前面假设中的1,2,...，对应weight和value数组中的k-1下标
6 // 定义中weight(1)对应weight[0]，value(1)对应value[0]
7 for (int k = 1; k <= n; k++) {
8 for (int w = weight[k - 1]; w <= W; w++) {
9 dp[w] = Math.max(dp[w], dp[w - weight[k - 1]] + value[k - 1]);
10 }
11 }
12
13 // 或者可以简写成这样，方便记忆：
14 for (int k = 0; k < n; k++) {
15 for (int w = weight[k]; w <= W; w++) {
16 dp[w] = Math.max(dp[w], dp[w - weight[k]] + value[k]);
17 }
18 }
19
20 return dp[W];
21}
多重背包
问题描述
有 $n$ 个物品，第 $k$ （$k=1,2,3,\cdots,n$）个物品有一个重量 $weight(k)$ 和一个价值 $value(k)$ 。现在有一个小偷，他有一个容量为 $W$ 的背包，每个物品放入背包的次数不超过$count(k)$，问小偷如何选择物品放入背包，使得背包中的总价值最大。
这个问题其实就是分组。最直观的方法是把每个相同的物品都直接看作一个独立的物品（暴力拆解），然后使用01背包的解法。
暴力拆解
1public static int multipleBag(int[] weight, int[] value, int[] num, int W) {
2 int n = weight.length;
3 int[] dp = new int[W + 1];
4 // Java 默认初始化数组为 0
5
6 for (int k = 0; k < n; k++) {
7 for (int c = 1; c <= num[k]; c++) { // 拆成 num[k] 件物品
8 for (int w = W; w >= weight[k]; w--) {
9 dp[w] = Math.max(dp[w], dp[w - weight[k]] + value[k]);
10 }
11 }
12 }
13
14 return dp[W];
15}
这种暴力拆解的方法时间复杂度为 $O(nW\sum_{i=1}^{n}num[i])$ ，当数据量较大时，时间复杂度会非常高。
二进制拆解
二进制拆解的思路是将每个物品的个数拆成若干个2的幂次方，然后使用01背包的解法。依据一个事实：任何整数都可以表示成若干个2的幂次方之和，如13=1+4+8。
1public static int multipleBag(int[] weight, int[] value, int[] num, int W) {
2 int n = weight.length;
3 int[] dp = new int[W + 1];
4 // Java 默认初始化数组为 0
5
6 for (int k = 0; k < n; k++) {
7 int m = 1; // 用来生成1,2,4,8… 的“拆分基数”
8 int c = num[k]; // 当前物品的个数
9 while (c > 0) {
10 int count = Math.min(c, m); // 取c和m中较小者，避免拆分过多
11 int newWeight = weight[k] * count;
12 int newValue = value[k] * count;
13 // 标准01背包
14 for (int w = W; w >= newWeight; w--) {
15 dp[w] = Math.max(dp[w], dp[w - newWeight] + newValue);
16 }
17 c -= count; // 减去已经拆分出去的件数
18 m <<= 1; // 下一轮基数翻倍：1→2→4→8…
19 }
20 }
21
22 return dp[W];
23}
这种方法把每个物品的个数拆成了若干个2的幂次方，时间复杂度为 $O(nW\sum_{i=1}^{n}log(num[i]))$ ，大大降低了时间复杂度。
单调队列优化
单调队列优化的时间复杂度为 $O(nW)$ ，比暴力拆解和二进制拆解都要快。
1
2 /**
3 * 多重背包——单调队列优化
4 * @param weight 每种物品重量数组 w[i]
5 * @param value 每种物品价值数组 v[i]
6 * @param num 每种物品最大数量数组 c[i]
7 * @param W 背包总容量
8 * @return 背包能装下的最大价值
9 */
10 public static int multipleBag(int[] weight, int[] value, int[] num, int W) {
11 int n = weight.length;
12 // dp[j] 表示当前考虑完若干物品后，容量恰好为 j 时的最大价值
13 int[] dp = new int[W + 1];
14
15 // 枚举每一类物品
16 for (int k = 0; k < n; k++) {
17 int w = weight[k], v = value[k], c = num[k];
18
19 // 对同一种物品，根据 j mod w 分成 w 条子序列
20 for (int r = 0; r < w; r++) {
21 // 维护一个双端队列，队列元素是索引 m，以及对应的 f(m) = dp_old[r + m*w] - m*v
22 Deque<Integer> deque = new ArrayDeque<>();
23
24 // m = 0,1,2,...；对应 j = r + m*w
25 // 我们需要遍历这一条“序列”上的所有 j
26 for (int j = r, m = 0; j <= W; j += w, m++) {
27 // 1) 计算当前点的 f(m)
28 int fm = dp[j] - m * v;
29
30 // 2) 将 fm 进队尾，保持队列单调递减（队头是最大）
31 while (!deque.isEmpty()) {
32 int mTail = deque.peekLast();
33 int fTail = dp[r + mTail * w] - mTail * v;
34 if (fTail <= fm) {
35 deque.pollLast();
36 } else {
37 break;
38 }
39 }
40 deque.offerLast(m);
41
42 // 3) 弹出过期元素（下标 < m - c）
43 if (deque.peekFirst() < m - c) {
44 deque.pollFirst();
45 }
46
47 // 4) 队头就是窗口 [m-c, m] 内最大的 f(u)
48 int bestM = deque.peekFirst();
49 int bestF = dp[r + bestM * w] - bestM * v;
50
51 // 5) 恢复成 dp_new[j]
52 dp[j] = bestF + m * v;
53 }
54 }
55 }
56
57 return dp[W];
58 }
我们的总体思路是：
dp[j]：表示“当前已经处理完第 0…k 类物品后，恰好装满容量 j 的最大价值”。- 对每一类物品
k，我们要用单调队列优化下面这个转移： $$ dp_{\text{new}}[j] = \max_{0 \le t \le c_k,; j - t w_k \ge 0} \bigl(dp_{\text{old}}[,j - t w_k,] + t,v_k\bigr). $$
首先按 “模 w” 分组，
1for (int r = 0; r < w; r++) {
2 // 序列：j = r, r+w, r+2w, …
3}
把所有容量 j 按 j % w == r 分成 w 条独立的序列，这样处理起来只需线性扫一遍。然后我们定义 f(m)，令
$$
m = \frac{j - r}{w},\quad
j = r + m,w;
$$
定义
$$ f(m) = dp_{\text{old}}[r + m,w] - m,v_k. $$
那么转移就变成
$$ dp_{\text{new}}[r + m,w] = \max_{m-c_k \le u \le m}\bigl(f(u)\bigr) + mv_k, $$
即在下标 u ∈ [m - c, m] 区间里取最大。
然后用单调队列维护窗口最大值。
- 队列存什么？ 存下标
u，真正的比较量是dp[r + u*w] - u*v。 - 进队（保持递减）：
1while (!deque.isEmpty() && f(tail) <= f(m)) deque.pollLast();
2deque.offerLast(m);
这样队头永远是窗口内最大的 f(u)。
- 出队过期：
1if (deque.peekFirst() < m - c) deque.pollFirst();
确保窗口大小不超过 c+1。
最后恢复 dp 新值，队头 bestM = deque.peekFirst()，对应最大 f(bestM)。
$$ dp[j] = f(\text{bestM}) + m,v = \bigl(dp_{\text{old}}[r + bestM,w] - bestM,v\bigr) + m,v. $$
这样优化后，时间复杂度为 $O(nW)$ 。