Hello Algo 源码精读：0-1 背包问题的动态规划四解法——状态定义、转移方程到一维滚动数组优化

导读

0-1 背包问题是《Hello 算法》中引入动态规划的第一道经典组合优化题，它用“每一件物品选或不选”这样一轮轮相互制约的决策，把动态规划的三大核心要素——状态定义、最优子结构、边界与转移顺序——完整地串了起来。本文以仓库英文文档 knapsack_problem.md 为骨架，对照 Python / C++ / Java 等语言的 knapsack.py 真实源码，逐级讲解暴力搜索 → 记忆化 → 二维 DP 填表 → 一维滚动数组优化的递进过程。读完你将能独立推导背包类问题的状态转移方程，并理解“为什么空间优化必须倒序遍历”这一面试高频考点。

问题背景：为什么 0-1 背包是动态规划的“入门第一题”

在《Hello 算法》的动态规划章节中，0-1 背包位于承前启后的位置：它承接 intro_to_dynamic_programming.md 中“重叠子问题 + 最优子结构”两大判定特征，又与后续的 unbounded_knapsack_problem.md（完全背包）、以及零钱兑换、编辑距离等问题共享同一套推导框架。

背包问题本身是一个庞大的家族，最常见的三种变体是：

• 0-1 背包：每件物品最多选一次（本专题讲解）；
• 完全背包（unbounded knapsack）：每件物品可以选择任意多次；
• 多重背包（multiple knapsack）：每件物品有固定的可选次数上限。

问题陈述

给定 $n$ 个物品和一个容量为 $cap$ 的背包，第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$，每件物品最多被选择一次。求在容量限制下，背包能装下的最大价值是多少？

注意这里有个容易混淆的映射关系：物品编号从 1 开始计数，而数组下标从 0 开始，因此物品 $i$ 对应 $wgt[i-1]$ 与 $val[i-1]$。仓库驱动代码使用的样例数据如下（见 knapsack.py）：

wgt = [10, 20, 30, 40, 50]   # 各物品重量
val = [50, 120, 150, 210, 240]  # 各物品价值
cap = 50                     # 背包容量

若用手工尝试，能直观感受到“多选高价值大件”与“少选却把空间装满”之间的矛盾：例如第 4、1 件（40+10 重量）合计价值 260，而第 2、3 件（20+30 重量）合计价值可达 270，后者才是最优组合。这正是动态规划要解决的权衡问题。

决策树模型视角

从过程角度看，0-1 背包可以理解为 $n$ 轮决策：对每件物品只有“不放入”与“放入”两个分支。因此问题天然满足决策树模型，而目标是求“容量限制下的最大可装价值”，属于最优化问题，具备典型的动态规划特征。

第 1 步：定义状态与 $dp$ 表

每轮决策“是否放入物品 $i$”只改变两个量：当前处理到第几件物品、背包还剩多少容量。

• 不放入：背包剩余容量不变；
• 放入：背包剩余容量减少 $wgt[i-1]$。

由此得到状态定义——当前物品编号 $i$ 与当前背包容量 $c$，记为二元组 $[i, c]$；对应子问题是：前 $i$ 个物品在容量为 $c$ 的背包中的最大价值，记为 $dp[i, c]$。

最终我们要求的是 $dp[n, cap]$，因此需要一个大小为 $(n+1) \times (cap+1)$ 的二维 $dp$ 表。多出的第 0 行 / 第 0 列是为了容纳“没有物品可选”和“容量为 0”两种边界情况，这也解释了为什么所有实现里 dp 数组都比物品数多一行。

第 2 步：最优子结构与状态转移方程

对物品 $i$ 做出决策之后，剩余问题是前 $i-1$ 个物品的子问题，只可能落入两种情况：

决策	状态变化	价值变化
不放入物品 $i$	$[i-1, c]$	不变
放入物品 $i$	$[i-1, c - wgt[i-1]]$	$+val[i-1]$

于是最大价值 $dp[i, c]$ 等于“不放”与“放”两种选择中的较大者，这就是该问题的最优子结构，转移方程如下：

$$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]$，不可套用上式第二项（否则下标会越界）。

第 3 步：边界条件与转移顺序

• 边界：当“没有物品”（$i = 0$）或“容量为 0”（$c = 0$）时，最大价值为 0，即第 0 行 $dp[0, c]$ 与第 0 列 $dp[i, 0]$ 全部为 0；
• 转移顺序：状态 $[i, c]$ 只依赖上方 $[i-1, c]$ 与左上 $[i-1, c - wgt[i-1]]$，即只依赖上一行的状态。因此用两层正序嵌套循环逐行填表即可，先保证第 $i-1$ 行全部算完，再算第 $i$ 行。

基于以上三步推导，接下来看仓库中按“暴力搜索 → 记忆化 → 动态规划”循序渐进实现的四种解法。

方法一：暴力搜索（指数级递归）

暴力解法把决策树完整展开。以 Python 实现为例（见 knapsack.py）：

def knapsack_dfs(wgt: list[int], val: list[int], i: int, c: int) -> int:
    """0-1 knapsack: Brute-force search"""
    # If all items have been selected or knapsack has no remaining capacity, return value 0
    if i == 0 or c == 0:
        return 0
    # If exceeds knapsack capacity, can only choose not to put it in
    if wgt[i - 1] > c:
        return knapsack_dfs(wgt, val, i - 1, c)
    # Calculate the maximum value of not putting in and putting in item i
    no = knapsack_dfs(wgt, val, i - 1, c)
    yes = knapsack_dfs(wgt, val, i - 1, c - wgt[i - 1]) + val[i - 1]
    # Return the larger value of the two options
    return max(no, yes)

对照文档总结其四个递归要素：

• 递归参数：状态 $[i, c]$；
• 返回值：子问题解 $dp[i, c]$；
• 终止条件：物品取完（$i = 0$）或剩余容量为 0（$c = 0$）时返回 0；
• 剪枝：当前物品重量超过剩余容量时，只能选择“不放”。

由于每件物品都生成“排除”与“放入”两个分支，从递归树形态可推断其时间复杂度为 $O(2^n)$。观察递归树还会发现大量重叠子问题（如图中的 $dp[1, 10]$）；当物品数量多、背包容量大，尤其存在许多等重物品时，重叠子问题数量会显著膨胀——这正是需要记忆化改造的信号。

方法二：记忆化搜索（自上而下消除重复计算）

为了让每个重叠子问题只计算一次，引入备忘录 mem 记录子问题解，其中 mem[i][c] 对应 $dp[i,c]$。由于最大价值不可能是负数，仓库实现统一用 -1 初始化备忘录作为“未计算”标记（见 knapsack.py）：

def knapsack_dfs_mem(
    wgt: list[int], val: list[int], mem: list[list[int]], i: int, c: int
) -> int:
    """0-1 knapsack: Memoization search"""
    # If all items have been selected or knapsack has no remaining capacity, return value 0
    if i == 0 or c == 0:
        return 0
    # If there's a record, return it directly
    if mem[i][c] != -1:
        return mem[i][c]
    # If exceeds knapsack capacity, can only choose not to put it in
    if wgt[i - 1] > c:
        return knapsack_dfs_mem(wgt, val, mem, i - 1, c)
    # Calculate the maximum value of not putting in and putting in item 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]
    # Record and return the larger value of the two options
    mem[i][c] = max(no, yes)
    return mem[i][c]

引入记忆化后，每个状态 $[i, c]$ 至多计算一次，因此时间复杂度取决于子问题总数，即 $O(n \times cap)$。相比 $O(2^n)$，这是从“随物品数指数增长”到“随物品数与容量乘积增长”的质变。记忆化剪枝后的搜索树中，重复分支（如图中被合并的 $dp[2,10]$）不再被展开。

方法三：动态规划（自下而上填表）

动态规划本质上就是“按转移方程把 $dp$ 表一格一格填满”的过程（见 knapsack.py）：

def knapsack_dp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 knapsack: Dynamic programming"""
    n = len(wgt)
    # Initialize dp table
    dp = [[0] * (cap + 1) for _ in range(n + 1)]
    # State transition
    for i in range(1, n + 1):
        for c in range(1, cap + 1):
            if wgt[i - 1] > c:
                # If exceeds knapsack capacity, don't select item i
                dp[i][c] = dp[i - 1][c]
            else:
                # The larger value between not selecting and selecting item 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] * (cap+1) for _ in range(n+1)] 一步同时完成了“第 0 行 / 第 0 列全为 0”的边界铺设，无需额外赋值；
• 外层循环 $i$ 从 1 到 $n$，内层循环 $c$ 从 1 到 $cap$，顺序填表；
• 分支处理：wgt[i-1] > c 时只能继承 dp[i-1][c]，否则取“不放”与“放”的较大者；
• 答案是右下角 dp[n][cap]。

从实现可以推断，DP 法的时间与空间复杂度都由二维数组规模决定，均为 $O(n\times cap)$。原文第 3、4 节还有一组 14 帧的 knapsack_dp_step1.png 至 knapsack_dp_step14.png 分步图，逐帧演示了容量 30 的小样例中整张表的填充过程，适合对照代码逐格推演。

方法四：空间优化（滚动数组与一维倒序遍历）

从二维到两行滚动数组

观察转移方程可以发现，第 $i$ 行的每个状态只与第 $i-1$ 行相关，更早的行不再被使用。因此可以用两行数组交替滚动，把空间复杂度从 $O(n \times cap)$ 降到 $O(cap)$。

更进一步：只用一行数组，但必须倒序遍历

再追问一句：能否只用一个一维数组？可以，但内层循环必须改为倒序。原因如下：

• 开始遍历第 $i$ 行时，一维数组里存的还是第 $i-1$ 行的结果；
• 若正序遍历到 $dp[i, c]$ 时，其左上依赖 $dp[i-1, 1] \sim dp[i-1, c-1]$ 可能已被本行的新值覆盖（因为下标更小、先被更新），导致“放物品 $i$”的分支用了错误的当前行数据；
• 若倒序遍历，更新 $dp[c]$ 时所有更小下标 $dp[0 \dots c-wgt[i-1]]$ 仍是上一行（第 $i-1$ 行）的旧值，未被本轮覆盖，状态转移因此正确。

代码上只需删掉 dp 的第一维并把内层循环改成倒序（见 knapsack.py）：

def knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) -> int:
    """0-1 knapsack: Space-optimized dynamic programming"""
    n = len(wgt)
    # Initialize dp table
    dp = [0] * (cap + 1)
    # State transition
    for i in range(1, n + 1):
        # Traverse in reverse order
        for c in range(cap, 0, -1):
            if wgt[i - 1] > c:
                # If exceeds knapsack capacity, don't select item i
                dp[c] = dp[c]
            else:
                # The larger value between not selecting and selecting item i
                dp[c] = max(dp[c], dp[c - wgt[i - 1]] + val[i - 1])
    return dp[cap]

补充说明两点：

• 当 wgt[i-1] > c 时 dp[c] = dp[c] 属于无操作写法，仅为保持分支结构与二维版本一一对应；C++/Java 实现则将其合并为 if (wgt[i - 1] <= c) dp[c] = max(dp[c], dp[c - wgt[i-1]] + val[i-1])，效果等价（见下方跨语言对比）；
• “为什么 0-1 背包空间优化必须倒序遍历、而完全背包却要正序遍历”，正是 unbounded_knapsack_problem.md 延续讨论的核心差异点。

原文在 knapsack_dp_comp_step1.png 至 knapsack_dp_comp_step6.png 的 6 帧分步图中，演示了从第 $i=1$ 行滚动到 $i=2$ 行时单数组的原地覆盖过程，可与上文“正序污染、倒序安全”的结论互相印证。

四种方法复杂度与要点总览

解法	时间（时间受子问题影响）	空间	核心技巧	适用理解点
暴力搜索 knapsack_dfs	$O(2^n)$	$O(n)$（递归栈深）	完整决策树	认识重叠子问题
记忆化搜索 knapsack_dfs_mem	$O(n \times cap)$	$O(n \times cap)$	备忘录 mem，-1 标记未算	剪掉重复分支
动态规划 knapsack_dp	$O(n \times cap)$	$O(n \times cap)$	二维表自底向上填	状态转移的机械过程
空间优化 knapsack_dp_comp	$O(n \times cap)$	$O(cap)$	单数组 + 内层倒序	覆盖顺序的边界处理

其中 $O(n \times cap)$ 的“伪多项式”性质值得留意：它的规模同时取决于物品数 $n$ 与容量数值 $cap$，因此严格地说复杂度与输入的数值范围相关。

仓库多语言实现与运行验证

《Hello 算法》同一份算法在十余种语言中均有等价实现。本专题文件以 knapsack 为基名存放于各语言目录的 chapter_dynamic_programming 下，本文引证过的至少包括：

• Python：knapsack.py（文中所列代码即出自此文件）
• C++：knapsack.cpp
• Java：knapsack.java
• Go：knapsack.go
• C：knapsack.c

各语言实现的函数一一对应：C++ 的 knapsackDFS / knapsackDFSMem / knapsackDP / knapsackDPComp、Java 的同名静态方法，与 Python 版四个函数逻辑完全同构。以 Java 版的二维初始化为例，new int[n + 1][cap + 1] 默认填 0，恰好满足边界条件，而备忘录 mem 则需要显式用 Arrays.fill(row, -1) 初始化为 -1（见 knapsack.java）；C++ 则用 vector<vector<int>> mem(n + 1, vector<int>(cap + 1, -1)) 一步完成（见 knapsack.cpp）。

运行验证：在仓库根目录执行

python3 en/codes/python/chapter_dynamic_programming/knapsack.py

四个函数依次运行，会打印四遍相同的结果：The maximum item value not exceeding knapsack capacity is 270。四路解法结果一致，本身就构成了对状态转移方程与空间优化正确性的交叉验证；读者也可通过将任意函数入口的返回值改为手工推演值来逐段核对。

延伸阅读：从 0-1 背包走向 DP 全章

0-1 背包的推导方法是《Hello 算法》动态规划章节反复使用的“三板斧”，可在以下同章文档中继续强化：

• intro_to_dynamic_programming.md：重叠子问题、最优子结构的判定方法；
• dp_problem_features.md：什么样的题“像”动态规划题；
• dp_solution_pipeline.md：从暴力回溯到记忆化再到 DP 填表的通用解题路径；
• unbounded_knapsack_problem.md：把“每件最多一次”放宽为“无限次”，转移方程与遍历顺序如何变化；
• edit_distance_problem.md 与 min_path_sum 系列：二维状态与字符串类 DP 的更多实战。

若希望对照原文档逐字研读，仓库内同时保留了中文版 knapsack_problem.md 与英文版 knapsack_problem.md，两者配图（递归树、填表分步图、滚动数组覆盖图）完全一致，可与本文结合阅读。