0-1 背包问题（动态规划、回溯法、分支限界法）

一、什么是 0-1 背包问题#

给定 $n$ 个物品和一个容量为 $W$ 的背包。每个物品 $i$ 有其重量 $w_i$ 和价值 $v_i$ 。

每个物品要么整个装进背包（1），要么不装（0），不能只装入一部分。目标是在不超过背包最大容量 $W$ 的前提下，使背包中物品的总价值最大。

数学表达为：

\max \sum_{i=1}^{n} x_i v_i \quad \text{s.t.} \quad \sum_{i=1}^{n} x_i w_i \le W,\quad x_i \in \{0, 1\}

由于每个物品都面临“装”与“不装”两种选择， $n$ 个物品会形成约 $2^n$ 种组合。当 $n$ 较大时，直接枚举很快变得不可承受，因此需要更系统的搜索或递推算法。

二、为什么贪心算法不行#

初学者最容易想到贪心。先看三种直观策略为什么得不到全局最优解。

假设背包容量 $W = 10$ 。

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$ 时的子集树结构：

graph TD
    classDef node fill:#eff6ff,stroke:#3b82f6,stroke-width:1.5px,font-family:Inter;
    
    Root["开始"]:::node
    
    Y1["装物品1"]:::node
    N1["不装物品1"]:::node
    
    Y2_1["装物品2"]:::node
    N2_1["不装物品2"]:::node
    Y2_2["装物品2"]:::node
    N2_2["不装物品2"]:::node
    
    Y3_1["装物品3"]:::node
    N3_1["不装物品3"]:::node
    Y3_2["装物品3"]:::node
    N3_2["不装物品3"]:::node
    Y3_3["装物品3"]:::node
    N3_3["不装物品3"]:::node
    Y3_4["装物品3"]:::node
    N3_4["不装物品3"]:::node

    Root --> Y1
    Root --> N1
    Y1 --> Y2_1
    Y1 --> N2_1
    N1 --> Y2_2
    N1 --> N2_2
    Y2_1 --> Y3_1
    Y2_1 --> N3_1
    N2_1 --> Y3_2
    N2_1 --> N3_2
    Y2_2 --> Y3_3
    Y2_2 --> N3_3
    N2_2 --> Y3_4
    N2_2 --> N3_4

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

3.2 为什么需要剪枝#

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

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

剪枝分为两种：

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

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

3.3 什么是 UB#

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

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

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

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

3.4 用分数背包计算 UB#

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

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

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

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

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

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

物品 $i$	重量 $w_i$	价值 $v_i$	价值密度 $v_i/w_i$
1	2	6	3.00
2	5	10	2.00
3	4	7	1.75
4	3	3	1.00

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

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

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

UB = 0 + 6 + 10 + 5.25 = 21.25

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

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

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

四、回溯法#

有了 $UB$ ，就可以把暴力 DFS 改成带剪枝的回溯法。

4.1 整体搜索树演示#

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

图中使用的记号如下：

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

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

graph TD
    classDef root fill:#f8fafc,stroke:#64748b,stroke-width:2px,font-family:Inter;
    classDef path fill:#eff6ff,stroke:#2563eb,stroke-width:2px,font-family:Inter;
    classDef best fill:#ecfdf5,stroke:#059669,stroke-width:3px,font-family:Inter;
    classDef overweight fill:#fef2f2,stroke:#ef4444,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;

    R["根节点<br>UB=21.25"]:::root

    A["装1<br>cw=2, cv=6"]:::path
    B["装2<br>cw=7, cv=16"]:::path
    C["装3<br>cw=11 > 10"]:::overweight
    D["不装3<br>cw=7, cv=16"]:::path
    E["装4<br>cw=10, cv=19<br>best=19"]:::best

    R -->|先装1| A
    A -->|再装2| B
    B -->|尝试装3：超重| C
    B -->|改为不装3| D
    D -->|装4| E

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

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

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

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

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

graph TD
    classDef root fill:#f8fafc,stroke:#64748b,stroke-width:2px,font-family:Inter;
    classDef done fill:#ecfdf5,stroke:#059669,stroke-width:2px,font-family:Inter;
    classDef bound fill:#fff7ed,stroke:#f97316,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;
    classDef leaf fill:#f8fafc,stroke:#94a3b8,stroke-width:1.5px,font-family:Inter;

    R["已找到 best=19"]:::done

    A["不装4<br>cv=16<br>叶子：不更新"]:::leaf
    B["不装2<br>UB=16"]:::bound
    C["不装1<br>UB=18"]:::bound

    R -->|回溯到物品4| A
    R -->|回溯到物品2| B
    R -->|回溯到物品1| C

    B -.->|UB < best，剪掉子树| B1["后续选择不再展开"]:::bound
    C -.->|UB < best，剪掉子树| C1["后续选择不再展开"]:::bound

回溯过程如下：

“不装4”已经是叶子节点，当前价值 $cv = 16 < best(19)$ ，不更新最优解。
“不装2”的状态为 $(i=2, cw=2, cv=6)$ 。

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

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

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

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

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

graph TD
    classDef root fill:#f8fafc,stroke:#64748b,stroke-width:2px,font-family:Inter;
    classDef path fill:#eff6ff,stroke:#2563eb,stroke-width:2px,font-family:Inter;
    classDef best fill:#ecfdf5,stroke:#059669,stroke-width:3px,font-family:Inter;
    classDef overweight fill:#fef2f2,stroke:#ef4444,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;
    classDef bound fill:#fff7ed,stroke:#f97316,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;
    classDef leaf fill:#f8fafc,stroke:#94a3b8,stroke-width:1.5px,font-family:Inter;
    classDef skipped fill:#f3f4f6,stroke:#d1d5db,stroke-width:1px,color:#9ca3af,font-family:Inter;

    R["根<br>UB=21.25"]:::root

    A["装1<br>cw=2, cv=6"]:::path
    H["不装1<br>UB=18<br>剪枝"]:::bound

    B["装2<br>cw=7, cv=16"]:::path
    G["不装2<br>UB=16<br>剪枝"]:::bound

    C["装3<br>超重"]:::overweight
    D["不装3<br>cw=7, cv=16"]:::path

    E["装4<br>cv=19<br>best=19"]:::best
    F["不装4<br>cv=16<br>不更新"]:::leaf

    G1["装3"]:::skipped
    G2["不装3"]:::skipped
    G3["装4"]:::skipped
    G4["不装4"]:::skipped

    H1["装2"]:::skipped
    H2["不装2"]:::skipped
    H3["装3"]:::skipped
    H4["不装3"]:::skipped

    R -->|装1| A
    R -->|不装1| H

    A -->|装2| B
    A -->|不装2| G

    B -->|装3| C
    B -->|不装3| D

    D -->|装4| E
    D -->|不装4| F

    G -.->|未访问| G1
    G -.->|未访问| G2
    G2 -.->|未访问| G3
    G2 -.->|未访问| G4

    H -.->|未访问| H1
    H -.->|未访问| H2
    H2 -.->|未访问| H3
    H2 -.->|未访问| H4

所有可产生更优解的分支都已处理完，算法结束，最优解为 $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

五、动态规划#

回溯法即使有剪枝，最坏时间复杂度仍是 $O(2^n)$ 。动态规划通过记录子问题，消除重复计算。

动态规划的重点不是循环流程，而是每个状态从哪里来。先记住一句话：当前格子只从上一行的结果转移而来。

5.1 状态定义#

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

定义：

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

那么原问题的答案就是：

f[n][W]

边界也很自然：

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

5.2 状态转移#

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

不装第 $i$ 个物品：

f[i][j] = f[i-1][j]

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

f[i-1][j-w_i] + v_i

所以转移方程是：

f[i][j] = \begin{cases} f[i-1][j] & j < w_i \\ \max(f[i-1][j], f[i-1][j-w_i] + v_i) & j \ge w_i \end{cases}

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

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

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

取较大值：

f[2][7] = \max(6, 16) = 16

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

graph TD
    classDef current fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,font-family:Inter;
    classDef prev fill:#f8fafc,stroke:#cbd5e1,stroke-width:1.5px,font-family:Inter;
    classDef choose fill:#eff6ff,stroke:#3b82f6,stroke-width:1.5px,font-family:Inter;
    classDef result fill:#ecfdf5,stroke:#10b981,stroke-width:2px,font-family:Inter;

    A["当前格<br>f[2][7]"]:::current
    B["不装物品2<br>看 f[1][7] = 6"]:::prev
    C["装物品2<br>看 f[1][2] + 10 = 16"]:::choose
    D["取最大值<br>f[2][7] = 16"]:::result

    A --> B
    A --> C
    B --> D
    C --> D

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

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。

graph TD
    classDef root fill:#f8fafc,stroke:#64748b,stroke-width:2px,font-family:Inter;
    classDef active fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,font-family:Inter;
    classDef wait fill:#eff6ff,stroke:#3b82f6,stroke-width:1.5px,font-family:Inter;

    R["根节点<br>UB=21.25"]:::root
    A["装1<br>UB=21.25<br>下一步扩展"]:::active
    B["不装1<br>UB=18.00<br>暂存队列"]:::wait

    R -->|装1| A
    R -->|不装1| B

6.2 队列演化推演#

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

颜色含义如下：

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

第一步：扩展根节点#

初始时只有根节点。扩展根节点后生成两个分支：装1 和 不装1。

因为 装1 的 $UB$ 更大，下一步会优先扩展它。

graph TD
    classDef active fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,font-family:Inter;
    classDef queue fill:#eff6ff,stroke:#3b82f6,stroke-width:1.5px,font-family:Inter;
    classDef root fill:#f8fafc,stroke:#64748b,stroke-width:2px,font-family:Inter;

    R["root<br>UB=21.25<br>出队扩展"]:::active
    A["装1<br>UB=21.25<br>队首"]:::queue
    B["不装1<br>UB=18.00<br>等待"]:::queue

    R -->|装1| A
    R -->|不装1| B

此时 $best$ 从 $0$ 更新为 $6$ ，队列为：装1(21.25)、不装1(18.00)。

第二步：扩展 `装1`#

扩展 装1 后，装2 的上界仍为 $21.25$ ，继续排在队首；不装2 的上界为 $16.00$ ，此时 $best$ 已更新为 $16$ ，所以它不会入队。

graph TD
    classDef active fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,font-family:Inter;
    classDef queue fill:#eff6ff,stroke:#3b82f6,stroke-width:1.5px,font-family:Inter;
    classDef bound fill:#fff7ed,stroke:#f97316,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;
    classDef wait fill:#f8fafc,stroke:#94a3b8,stroke-width:1.5px,font-family:Inter;

    A["装1<br>UB=21.25<br>出队扩展"]:::active
    B["装2<br>UB=21.25<br>队首"]:::queue
    C["不装2<br>UB=16.00<br>不入队"]:::bound
    D["不装1<br>UB=18.00<br>等待"]:::wait

    A -->|装2| B
    A -->|不装2| C
    D -.->|仍在队列| B

此时 $best$ 从 $6$ 更新为 $16$ ，队列为：装1,2(21.25)、不装1(18.00)。

第三步：扩展 `装1,2`#

扩展 装1,2 时，尝试装入物品 3 会超重，因此直接剪掉；不装物品 3 后得到节点 装1,2,不装3，它的 $UB=19.00$ ，仍然大于当前 $best=16$ ，所以入队并成为队首。

graph TD
    classDef active fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,font-family:Inter;
    classDef queue fill:#eff6ff,stroke:#3b82f6,stroke-width:1.5px,font-family:Inter;
    classDef overweight fill:#fef2f2,stroke:#ef4444,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;
    classDef wait fill:#f8fafc,stroke:#94a3b8,stroke-width:1.5px,font-family:Inter;

    A["装1,2<br>UB=21.25<br>出队扩展"]:::active
    B["装3<br>cw=11>10<br>超重"]:::overweight
    C["不装3<br>UB=19.00<br>队首"]:::queue
    D["不装1<br>UB=18.00<br>等待"]:::wait

    A -->|装3| B
    A -->|不装3| C
    D -.->|仍在队列| C

此时 $best$ 仍为 $16$ ，队列为：装1,2,不装3(19.00)、不装1(18.00)。

第四步：扩展 `装1,2,不装3`#

扩展 装1,2,不装3 时，装入物品 4 得到合法解，价值为 $19$ ，于是更新 $best=19$ 。不装物品 4 的上界只有 $16.00$ ，不再入队。

graph TD
    classDef active fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,font-family:Inter;
    classDef best fill:#ecfdf5,stroke:#10b981,stroke-width:3px,font-family:Inter;
    classDef bound fill:#fff7ed,stroke:#f97316,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;
    classDef wait fill:#f8fafc,stroke:#94a3b8,stroke-width:1.5px,font-family:Inter;

    A["装1,2,不装3<br>UB=19.00<br>出队扩展"]:::active
    B["装4<br>cv=19<br>best=19"]:::best
    C["不装4<br>UB=16.00<br>不入队"]:::bound
    D["不装1<br>UB=18.00<br>等待"]:::wait

    A -->|装4| B
    A -->|不装4| C
    D -.->|仍在队列| B

此时队列只剩 不装1(18.00)。

第五步：剪枝收尾#

最后弹出 不装1。

它的 $UB = 18.00$ ，已经不可能超过 $best = 19$ ，直接剪枝。队列清空，算法结束。

graph TD
    classDef best fill:#ecfdf5,stroke:#10b981,stroke-width:3px,font-family:Inter;
    classDef bound fill:#fff7ed,stroke:#f97316,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;

    A["当前 best=19"]:::best
    B["不装1<br>UB=18.00<br>剪枝"]:::bound

    A -->|UB <= best| B

把五个步骤合在一起，可以得到整棵搜索树。颜色含义如下：

黄色：按 $UB$ 优先扩展的路径。
蓝色：曾进入优先队列等待的节点。
绿色：更新 $best = 19$ 。
橙色： $UB \le best$ ，剪枝或不入队。
红色：超重剪枝。

graph TD
    classDef root fill:#f8fafc,stroke:#64748b,stroke-width:2px,font-family:Inter;
    classDef active fill:#fef3c7,stroke:#f59e0b,stroke-width:2px,font-family:Inter;
    classDef queue fill:#eff6ff,stroke:#3b82f6,stroke-width:1.5px,font-family:Inter;
    classDef best fill:#ecfdf5,stroke:#10b981,stroke-width:3px,font-family:Inter;
    classDef bound fill:#fff7ed,stroke:#f97316,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;
    classDef overweight fill:#fef2f2,stroke:#ef4444,stroke-width:2px,stroke-dasharray:5 5,font-family:Inter;

    R["根<br>UB=21.25"]:::root

    A["装1<br>UB=21.25<br>第1个扩展"]:::active
    H["不装1<br>UB=18.00<br>先等待，后剪枝"]:::queue

    B["装2<br>UB=21.25<br>第2个扩展"]:::active
    G["不装2<br>UB=16.00<br>不入队"]:::bound

    C["装3<br>cw=11>10<br>超重"]:::overweight
    D["不装3<br>UB=19.00<br>第3个扩展"]:::active

    E["装4<br>cv=19<br>best=19"]:::best
    F["不装4<br>UB=16.00<br>不入队"]:::bound

    R -->|装1| A
    R -->|不装1| H

    A -->|装2| B
    A -->|不装2| G

    B -->|装3| C
    B -->|不装3| D

    D -->|装4| E
    D -->|不装4| F

    H -.->|最后出队<br>UB < best| Hx["剪枝"]:::bound

最终最优值为 $19$ ，对应选择物品 $\{1,2,4\}$ 。

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

七、三种算法的统一视角#

三种算法都可以放在“如何处理指数级解空间”这一脉络下理解：

暴力搜索：在子集树中不加选择地走完所有 $2^n$ 条路径，这是最基础的起点。
回溯法：给暴力搜索加了可行性剪枝和分数背包上界，用 DFS 规避无用分支。
分支限界法：在回溯法的基础上，将“深度优先”改为“最有希望的分支优先”，用优先队列保证最快拿到高分，从而实现更早、更大面积地对其他分支剪枝。
动态规划：跳出了“树形搜索”的框架，转而寻找“状态间的递推关系”。通过定义 $f[i][j]$ ，它把搜索过程中可能重复计算的相同子问题记录下来，自底向上递推，从而将指数级的搜索压缩到了伪多项式级 $O(nW)$ 。

八、三种方法横向对比#

维度	动态规划	回溯法	分支限界法
核心思想	最优子结构 + 自底向上填表	DFS 遍历子集树 + 剪枝	优先队列最佳优先扩展 + 上界剪枝
搜索机制	自底向上直接填表，不进行搜索	DFS（深度优先），撞墙后回溯	最佳优先，优先扩展上界大的节点
时间复杂度	$O(nW)$ 伪多项式	最坏 $O(2^n)$ ，实际高度依赖剪枝	最坏 $O(2^n)$ ，实际高度依赖剪枝
空间复杂度	$O(nW)$ （一维优化后为 $O(W)$ ）	$O(n)$ （主要是递归调用栈的深度）	最坏 $O(2^n)$ （优先队列中活节点可能极多）
获取具体方案	需要通过已填表格进行逆向回溯寻找	天然支持在搜索中直接记录	较为复杂，需要为节点保存父指针信息
适用场景	$W$ 为不大整数的绝大多数情况	$n$ 较小，或需要枚举出所有可行方案	$n$ 中等，只求最优解值，且 $W$ 实数或极大

九、总结#

0-1 背包的难点在于指数级解空间。本文介绍的三种方法分别从两个方向压缩搜索成本：

分数上界：通过“允许将物品切开”的放宽约束，得到搜索分支的乐观上界，用于回溯法和分支限界法剪枝。
状态设计：用“物品索引”和“背包容量”描述子问题，让动态规划可以复用重复状态，在伪多项式时间内求解。

算法选型场景指导：

如果背包容量 $W$ 较小，且为整数：优先使用动态规划。
如果需要找出所有可行方案：使用回溯法。
如果问题规模较大且只需要获得最优解值：可以考虑分支限界法。

十、扩展阅读：复杂度与 NP 理论#

从算法理论角度来看，0-1 背包问题属于经典的第一批被证明的 NP-Hard 优化问题（其判定版本“在价值不小于 $V$ 的前提下，能否在背包中装入不超过重量 $W$ 的物品”属于 NP-Complete 问题）。

这意味着目前学术界普遍认为无法在 $O(n^k)$ （多项式时间）内求得 0-1 背包问题的精确最优解。随着物品数 $n$ 的增长，其最坏解空间的规模呈 $2^n$ 指数速度爆炸增长。

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）来求取近似最优解。

黎明の小站

一、什么是 0-1 背包问题#

二、为什么贪心算法不行#

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

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

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

三、暴力搜索与价值上界#

3.1 解空间与暴力搜索#

3.2 为什么需要剪枝#

3.3 什么是 UB#

3.4 用分数背包计算 UB#

四、回溯法#

4.1 整体搜索树演示#

4.2 Java 实现#

五、动态规划#

5.1 状态定义#

5.2 状态转移#

5.3 二维 DP 写法#

5.4 一维 DP 优化#

5.5 如何恢复最优方案#

六、分支限界法#

6.1 基本思想#

6.2 队列演化推演#

第一步：扩展根节点#

第二步：扩展 `装1`#

第三步：扩展 `装1,2`#

第四步：扩展 `装1,2,不装3`#

第五步：剪枝收尾#

6.3 Java 实现#

七、三种算法的统一视角#

八、三种方法横向对比#

九、总结#

十、扩展阅读：复杂度与 NP 理论#

10.1 伪多项式时间的奥秘#

继续阅读

换条路线

评论

黎明の小站

一、 什么是 0-1 背包问题#

二、 为什么贪心算法不行#

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

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

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

三、 暴力搜索与价值上界#

3.1 解空间与暴力搜索#

3.2 为什么需要剪枝#

3.3 什么是 UB#

3.4 用分数背包计算 UB#

四、 回溯法#

4.1 整体搜索树演示#

4.2 Java 实现#

五、 动态规划#

5.1 状态定义#

5.2 状态转移#

5.3 二维 DP 写法#

5.4 一维 DP 优化#

5.5 如何恢复最优方案#

六、 分支限界法#

6.1 基本思想#

6.2 队列演化推演#

第一步：扩展根节点#

第二步：扩展 装1#

第三步：扩展 装1,2#

第四步：扩展 装1,2,不装3#

第五步：剪枝收尾#

6.3 Java 实现#

七、 三种算法的统一视角#

八、 三种方法横向对比#

九、 总结#

十、 扩展阅读：复杂度与 NP 理论#

10.1 伪多项式时间的奥秘#

分享文章

沿着主题读

换条路线

评论

一、什么是 0-1 背包问题#

二、为什么贪心算法不行#

三、暴力搜索与价值上界#

四、回溯法#

五、动态规划#

六、分支限界法#

第二步：扩展 `装1`#

第三步：扩展 `装1,2`#

第四步：扩展 `装1,2,不装3`#

七、三种算法的统一视角#

八、三种方法横向对比#

九、总结#

十、扩展阅读：复杂度与 NP 理论#