Hello 算法从暴力搜索到空间优化 DP 的 0-1 背包问题完整解法与逐步可视化【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo本篇基于《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 Codewgt [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重量 203050价值 120150270。0-1 背包可以看作一个由 $n$ 轮决策组成的过程对每个物品都有“不放入”和“放入”两种决策因此该问题满足决策树模型且目标是最优化求最大价值符合动态规划的适用特征。状态定义与状态转移方程状态定义当前物品编号 $i$ 和背包容量 $c$记为 $[i, c]$。状态 $[i, c]$ 对应的子问题是“前 $i$ 个物品在容量为 $c$ 的背包中的最大价值”记为 $dp[i, c]$。待求解的是 $dp[n, cap]$因此需要一个尺寸为 $(n1) \times (cap1)$ 的二维表。最优子结构做出物品 $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-L20def 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-L41def 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即 $(n1) \times (cap1)$ 的全 $-1$ 表。引入记忆化后时间复杂度取决于子问题数量降为 $O(n \times cap)$空间复杂度为 $O(n \times cap)$记忆表加 $O(n)$递归栈。记忆化搜索是“自顶向下”填表与下一节的“自底向上”动态规划互为镜像。解法三动态规划knapsack_dp动态规划实质上就是在状态转移中自底向上填充二维 $dp$ 表的过程。边界条件“首行首列全为 0”恰好由dp表的初始值0天然满足无需单独处理。对应 knapsack.py#L44-L58def 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]两个关键点值得注意外层循环for i in range(1, n 1)从第 1 行开始因为第 0 行是边界值 0状态只依赖上一行第 $i-1$ 行转移顺序为正序双重循环即可时间复杂度与空间复杂度均由dp表大小决定即 $O(n \times cap)$。运行 knapsack.pypython3 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-L76def 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 逐步执行链接py3.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]cap50上的结果一致为 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 算法》动态规划章节爬楼梯、编辑距离、完全背包等的通用钥匙。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考