わたしの部屋

2.1 策略一：价值最大优先#

每次优先选择价值最大的物品。

• 反例：有三个物品，分别为 $A$(重量9, 价值10)、$B$(重量5, 价值8)、$C$(重量5, 价值8)。
• 贪心选择：优先装入价值最大的 $A$，此时剩余容量为 $1$，无法再装入其他物品。总价值为 $10$。
• 全局最优：放弃 $A$，选择装入 $B$ 和 $C$。总重量为 $5 + 5 = 10 \le 10$，总价值为 $8 + 8 = 16$。
• 结论：价值最大优先策略失败。

2.2 策略二：重量最小优先#

每次优先选择重量最小的物品。

• 反例：有三个物品，分别为 $A$(重量1, 价值1)、$B$(重量5, 价值10)、$C$(重量5, 价值10)。
• 贪心选择：优先装入重量最小的 $A$，剩余容量为 $9$。接下来只能在 $B$ 和 $C$ 中选择一个装入。总价值为 $1 + 10 = 11$。
• 全局最优：放弃 $A$，选择装入 $B$ 和 $C$。总重量为 $5 + 5 = 10 \le 10$，总价值为 $10 + 10 = 20$。
• 结论：重量最小优先策略失败。

2.3 策略三：价值密度优先#

每次优先选择单位重量价值最高，即 $v_i/w_i$ 最大的物品。

• 反例：假设背包容量 $W = 8$。有三个物品，分别为 $A$(重量1, 价值3, 密度3.0)、$B$(重量4, 价值10, 密度2.5)、$C$(重量4, 价值10, 密度2.5)。
• 贪心选择：优先装入密度最高的 $A$，剩余容量为 $7$。接着只能在 $B$ 和 $C$ 中选择一个装入，总重量为 $1 + 4 = 5 \le 8$，总价值为 $3 + 10 = 13$。
• 全局最优：放弃 $A$，选择装入 $B$ 和 $C$。总重量为 $4 + 4 = 8 \le 8$，总价值为 $10 + 10 = 20$。
• 结论：价值密度优先策略同样失败。

这些策略失效的根源在于物品不可分割。局部最优可能占掉关键容量，使后续更优组合无法装入，所以需要能保证全局最优的解法。

3.1 解空间与暴力搜索#

对于 $n$ 个物品，每个物品有“装”与“不装”两种状态，其解空间可以用一棵二叉子集树表示。在没有约束的情况下，这棵树共有 $2^n$ 个叶子节点。

以下是 $n=3$ 时的子集树结构：

最朴素的 DFS 会遍历整棵子集树，检查每一个叶子节点的总重量是否超重，并记录合法解中的最大价值。其时间复杂度为 $O(2^n)$。

3.2 为什么需要剪枝#

当 $n$ 较大时，遍历 $2^n$ 种组合不可行。

剪枝的思路是：如果当前分支不可能产生比已知最优解更好的结果，就停止探索，回退到上一个决策节点。

剪枝分为两种：

1. 可行性剪枝：若装入当前物品导致当前总重量超过了背包容量 $W$，直接剪枝。
2. 限界剪枝：若“当前价值 + 剩余物品价值上界”仍不超过已知最优值，直接剪枝。

可行性剪枝很好判断，限界剪枝的关键在于：如何给一个尚未搜索完的分支估算“最多还能拿到多少价值”。

3.3 什么是 UB#

在搜索树的某个节点上，设：

• $i$：下一个要决策的物品下标；
• $cw$：当前已经装入的总重量；
• $cv$：当前已经装入的总价值；
• $best$：目前已经找到的最好合法解。

$UB$ 是这个节点的 Upper Bound，价值上界。它不是当前价值，而是从当前节点继续向下搜索时，理论上可能达到的最大总价值的乐观估计。

如果某个节点的 $UB \le best$，说明这个分支即使按最乐观方式估计，也无法超过当前最优解。此时可以剪掉整棵子树。

如何理解 UB

把 $UB$ 想成“这个分支的最高天花板”。

假设当前已经找到一个合法方案，价值 $best = 19$。现在搜索到另一个分支，当前价值是 $6$，把剩余容量按分数背包的最乐观方式填满后，最多也只能到 $UB = 16$。

这说明这个分支无论继续怎么选，都不可能超过 $19$。继续搜索只会浪费时间，因此可以直接剪掉。

3.4 用分数背包计算 UB#

0-1 背包要求物品要么完整装入，要么不装。

为了得到一个乐观上界，可以临时放宽限制：允许物品按比例切开装入。这就是分数背包。

分数背包的可选范围比 0-1 背包更大，因此它算出的价值不会小于真实的 0-1 最优值。用它作为 $UB$ 是安全的：上界可能偏高，但不能偏低。

在节点 $(i, cw, cv)$ 上，$UB$ 的计算步骤为：

1. 计算剩余可用容量 $rem = W - cw$。
2. 将尚未决策的物品（从 $i$ 到 $n-1$）按照价值密度降序依次整件装入。
3. 如果遇到某件物品完整装不下，则允许切开，只装入剩余容量能容纳的比例。
4. 累计 $cv$、整件装入的价值、切分装入的价值，得到当前节点的 $UB$。

用后文的统一示例计算根节点上界。背包容量 $W = 10$，物品已按价值密度降序排列：

根节点状态为 $(i=0, cw=0, cv=0)$。按分数背包估算：

1. 装入物品 1，价值 $6$，剩余容量 $8$。
2. 装入物品 2，价值 $10$，剩余容量 $3$。
3. 物品 3 重量为 $4$，完整装不下；切入 $3/4$ 个物品 3，得到价值 $7 \times \frac{3}{4} = 5.25$。

所以根节点的价值上界为：

这个 $21.25$ 不是合法答案，因为 0-1 背包不能切开物品。

它只表示：从根节点继续搜索，真实最优值不会超过 $21.25$。

若后续已经找到 $best = 19$，而某个分支的 $UB = 18$，则该分支不可能产生更优解，可以剪枝。

4.1 整体搜索树演示#

继续使用上一节的示例：$n = 4$，$W = 10$，物品已按价值密度降序排列。

图中使用的记号如下：

• $cw$ 表示当前已经装入的总重量；
• $cv$ 表示当前已经装入的总价值；
• $UB$ 表示当前节点的总价值上界，不是当前价值；
• 边上的“装1 / 不装1”使用 1-based 物品编号，便于阅读。

第一张图只展示 DFS 如何沿着“优先尝试装入”的路径找到 $best = 19$。

DFS 先尝试“装1 -> 装2 -> 装3”。

由于 $cw + w_3 = 11 > 10$，装入物品 3 会超重，因此转向“不装3”。

随后继续尝试“装4”，得到合法解 $\{1, 2, 4\}$，更新 $best = 19$。

第二张图展示 $best = 19$ 之后的回溯收尾。

此时只需要检查尚未展开的分支入口：如果入口节点的 $UB$ 已经小于 $best$，整棵子树都可以跳过。

回溯过程如下：

1. “不装4”已经是叶子节点，当前价值 $cv = 16 < best(19)$，不更新最优解。

2. “不装2”的状态为 $(i=2, cw=2, cv=6)$。

   这里的 $i$ 表示下一个要决策的物品下标，代码中使用 0-based 下标。从物品 3 起做分数贪心，$UB = 6 + 7 + 3 = 16 < best(19)$，整棵子树剪掉。

3. “不装1”的状态为 $(i=1, cw=0, cv=0)$。

   从物品 2 起做分数贪心，$UB = 10 + 7 + 1 = 18 < best(19)$，整棵子树剪掉。

有了前两张图的铺垫，再回看整棵搜索树会更清楚。

下面这张图保留分支关系和关键结果。颜色含义如下：

• 蓝色：实际搜索路径。
• 绿色：更新最优解。
• 红色：超重剪枝。
• 橙色：限界剪枝。
• 灰色：因为祖先节点被剪枝而没有继续访问的子树。

所有可产生更优解的分支都已处理完，算法结束，最优解为 $19$。

4.2 Java 实现#

1
public class KnapsackBacktrack {
2
    private static int[] w, v;
3
    private static int W, n, best;
4

5
    public static int solve(int[] weight, int[] value, int capacity) {
6
        w = weight; v = value; W = capacity; n = w.length;
7
        best = 0;
8
        backtrack(0, 0, 0);
9
        return best;
10
    }
11

12
    private static void backtrack(int i, int cw, int cv) {
13
        if (i == n) {
14
            if (cv > best) best = cv;
15
            return;
16
        }
17
        // 限界剪枝：如果当前期望能达到的最大价值上限都不超过已知最优解，则剪枝
18
        if (cv + fractionalUB(i, cw) <= best) return;
19

20
        // 可行性剪枝：只在不超过容量限制的前提下装入物品
21
        if (cw + w[i] <= W) {
22
            backtrack(i + 1, cw + w[i], cv + v[i]); // 可行分支
23
        }
24
        backtrack(i + 1, cw, cv); // 不装分支
25
    }
26

27
    // 分数背包上界函数
28
    private static double fractionalUB(int i, int cw) {
29
        double ub = 0;
30
        int rem = W - cw;
31
        for (int k = i; k < n && rem > 0; k++) {
32
            if (w[k] <= rem) { rem -= w[k]; ub += v[k]; }
33
            else { ub += (double) v[k] / w[k] * rem; break; }
34
        }
35
        return ub;
36
    }
37

38
    public static void main(String[] args) {
39
        int[] w = {2, 5, 4, 3};
40
        int[] v = {6, 10, 7, 3};
41
        int W = 10;
42
        System.out.println("最大价值 = " + solve(w, v, W));
43
    }
44
}

运行输出：

1
最大价值 = 19

5.1 状态定义#

动态规划适用于背包容量 $W$ 为非负整数的场景。它不再沿着搜索树试探每条路径，而是把已经算过的子问题保存下来。

定义：

$f[i][j]$ 表示：只考虑前 $i$ 个物品，在背包容量为 $j$ 时能获得的最大价值。

那么原问题的答案就是：

边界也很自然：

• $f[0][j] = 0$：没有物品可选，价值只能是 0。
• $f[i][0] = 0$：容量为 0，什么也装不下。

5.2 状态转移#

对于第 $i$ 个物品，只有两种选择：不装，或者装。

不装第 $i$ 个物品：

装第 $i$ 个物品，前提是容量够，即 $j \ge w_i$。装入后剩余容量为 $j-w_i$，总价值为：

所以转移方程是：

用统一示例算一个格子：$f[2][7]$。

此时只考虑前 2 个物品，容量为 $7$。物品 2 的重量为 $5$，价值为 $10$。

• 不装物品 2：$f[1][7] = 6$。
• 装物品 2：$f[1][2] + 10 = 6 + 10 = 16$。

取较大值：

这个格子的依赖关系如下：

这就是动态规划的关键：每个格子只从上一行取结果，避免重复枚举同一批选择。

5.3 二维 DP 写法#

代码中的物品数组是 0-based，因此第 $i$ 个物品对应 w[i - 1] 和 v[i - 1]。

1
public class KnapsackDP {
2
    public static int solve(int[] w, int[] v, int W) {
3
        int n = w.length;
4
        int[][] f = new int[n + 1][W + 1];
5
        for (int i = 1; i <= n; i++) {
6
            for (int j = 0; j <= W; j++) {
7
                f[i][j] = f[i - 1][j];
8
                if (j >= w[i - 1]) {
9
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - w[i - 1]] + v[i - 1]);
10
                }
11
            }
12
        }
13

14
        // 逆向递推恢复最优解路径
15
        System.out.print("装入物品的决策路径：{ ");
16
        int j = W;
17
        for (int i = n; i >= 1; i--) {
18
            if (f[i][j] != f[i - 1][j]) {
19
                System.out.print(i + " ");
20
                j -= w[i - 1];
21
            }
22
        }
23
        System.out.println("}");
24

25
        return f[n][W];
26
    }
27

28
    public static void main(String[] args) {
29
        int[] w = {2, 5, 4, 3};
30
        int[] v = {6, 10, 7, 3};
31
        int W = 10;
32
        System.out.println("最大价值 = " + solve(w, v, W));
33
    }
34
}

运行输出：

1
装入物品的决策路径：{ 4 2 1 }
2
最大价值 = 19

5.4 一维 DP 优化#

二维 DP 中，$f[i][j]$ 只依赖上一行。因此可以把表压缩成一维数组：

$f[j]$ 表示当前已经处理过若干物品后，容量为 $j$ 时的最大价值。

1
int[] f = new int[W + 1];
2
for (int i = 0; i < n; i++) {
3
    for (int j = W; j >= w[i]; j--) {
4
        f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
5
    }
6
}

为什么容量要倒序遍历

这里最关键的是容量要倒序遍历。

flowchart RL classDef cell fill:#eff6ff,stroke:#3b82f6,stroke-width:1.5px,font-family:Inter; classDef warn fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,font-family:Inter; J10["dp[10]"]:::cell --> J9["dp[9]"]:::cell --> J8["dp[8]"]:::cell --> J7["..."]:::cell --> JW["dp[w]"]:::cell N["容量从大到小更新<br>保证 dp[j-w] 仍来自上一轮"]:::warn J10 -.-> N

如果从左到右更新，$f[j - w_i]$ 可能已经在当前这一轮被物品 $i$ 更新过，相当于同一个物品被重复使用。倒序遍历时，$f[j - w_i]$ 仍是上一轮物品留下的状态，可以保证当前物品最多只选一次。

一句话记忆：

1
0-1 背包：容量倒序
2
完全背包：容量正序

5.5 如何恢复最优方案#

如果需要恢复具体选择，可以从 $f[n][W]$ 反向走回去：

• 若 $f[i][j] == f[i-1][j]$，可以沿“不选物品 $i$”继续。
• 若 $f[i][j] \ne f[i-1][j]$，当前恢复路径选择了物品 $i$，然后跳到 $f[i-1][j-w_i]$。

统一示例中从 $f[4][10] = 19$ 逆推，可以得到一组最优方案：选择物品 $\{1, 2, 4\}$。若存在并列最优解，恢复路径可能不止一条。

6.1 基本思想#

回溯法使用 DFS，先沿一条路径走到底，再回头处理其他分支。分支限界法换一种顺序：把所有待扩展节点放进优先队列，每次选择 $UB$ 最大的节点扩展。

两者都会使用 $UB$ 剪枝，但侧重点不同：

• 回溯法：$UB$ 主要用于判断当前 DFS 分支要不要剪掉。
• 分支限界法：$UB$ 不仅用于剪枝，还用于决定下一个扩展哪个活节点。

所以，分支限界法不是换了一种上界计算方式，而是换了一种搜索顺序：从“深度优先”改为“最有希望的节点优先”。

这里的 $UB$ 仍然是前文讲过的分数背包上界。它表示“从当前节点继续搜索，理论上最多能达到多少价值”。

分支限界法的核心规则很简单：

• 优先扩展：优先队列每次弹出 $UB$ 最大的活节点。
• 限界剪枝：若某个节点的 $UB \le best$，说明它不可能产生更优解，整棵子树可以跳过。

下面先看一个局部例子。

根节点展开后，队列里有两个活节点：

• 装1 的 $UB = 21.25$。
• 不装1 的 $UB = 18.00$。

分支限界法会先扩展 $UB$ 更大的 装1。

6.2 队列演化推演#

继续使用统一示例。下面按步骤展示优先队列如何变化。

颜色含义如下：

• 黄色：当前出队并扩展的节点。
• 蓝色：仍在队列中等待的节点。
• 橙色：因为 $UB \le best$ 不入队或被剪掉。
• 红色：超重剪枝。

6.3 Java 实现#

1
import java.util.PriorityQueue;
2

3
public class KnapsackBB {
4
    private static int[] w, v;
5
    private static int W, n;
6

7
    // 活节点：优先队列比较器，ub 越大越优先扩展
8
    private static class Node implements Comparable<Node> {
9
        int i, cw, cv;
10
        double ub;
11
        Node(int i, int cw, int cv, double ub) {
12
            this.i = i; this.cw = cw; this.cv = cv; this.ub = ub;
13
        }
14
        public int compareTo(Node o) {
15
            return Double.compare(o.ub, this.ub);
16
        }
17
    }
18

19
    public static int solve(int[] weight, int[] value, int capacity) {
20
        w = weight; v = value; W = capacity; n = w.length;
21
        PriorityQueue<Node> pq = new PriorityQueue<>();
22
        int best = 0;
23
        pq.offer(new Node(0, 0, 0, fractionalUB(0, 0)));
24

25
        while (!pq.isEmpty()) {
26
            Node x = pq.poll();
27

28
            // 限界剪枝：如果当前出队节点的上限都比不上当前已知最优，则其子代也无希望
29
            if (x.ub <= best) continue;
30

31
            // 到达叶子节点
32
            if (x.i == n) {
33
                if (x.cv > best) best = x.cv;
34
                continue;
35
            }
36
            int i = x.i;
37

38
            // 分支 1：装入物品 i（必须满足重量约束）
39
            if (x.cw + w[i] <= W) {
40
                int ncw = x.cw + w[i], ncv = x.cv + v[i];
41
                double ub = ncv + fractionalUB(i + 1, ncw);
42
                if (ncv > best) best = ncv;       // 更新当前最好可行值
43
                if (ub > best) {
44
                    pq.offer(new Node(i + 1, ncw, ncv, ub));
45
                }
46
            }
47
            // 分支 2：不装物品 i
48
            double sub = x.cv + fractionalUB(i + 1, x.cw);
49
            if (sub > best) {
50
                pq.offer(new Node(i + 1, x.cw, x.cv, sub));
51
            }
52
        }
53
        return best;
54
    }
55

56
    private static double fractionalUB(int i, int cw) {
57
        double ub = 0;
58
        int rem = W - cw;
59
        for (int k = i; k < n && rem > 0; k++) {
60
            if (w[k] <= rem) { rem -= w[k]; ub += v[k]; }
61
            else { ub += (double) v[k] / w[k] * rem; break; }
62
        }
63
        return ub;
64
    }
65

66
    public static void main(String[] args) {
67
        int[] w = {2, 5, 4, 3};
68
        int[] v = {6, 10, 7, 3};
69
        int W = 10;
70
        System.out.println("最大价值 = " + solve(w, v, W));
71
    }
72
}

运行输出：

1
最大价值 = 19

10.1 伪多项式时间的奥秘#

尽管如此，动态规划能以 $O(nW)$ 求得最优值。为什么这没有和 NP-Hard 的结论冲突？

原因在于：$O(nW)$ 是伪多项式时间。 在计算机复杂度理论中，输入规模是以表示输入所需的二进制位数来度量的：

• 物品数 $n$ 的值增长，其输入长度呈线性增长。
• 背包容量 $W$ 的值增长，其输入长度仅呈对数 $\log_2(W)$ 增长。

这意味着，容量 $W$ 翻倍时，输入长度只增加 1 bit，但动态规划时间会直接翻倍。当 $W = 10^9$ 时，即使 $n=10$，动态规划也要处理 $10^{10}$ 个状态，可能比指数搜索还慢。 因此，动态规划只有在 $W$ 的值被限制在 $n$ 的多项式级别内时才是高效的。若 $W$ 的值呈指数增长或为浮点数，通常就需要考虑分支限界、按价值维度动态规划，或者使用近似算法（如 FPTAS）来求取近似最优解。