Hello 算法中的 0-1 背包问题全解：从暴力搜索、记忆化到空间优化的动态规划

背包问题是动态规划中最经典、最常见的入门题型，具有 0-1 背包、完全背包、多重背包等众多变种。本文以《Hello 算法》动态规划章节中的 0-1 背包问题 为主线，完整继承原文的“定义状态 → 推导状态转移方程 → 确定边界与转移顺序”三步法，并深入 Python 参考实现 与 C++ 参考实现，逐一展开暴力搜索、记忆化搜索、表形动态规划和一维空间优化四种解法，帮助你掌握 0-1 背包的完整推导与工程实现细节。

问题定义与示例数据

问题描述如下：

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

注意一个细节：物品编号 $i$ 从 $1$ 开始计数，而数组索引从 $0$ 开始计数，因此物品 $i$ 对应重量 $wgt[i-1]$ 和价值 $val[i-1]$。

仓库中各语言实现的驱动代码统一使用如下示例数据（见 knapsack.py 的 __main__ 段）：

• 重量数组 wgt = [10, 20, 30, 40, 50]
• 价值数组 val = [50, 120, 150, 210, 240]
• 背包容量为 cap = 50

该实例的正确答案是 270（选择重量 20 与 30 的两个物品，总重量恰好 50，总价值 120 + 150 = 270），四种解法运行后应输出相同结果：不超过背包容量的最大物品价值为 270。

动态规划三步推导

0-1 背包问题可以看作一个由 $n$ 轮决策组成的过程：每个物品都有“不放入”和“放入”两种决策，因此满足决策树模型。其目标是求解“在限定背包容量下能放入物品的最大价值”，较大概率是一个动态规划问题。按照原文档的三步法展开：

第一步：定义状态，得到 dp 表

对于每个物品：

• 不放入背包，背包容量不变；
• 放入背包，背包容量减小。

由此可得状态定义：当前物品编号 $i$ 和背包容量 $c$，记为 $[i, c]$。

状态 $[i, c]$ 对应的子问题是：前 $i$ 个物品在容量为 $c$ 的背包中的最大价值，记为 $dp[i, c]$。

待求解的是 $dp[n, cap]$，因此需要一个尺寸为 $(n+1) \times (cap+1)$ 的二维 $dp$ 表。

第二步：找出最优子结构，推导状态转移方程

当我们做出物品 $i$ 的决策后，剩余的是前 $i-1$ 个物品决策的子问题，分两种情况：

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

上述分析揭示了本题的最优子结构：最大价值 $dp[i, c]$ 等于“不放入物品 $i$”和“放入物品 $i$”两种方案中价值更大的那一个。由此得到状态转移方程：

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

需要注意的是：若当前物品重量 $wgt[i-1]$ 超出剩余背包容量 $c$，则只能选择不放入背包。

第三步：确定边界条件和状态转移顺序

• 当无物品（$i=0$）或背包容量为 $0$（$c=0$）时，最大价值为 $0$，即首列 $dp[i, 0]$ 和首行 $dp[0, c]$ 都等于 $0$；
• 当前状态 $[i, c]$ 只从上方的 $[i-1, c]$ 和左上方的 $[i-1, c-wgt[i-1]]$ 转移而来，因此用两层循环正序遍历整个 $dp$ 表即可。

方法一：暴力搜索

搜索实现包含四个要素（与 knapsack.py 中 knapsack_dfs 一一对应）：

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

Python 参考实现如下：

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)$。

观察递归树可以发现其中存在重叠子问题，例如 $dp[1, 10]$。当物品较多、背包容量较大，尤其是相同重量的物品较多时，重叠子问题的数量会大幅增多——这正是引入记忆化的动机。

方法二：记忆化搜索

为了保证重叠子问题只被计算一次，借助记忆列表 mem 记录子问题的解，其中 mem[i][c] 对应 $dp[i, c]$。

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 的二维数组再传入，Python 驱动代码中的写法是：

mem = [[-1] * (cap + 1) for _ in range(n + 1)]
res = knapsack_dfs_mem(wgt, val, mem, n, cap)

这里 -1 充当“未计算”标记：合法的价值均为非负整数，因此 mem[i][c] != -1 即可判断该子问题是否已求解。引入记忆化之后，时间复杂度取决于子问题数量，即 $O(n \times cap)$，空间复杂度同为 $O(n \times cap)$（$dp$ 表加上递归栈）。

上图中被标记剪掉的分支，正是命中记忆后不再展开的部分。

方法三：表形动态规划

动态规划实质上就是在状态转移中逐行填充 $dp$ 表的过程，不再依赖递归：

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]

几个实现细节值得注意：

• dp 初始化为全 0，恰好自动满足了“首行首列为 0”的边界条件，无需单独写边界代码；
• 外层循环从 $i=1$ 开始、内层从 $c=1$ 开始的正序遍历，与状态转移来源（上方与左上方）严格对应；
• 时间复杂度和空间复杂度都由 dp 表大小决定，即 $O(n\times cap)$。C++ 侧的 knapsack.cpp 中 knapsackDP 的逻辑与之一致，仅类型与容器不同（vector<vector<int>>）。

原文档用 14 张动画帧逐步演示了 $dp$ 表的填充过程，可以在 knapsack_problem.assets 目录下查看 knapsack_dp_step1.png 至 knapsack_dp_step14.png。

空间优化：一维数组与倒序遍历

由于每个状态都只与其上一行的状态有关，可以先使用两个数组滚动前进，把空间复杂度从 $O(n \times cap)$ 降至 $O(cap)$。

进一步思考：能否只用一个数组？观察可知，每个状态都是从正上方或左上方的格子转移过来的。假设只有一个数组，当开始遍历第 $i$ 行时，数组中存储的仍是第 $i-1$ 行的状态：

• 正序遍历会出错：遍历到 $dp[i, j]$ 时，左上方 $dp[i-1, 1] \sim dp[i-1, j-1]$ 的值可能已经被本行覆盖，无法得到正确的转移结果；
• 倒序遍历则不会发生覆盖：从大到小填 $c$ 时，$dp[c - wgt[i-1]]$ 尚未被本轮更新，仍是上一行的值，转移可以正确进行。

原文档用 6 帧动画（knapsack_dp_comp_step1.png 至 knapsack_dp_comp_step6.png）演示了单个数组下从第 $i=1$ 行转换至第 $i=2$ 行的过程，重点展示了正序与倒序的区别。

在代码层面，只需做两处修改：删除 dp 数组的第一维 $i$，并把内循环改为倒序遍历：

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]

从源码结构看，C++ 版本的 knapsackDPComp 把“超重则不选”这个分支直接合并进了条件判断：只有 wgt[i - 1] <= c 时才执行 dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])，超重时什么都不做（等价于保留上一行的值）。这与 Python 版本中显式的 dp[c] = dp[c] 是自赋值空操作在语义上完全等价，只是写法更紧凑。

四种解法复杂度对比

解法	时间复杂度	空间复杂度	说明
暴力搜索 knapsack_dfs	$O(2^n)$	$O(n)$（递归栈）	每个物品两条分支，指数级
记忆化搜索 knapsack_dfs_mem	$O(n \times cap)$	$O(n \times cap)$	重叠子问题只算一次
表形 DP knapsack_dp	$O(n \times cap)$	$O(n \times cap)$	正序两层循环填表
空间优化 DP knapsack_dp_comp	$O(n \times cap)$	$O(cap)$	一维数组 + 倒序遍历

在示例数据（5 个物品、容量 50）下，四种解法均输出最大价值 270，可作为验证实现正确性的基准用例。

小结与延伸

0-1 背包问题完整展示了动态规划的标准流程：定义状态 $[i,c]$、依据最优子结构推导转移方程 $dp[i,c]=\max (dp[i-1,c],dp[i-1,c-wgt[i-1]]+val[i-1])$、确定首行首列全 0 的边界与正序填表顺序，最后通过一维数组倒序遍历把空间压缩到 $O(cap)$。其中“倒序遍历防止状态被提前覆盖”是 0-1 背包与完全背包在实现上最核心的区别之一——仓库中紧接着的 完全背包问题 正是基于这一点展开的：物品可无限次选取时，内循环需要改为正序遍历以允许同一物品重复入选。

多语言的完整对照实现（含 Python、C++、Java、Go、Rust、Swift、Kotlin、Ruby 等十余种语言）可以在 codes/ 目录下各语言的 chapter_dynamic_programming 章节中查阅，便于对比不同语言在二维数组初始化、负数标记与一维倒序循环上的习惯写法。