Hello 算法：从暴力搜索到空间优化 DP 的 0-1 背包问题完整解法与逐步可视化

本篇基于《Hello 算法》（hello-algo）仓库中 codes/pythontutor/chapter_dynamic_programming/knapsack.md 提供的四段可逐步可视化执行的 Python 代码，结合 完整可运行的源码实现 与 0-1 背包问题教程文档，系统讲解 0-1 背包问题从状态定义、状态转移方程推导，到暴力搜索、记忆化搜索、二维动态规划、一维空间优化四个阶段的完整实现。读完后你将掌握 0-1 背包的标准求解管线，能独立写出可运行的求解代码，并理解为什么空间优化版本必须倒序遍历容量。

问题定义与示例数据

给定 $n$ 个物品，第 $i$ 个物品的重量为 wgt[i-1]、价值为 val[i-1]，以及一个容量为 cap 的背包。每个物品只能选择一次，求在限定背包容量下能放入物品的最大价值。

仓库中所有解法使用的统一示例数据（见 knapsack.py 的 Driver Code）：

wgt = [10, 20, 30, 40, 50]
val = [50, 120, 150, 210, 240]
cap = 50
n = len(wgt)

注意物品编号 $i$ 从 $1$ 开始计数、数组索引从 $0$ 开始计数，因此物品 $i$ 对应 wgt[i-1] 和 val[i-1]。该示例的最优解为放入物品 2 和物品 3（重量 20+30=50，价值 120+150=270）。

0-1 背包可以看作一个由 $n$ 轮决策组成的过程：对每个物品都有“不放入”和“放入”两种决策，因此该问题满足决策树模型，且目标是最优化（求最大价值），符合动态规划的适用特征。

状态定义与状态转移方程

状态定义：当前物品编号 $i$ 和背包容量 $c$，记为 $[i, c]$。状态 $[i, c]$ 对应的子问题是“前 $i$ 个物品在容量为 $c$ 的背包中的最大价值”，记为 $dp[i, c]$。待求解的是 $dp[n, cap]$，因此需要一个尺寸为 $(n+1) \times (cap+1)$ 的二维表。

最优子结构：做出物品 $i$ 的决策后，剩余的是前 $i-1$ 个物品的子问题：

• 不放入物品 $i$：背包容量不变，状态变化为 $[i-1, c]$；
• 放入物品 $i$：背包容量减少 wgt[i-1]，价值增加 val[i-1]，状态变化为 $[i-1, c-wgt[i-1]]$。

由此得到状态转移方程：

$$dp[i, c] = \max(dp[i-1, c],\ dp[i-1, c - wgt[i-1]] + val[i-1])$$

若当前物品重量 wgt[i-1] 超出剩余容量 $c$，则只能选择不放入背包，此时 $dp[i, c] = dp[i-1, c]$。

边界条件：无物品或背包容量为 $0$ 时最大价值为 $0$，即首列 $dp[i, 0]$ 和首行 $dp[0, c]$ 均为 $0$。状态转移顺序上，$[i, c]$ 由上方 $[i-1, c]$ 和左上方 $[i-1, c-wgt[i-1]]$ 转移而来，正序两层循环遍历即可。

下面四种解法在 pythontutor 可视化文档 中各对应一段 Python Tutor 逐步执行链接（文档以 [file]{knapsack}-[func]{函数名} 的注释锚点标注），可在 Python Tutor 平台上逐指令观察变量、dp 表与递归栈的变化。

解法一：暴力搜索（knapsack_dfs）

暴力搜索用递归枚举每个物品的“选 / 不选”两种决策，其要素为：

• 递归参数：状态 $[i, c]$；
• 返回值：子问题的解 $dp[i, c]$；
• 终止条件：物品编号越界 $i = 0$ 或剩余容量 $c = 0$ 时返回 $0$；
• 剪枝：当前物品重量超出剩余容量时，只能递归“不放入”分支。

对应 knapsack.py#L8-L20：

def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int) -> int:
    """0-1 背包：暴力搜索"""
    # 若已选完所有物品或背包无剩余容量，则返回价值 0
    if i == 0 or c == 0:
        return 0
    # 若超过背包容量，则只能选择不放入背包
    if wgt[i - 1] > c:
        return knapsack_dfs(wgt, val, i - 1, c)
    # 计算不放入和放入物品 i 的最大价值
    no = knapsack_dfs(wgt, val, i - 1, c)
    yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
    # 返回两种方案中价值更大的那一个
    return max(no, yes)

由于每个物品都产生两条分支，时间复杂度为 $O(2^n)$，空间复杂度（递归深度）为 $O(n)$。从源码结构看，递归树中存在大量重叠子问题（例如 dp[1, 10] 会被多个父节点重复计算），当物品较多、容量较大、相同重量物品较多时，重复量会急剧放大——这正是引入记忆化的动机。

解法二：记忆化搜索（knapsack_dfs_mem）

在暴力搜索之上引入二维记忆列表 mem，其中 mem[i][c] 对应 $dp[i,c]$，用哨兵值 $-1$ 标记“尚未计算”。命中记录时直接返回，保证每个子问题只被计算一次。对应 knapsack.py#L23-L41：

def knapsack_dfs_mem(
    wgt: list[int], val: list[int], mem: list[list[int]], i: int, c: int
) -> int:
    """0-1 背包：记忆化搜索"""
    # 若已选完所有物品或背包无剩余容量，则返回价值 0
    if i == 0 or c == 0:
        return 0
    # 若已有记录，则直接返回
    if mem[i][c] != -1:
        return mem[i][c]
    # 若超过背包容量，则只能选择不放入背包
    if wgt[i - 1] > c:
        return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
    # 计算不放入和放入物品 i 的最大价值
    no = knapsack_dfs_mem(wgt, val, mem, i - 1, c)
    yes = knapsack_dfs_mem(wgt, val, mem, i - 1, c - wgt[i - 1]) + val[i - 1]
    # 记录并返回两种方案中价值更大的那一个
    mem[i][c] = max(no, yes)
    return mem[i][c]

驱动代码中记忆列表的初始化方式为 mem = [[-1] * (cap + 1) for _ in range(n + 1)]（见 knapsack.py#L91-L92），即 $(n+1) \times (cap+1)$ 的全 $-1$ 表。引入记忆化后，时间复杂度取决于子问题数量，降为 $O(n \times cap)$；空间复杂度为 $O(n \times cap)$（记忆表）加 $O(n)$（递归栈）。记忆化搜索是“自顶向下”填表，与下一节的“自底向上”动态规划互为镜像。

解法三：动态规划（knapsack_dp）

动态规划实质上就是在状态转移中自底向上填充二维 $dp$ 表的过程。边界条件“首行首列全为 0”恰好由 dp 表的初始值 0 天然满足，无需单独处理。对应 knapsack.py#L44-L58：

def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 背包：动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    # 状态转移
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                # 若超过背包容量，则不选物品 i
                dp[i][c] = dp[i - 1][c]
            else:
                # 不选和选物品 i 这两种方案的较大值
                dp[i][c] = max(dp[i - 1][c], dp[i - 1][c - wgt[i - 1]] + val[i - 1])
    return dp[n][cap]

两个关键点值得注意：

1. 外层循环 for i in range(1, n + 1) 从第 1 行开始，因为第 0 行是边界值 0；
2. 状态只依赖上一行（第 $i-1$ 行），转移顺序为正序双重循环即可，时间复杂度与空间复杂度均由 dp 表大小决定，即 $O(n \times cap)$。

运行 knapsack.py（python3 codes/python/chapter_dynamic_programming/knapsack.py）可依次看到四种解法的输出，四行结果均为 不超过背包容量的最大物品价值为 270，互相印证正确性。

解法四：空间优化后的动态规划（knapsack_dp_comp）

由于每个状态只与其上一行有关，可先用两个数组滚动将空间降至 $O(cap)$；进一步思考能否只用一个数组？从源码结构看，答案是否定的——单数组必须倒序遍历容量，原因如下：

• 正序遍历会覆盖状态：当遍历到 $dp[i, c]$ 时，左上方依赖的 $dp[i-1, c-wgt[i-1]]$ 可能已被本行的新值覆盖，导致状态转移结果错误（等价于允许同一物品被重复装入，即变成完全背包）；
• 倒序遍历不会覆盖：dp[c - wgt[i-1]] 在更新 dp[c] 之前仍是第 $i-1$ 行的旧值，状态转移可以正确进行。

对应 knapsack.py#L61-L76：

def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 背包：空间优化后的动态规划"""
    n = len(wgt)
    # 初始化 dp 表
    dp = [0] * (cap + 1)
    # 状态转移
    for i in range(1, n + 1):
        # 倒序遍历
        for c in range(cap, 0, -1):
            if wgt[i - 1] > c:
                # 若超过背包容量，则不选物品 i
                dp[c] = dp[c]
            else:
                # 不选和选物品 i 这两种方案的较大值
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
    return dp[cap]

与二维版本相比，改动只有两处：删除 dp 的第一维 $i$（dp 变为长度 cap + 1 的一维数组）；内循环改为 range(cap, 0, -1) 倒序遍历。时间复杂度仍为 $O(n \times cap)$，空间复杂度降至 $O(cap)$，这是 0-1 背包最常用、最简洁的最终形态。

用 Python Tutor 逐步执行验证

仓库的 codes/pythontutor/chapter_dynamic_programming/knapsack.md 为上述四个函数各内嵌了一条 Python Tutor 逐步执行链接（py=3.11），每条链接的 #code= 载荷与 knapsack.py 中对应函数逐行一致，并附带驱动代码，可直接在 Python Tutor 平台上单步执行、观察：

代码块锚点	对应函数	可视化观察重点
[file]{knapsack}-[func]{knapsack_dfs}	暴力搜索	递归树的双分支展开与指数级调用次数
[file]{knapsack}-[func]{knapsack_dfs_mem}	记忆化搜索	mem[i][c] 从 -1 变为具体值后如何剪掉重叠分支
[file]{knapsack}-[func]{knapsack_dp}	动态规划	二维 dp 表逐格自底向上填充
[file]{knapsack}-[func]{knapsack_dp_comp}	空间优化 DP	一维 dp 数组倒序更新时的数值变化

这套“教程文档 + 多语言可运行代码 + 逐步可视化”的三件套结构在仓库中是统一的：同目录下的 unbounded_knapsack.md 等文件对应完全背包等变体；docs/chapter_dynamic_programming/knapsack_problem.md 则给出了带逐步动画的状态转移过程图解，适合配合本文源码阅读。此外，仓库 codes/ 下还提供了 Java、C++、C、Go、Rust、JavaScript、TypeScript 等十几种语言的同名实现（各语言目录下的 chapter_dynamic_programming/ 内），便于横向对照各语言对一维倒序 DP 的写法。

小结

四种解法在示例数据（wgt=[10,20,30,40,50]，val=[50,120,150,210,240]，cap=50）上的结果一致为 270，复杂度对比如下：

解法	时间复杂度	空间复杂度	核心思想
暴力搜索 knapsack_dfs	$O(2^n)$	$O(n)$（递归栈）	决策树枚举 + 容量剪枝
记忆化搜索 knapsack_dfs_mem	$O(n \times cap)$	$O(n \times cap) + O(n)$	自顶向下，记忆表消除重叠子问题
动态规划 knapsack_dp	$O(n \times cap)$	$O(n \times cap)$	自底向上填充二维表
空间优化 knapsack_dp_comp	$O(n \times cap)$	$O(cap)$	一维表 + 倒序遍历容量

掌握这条从递归到记忆化、再到 DP 表与空间压缩的推导管线，是理解《Hello 算法》动态规划章节（爬楼梯、编辑距离、完全背包等）的通用钥匙。