hello-algo完全背包问题的动态规划解法与空间优化——为什么内循环必须正序遍历【免费下载链接】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仓库中完全背包问题的代码与图解完整讲解从二维 dp 表推导到一维空间优化的全过程你将掌握完全背包与 0-1 背包在状态转移方程上唯一的差异dp[i-1][c-w]变为dp[i][c-w]、该差异如何决定内循环必须正序遍历这一关键结论并能直接复现仓库中的 Python 示例样例输入下最大价值为 22与 C 对照实现。问题定义与示例数据给定n个物品第i个物品的重量为wgt[i-1]、价值为val[i-1]和一个容量为cap的背包。与 0-1 背包的唯一区别是每个物品可以重复选取要求计算在限定背包容量下能放入物品的最大价值。仓库 完全背包 Python 实现 末尾的 Driver Code 使用了如下样例wgt [1, 2, 3] val [5, 11, 15] cap 4直觉上最优方案是选 2 个重量为 2 的物品总重量 4总价值 22。实际运行该文件可验证两个函数输出一致不超过背包容量的最大物品价值为 22 不超过背包容量的最大物品价值为 22动态规划思路状态转移方程与 0-1 背包的一字之差完全背包问题与 0-1 背包问题非常相似区别仅在于不限制物品的选择次数在 0-1 背包问题中每种物品只有一个将物品i放入背包后只能从前i-1个物品中继续选择在完全背包问题中每种物品数量无限将物品i放入背包后仍可以从前i个物品中选择即物品i本身可以再次被选。据此状态dp[i][c]考虑前i个物品、容量为c时的最大价值的两种决策转移为不放入物品i转移至dp[i-1][c]与 0-1 背包相同放入物品i转移至dp[i][c - wgt[i-1]]注意下标是i而不是i-1。状态转移方程为dp[i][c] max(dp[i-1][c], dp[i][c - wgt[i-1]] val[i-1])将 0-1 背包的 Python 实现 中knapsack_dp的转移式与本方程对比可以确认两道题的代码仅有一处从dp[i - 1][c - wgt[i - 1]]变为dp[i][c - wgt[i - 1]]其余完全一致。二维 dp 表的完整实现对应 codes/python/chapter_dynamic_programming/unbounded_knapsack.py#L8-L22 中的unbounded_knapsack_dpdef unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) - int: 完全背包动态规划 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][c - wgt[i - 1]] val[i - 1]) return dp[n][cap]逐点说明dp 表尺寸(n 1) × (cap 1)全 0 初始化。首行dp[0][c]与首列dp[i][0]天然为 0没有物品或没有容量时价值为 0这与完全背包不超过容量的语义一致不需要额外的∞处理容量越界分支当wgt[i-1] c时当前物品放不进去只能不选直接继承dp[i-1][c]正常分支取不选与选一次物品i两种方案的最大值。选物品i之后剩余容量c - wgt[i-1]内仍允许再选物品i这正是dp[i][...]同维度带来的可重复选取语义。时间复杂度为O(n × cap)空间复杂度为O(n × cap)。空间优化与 0-1 背包相反内循环改为正序遍历二维表压缩为一维数组时关键问题是遍历方向。由于当前状态dp[c]是从**左边同行c - w和上边上一行c**转移而来的压缩后正序遍历时dp[c - w]已经是**本轮第i个物品**算出的新值——这恰好符合完全背包放入物品i后仍可从物品i中继续选的要求若改用倒序遍历dp[c - w]会被保护为上一行的旧值物品i在一轮中最多只能选一次就退化成 0-1 背包了。这个遍历顺序与 0-1 背包正好相反这一点可以直接从源码得到印证knapsack.py 的knapsack_dp_comp内循环是for c in range(cap, 0, -1)倒序而 unbounded_knapsack.py 的unbounded_knapsack_dp_comp内循环是for c in range(1, cap 1)正序源码注释也分别写着倒序遍历与正序遍历。空间优化后的实现只需将dp数组的第一维删除def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) - int: 完全背包空间优化后的动态规划 n len(wgt) # 初始化 dp 表 dp [0] * (cap 1) # 状态转移 for i in range(1, n 1): # 正序遍历 for c in range(1, cap 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]注意转移式中max的左操作数dp[c]此时代表不选保留旧值右操作数dp[c - wgt[i - 1]] val[i - 1]代表选一次且右操作数引用的是本轮已更新的位置从而在一维数组上隐式地完成了无限次选取。空间复杂度降至O(cap)时间复杂度仍为O(n × cap)。跨语言实现的一致性从源码结构看各语言实现保持了同一套逻辑与同一组样例数据。以 C 实现 为例/* 完全背包空间优化后的动态规划 */ int unboundedKnapsackDPComp(vectorint wgt, vectorint val, int cap) { int n wgt.size(); // 初始化 dp 表 vectorint dp(cap 1, 0); // 状态转移 for (int i 1; i n; i) { for (int c 1; c cap; c) { 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]; }可以看到 Python 版中range(1, cap 1)的正序遍历对应 C 中的for (int c 1; c cap; c)转移式与越界分支逐行对应。仓库中 Go、Java、Rust、TypeScript 等其他语言的实现同样遵循该模式可分别在codes/下对应语言的chapter_dynamic_programming/unbounded_knapsack.*文件中核对。变体延伸零钱兑换是完全背包的特例背包问题是一大类动态规划问题的代表其中零钱兑换问题就是完全背包的特例详见 完全背包问题章节文档。两者的联系与不同点可相互转换物品对应硬币、物品重量对应硬币面值、背包容量对应目标金额优化目标相反完全背包最大化物品价值max零钱兑换最小化硬币数量min约束语义不同完全背包求不超过容量的解零钱兑换求恰好凑到目标金额的解。因此在 coin_change.py 的coin_change_dp中状态转移变为dp[i][a] min(dp[i-1][a], dp[i][a - coins[i-1]] 1)选中硬币时执行1计数而恰好凑出的要求通过哨兵值MAX amt 1实现——用amt 1表示无效解因为凑出amt最多只需amt枚硬币既避免了整型最大值1溢出又方便min过滤无效解最后若dp[n][amt] MAX则返回-1。空间优化版coin_change_dp_comp的写法与完全背包一致一维数组 正序遍历for a in range(1, amt 1)。小结与复杂度对照维度0-1 背包完全背包物品数量每种 1 个每种无限选物品后的状态转移dp[i-1][c - wgt[i-1]]dp[i][c - wgt[i-1]]一维优化时内循环倒序range(cap, 0, -1)正序range(1, cap 1)时间复杂度O(n × cap)O(n × cap)空间复杂度优化后O(cap)O(cap)掌握本文后可以验证几个要点完全背包与 0-1 背包的全部差异浓缩在一维下标ivsi-1与遍历方向正序 vs 倒序上空间优化的正确性完全由左边的值是否应为本轮新值这一需求决定。相关代码集中在 codes/python/chapter_dynamic_programming/unbounded_knapsack.py 与 codes/python/chapter_dynamic_programming/knapsack.py可直接运行对比两者在相同输入下的行为差异配套的逐步图解位于 完全背包章节文档 及其unbounded_knapsack_problem.assets/图片目录中。【免费下载链接】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），仅供参考 hello-algo：完全背包问题的动态规划解法与空间优化——为什么内循环必须正序遍历
hello-algo完全背包问题的动态规划解法与空间优化——为什么内循环必须正序遍历【免费下载链接】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仓库中完全背包问题的代码与图解完整讲解从二维 dp 表推导到一维空间优化的全过程你将掌握完全背包与 0-1 背包在状态转移方程上唯一的差异dp[i-1][c-w]变为dp[i][c-w]、该差异如何决定内循环必须正序遍历这一关键结论并能直接复现仓库中的 Python 示例样例输入下最大价值为 22与 C 对照实现。问题定义与示例数据给定n个物品第i个物品的重量为wgt[i-1]、价值为val[i-1]和一个容量为cap的背包。与 0-1 背包的唯一区别是每个物品可以重复选取要求计算在限定背包容量下能放入物品的最大价值。仓库 完全背包 Python 实现 末尾的 Driver Code 使用了如下样例wgt [1, 2, 3] val [5, 11, 15] cap 4直觉上最优方案是选 2 个重量为 2 的物品总重量 4总价值 22。实际运行该文件可验证两个函数输出一致不超过背包容量的最大物品价值为 22 不超过背包容量的最大物品价值为 22动态规划思路状态转移方程与 0-1 背包的一字之差完全背包问题与 0-1 背包问题非常相似区别仅在于不限制物品的选择次数在 0-1 背包问题中每种物品只有一个将物品i放入背包后只能从前i-1个物品中继续选择在完全背包问题中每种物品数量无限将物品i放入背包后仍可以从前i个物品中选择即物品i本身可以再次被选。据此状态dp[i][c]考虑前i个物品、容量为c时的最大价值的两种决策转移为不放入物品i转移至dp[i-1][c]与 0-1 背包相同放入物品i转移至dp[i][c - wgt[i-1]]注意下标是i而不是i-1。状态转移方程为dp[i][c] max(dp[i-1][c], dp[i][c - wgt[i-1]] val[i-1])将 0-1 背包的 Python 实现 中knapsack_dp的转移式与本方程对比可以确认两道题的代码仅有一处从dp[i - 1][c - wgt[i - 1]]变为dp[i][c - wgt[i - 1]]其余完全一致。二维 dp 表的完整实现对应 codes/python/chapter_dynamic_programming/unbounded_knapsack.py#L8-L22 中的unbounded_knapsack_dpdef unbounded_knapsack_dp(wgt: list[int], val: list[int], cap: int) - int: 完全背包动态规划 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][c - wgt[i - 1]] val[i - 1]) return dp[n][cap]逐点说明dp 表尺寸(n 1) × (cap 1)全 0 初始化。首行dp[0][c]与首列dp[i][0]天然为 0没有物品或没有容量时价值为 0这与完全背包不超过容量的语义一致不需要额外的∞处理容量越界分支当wgt[i-1] c时当前物品放不进去只能不选直接继承dp[i-1][c]正常分支取不选与选一次物品i两种方案的最大值。选物品i之后剩余容量c - wgt[i-1]内仍允许再选物品i这正是dp[i][...]同维度带来的可重复选取语义。时间复杂度为O(n × cap)空间复杂度为O(n × cap)。空间优化与 0-1 背包相反内循环改为正序遍历二维表压缩为一维数组时关键问题是遍历方向。由于当前状态dp[c]是从**左边同行c - w和上边上一行c**转移而来的压缩后正序遍历时dp[c - w]已经是**本轮第i个物品**算出的新值——这恰好符合完全背包放入物品i后仍可从物品i中继续选的要求若改用倒序遍历dp[c - w]会被保护为上一行的旧值物品i在一轮中最多只能选一次就退化成 0-1 背包了。这个遍历顺序与 0-1 背包正好相反这一点可以直接从源码得到印证knapsack.py 的knapsack_dp_comp内循环是for c in range(cap, 0, -1)倒序而 unbounded_knapsack.py 的unbounded_knapsack_dp_comp内循环是for c in range(1, cap 1)正序源码注释也分别写着倒序遍历与正序遍历。空间优化后的实现只需将dp数组的第一维删除def unbounded_knapsack_dp_comp(wgt: list[int], val: list[int], cap: int) - int: 完全背包空间优化后的动态规划 n len(wgt) # 初始化 dp 表 dp [0] * (cap 1) # 状态转移 for i in range(1, n 1): # 正序遍历 for c in range(1, cap 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]注意转移式中max的左操作数dp[c]此时代表不选保留旧值右操作数dp[c - wgt[i - 1]] val[i - 1]代表选一次且右操作数引用的是本轮已更新的位置从而在一维数组上隐式地完成了无限次选取。空间复杂度降至O(cap)时间复杂度仍为O(n × cap)。跨语言实现的一致性从源码结构看各语言实现保持了同一套逻辑与同一组样例数据。以 C 实现 为例/* 完全背包空间优化后的动态规划 */ int unboundedKnapsackDPComp(vectorint wgt, vectorint val, int cap) { int n wgt.size(); // 初始化 dp 表 vectorint dp(cap 1, 0); // 状态转移 for (int i 1; i n; i) { for (int c 1; c cap; c) { 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]; }可以看到 Python 版中range(1, cap 1)的正序遍历对应 C 中的for (int c 1; c cap; c)转移式与越界分支逐行对应。仓库中 Go、Java、Rust、TypeScript 等其他语言的实现同样遵循该模式可分别在codes/下对应语言的chapter_dynamic_programming/unbounded_knapsack.*文件中核对。变体延伸零钱兑换是完全背包的特例背包问题是一大类动态规划问题的代表其中零钱兑换问题就是完全背包的特例详见 完全背包问题章节文档。两者的联系与不同点可相互转换物品对应硬币、物品重量对应硬币面值、背包容量对应目标金额优化目标相反完全背包最大化物品价值max零钱兑换最小化硬币数量min约束语义不同完全背包求不超过容量的解零钱兑换求恰好凑到目标金额的解。因此在 coin_change.py 的coin_change_dp中状态转移变为dp[i][a] min(dp[i-1][a], dp[i][a - coins[i-1]] 1)选中硬币时执行1计数而恰好凑出的要求通过哨兵值MAX amt 1实现——用amt 1表示无效解因为凑出amt最多只需amt枚硬币既避免了整型最大值1溢出又方便min过滤无效解最后若dp[n][amt] MAX则返回-1。空间优化版coin_change_dp_comp的写法与完全背包一致一维数组 正序遍历for a in range(1, amt 1)。小结与复杂度对照维度0-1 背包完全背包物品数量每种 1 个每种无限选物品后的状态转移dp[i-1][c - wgt[i-1]]dp[i][c - wgt[i-1]]一维优化时内循环倒序range(cap, 0, -1)正序range(1, cap 1)时间复杂度O(n × cap)O(n × cap)空间复杂度优化后O(cap)O(cap)掌握本文后可以验证几个要点完全背包与 0-1 背包的全部差异浓缩在一维下标ivsi-1与遍历方向正序 vs 倒序上空间优化的正确性完全由左边的值是否应为本轮新值这一需求决定。相关代码集中在 codes/python/chapter_dynamic_programming/unbounded_knapsack.py 与 codes/python/chapter_dynamic_programming/knapsack.py可直接运行对比两者在相同输入下的行为差异配套的逐步图解位于 完全背包章节文档 及其unbounded_knapsack_problem.assets/图片目录中。【免费下载链接】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），仅供参考