完全背包问题全面解析状态转移推导、正序空间优化与零钱兑换双变体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本文围绕《Hello 算法》完全背包问题一节对应俄语版 unbounded_knapsack_problem.md展开先厘清完全背包与 0-1 背包在物品可重复选取上的本质差异再推导二维dp状态转移方程、讲解一维空间优化为何必须正序遍历最后把同一套框架套用到零钱兑换最小硬币数与零钱兑换 II组合方案数两个典型变体上。读完你将掌握背包类 DP 的建模三步骤定状态、推转移、定边界能徒手区分反向遍历0-1与正向遍历完全背包的适用场景并可直接运行仓库内多语言代码验证结论。问题定义物品无限次的完全背包!!! question 给定 $n$ 个物品第 $i$ 个物品的重量为 $wgt[i-1]$、价值为 $val[i-1]$另有一个容量为 $cap$ 的背包。每个物品可以被选取任意多次求在不超过背包容量的前提下能装入的最大总价值。与 0-1 背包问题 相比唯一区别就是物品数量不受限。图 1 给出了书中配套的示例数据注意图中物品以索引 1 开头对应数组下标需减 1整个问题可以抽象为第 $i$ 个物品在决策时要么不拿要么拿一件。关键差异在于0-1 背包物品 $i$ 只有 1 件放入背包后只能继续从 $[i-1, c-wgt[i-1]]$ 状态递推即不再考虑它完全背包物品 $i$ 有无限件放入一件后仍然可以从前 $i$ 个物品中继续选择于是状态落到 $[i, c-wgt[i-1]]$。这一字之差正是推导全部差异的源头。状态定义与转移方程只改一处 i-1 → i沿用 0-1 背包的建模套路状态$[i, c]$表示从前 $i$ 个物品中选取、背包容积为 $c$ 时的最大价值记为 $dp[i, c]$决策对物品 $i$ 有两种选择状态的两种变化方式是不取物品 $i$容量不变转移到 $[i-1, c]$价值继承 $dp[i-1, c]$取一件物品 $i$容量消耗 $wgt[i-1]$、价值累加 $val[i-1]$转移到 $[i, c-wgt[i-1]]$价值为 $dp[i, c-wgt[i-1]] val[i-1]$。于是得到转移方程$$ dp[i, c] \max(dp[i-1, c], dp[i, c - wgt[i-1]] val[i-1]) $$边界条件没有物品$i0$或容量为 0$c0$时最大价值均为 0因此第一行与第一列初始化为 0若 $wgt[i-1] c$放不下只能执行不取分支。按 $i$、$c$ 递增的正序双层循环即可完成填表时间与空间复杂度均为 $O(n \times cap)$。仓库中的 Python 实现位于 unbounded_knapsack.pydef 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]代码文件内置了驱动用例wgt [1, 2, 3]、val [5, 11, 15]、cap 4每个物品重量 1/2/3、价值 5/11/15容量 4可推算最优解为取两件重量 2 的物品总价值 22。在仓库根目录直接运行验证python3 codes/python/chapter_dynamic_programming/unbounded_knapsack.py空间优化为什么完全背包要正序遍历与 0-1 背包一样二维dp可以压缩为一维数组。区别在于遍历方向恰好相反0-1 背包的状态依赖上一行的 $[i-1, c-wgt[i-1]]$。若一维数组从左到右更新左侧的 $dp[c-wgt[i-1]]$ 已在本轮被覆盖等效于把同一物品用了多次因此必须**从右到左倒序**遍历保证每件物品至多取一次完全背包需要允许再次取同一物品其转移依赖同一行左侧的 $dp[i, c-wgt[i-1]]$所以恰恰必须**从左到右正序**遍历——更新 $dp[c]$ 时读到的是本轮已经允许重复选取的状态从而自然实现无限件。这正是两个问题在压缩后代码上仅存的差别。对照参见同一章节的 knapsack_problem.md0-1 背包一节对倒序遍历的论证。压缩后的状态转移过程可参考书中图集unbounded_knapsack_dp_comp_step1.png至unbounded_knapsack_dp_comp_step6.png位于 unbounded_knapsack_problem.assets逐帧展示 $dp$ 一维数组如何被覆盖演进。实现只需去掉第一维并把内层循环改成for c in range(1, cap 1)正序遍历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: dp[c] dp[c] # 若超过背包容量则不选物品 i else: dp[c] max(dp[c], dp[c - wgt[i - 1]] val[i - 1]) return dp[cap]优化后空间复杂度由 $O(n \times cap)$ 降至 $O(cap)$时间复杂度仍为 $O(n \times cap)$。该dp_comp版本同样在同目录 unbounded_knapsack.py 内两种算法使用同一组用例并打印相同的最优价值。变体一零钱兑换求最少硬币数!!! question 给定 $n$ 种硬币第 $i$ 种面额为 $coins[i-1]$目标金额为 $amt$每种硬币可取无限枚。求凑出目标金额所需的最少硬币数若无法凑出返回 $-1$。图 2 给出了配套示例面额 1、2、5 三种硬币目标金额 11最优为1 5 5共 3 枚。与完全背包的映射关系零钱兑换是求最小化的完全背包特例对应关系与差异可整理为完全背包零钱兑换物品硬币物品重量 $wgt$硬币面额 $coins$背包容积 $cap$目标金额 $amt$最大化总价值最小化硬币数目标相反不超过容量即可必须恰好凑出金额精确匹配三步建模Step 1 · 定义状态子问题为用前 $i$ 种硬币恰好凑出金额 $a$ 所需的最少硬币数记作 $dp[i, a]$二维表尺寸为 $(n1) \times (amt1)$。Step 2 · 推导转移相比完全背包有两处变化——优化目标从max换为min每取一枚硬币数加 1而非加价值 $val$$$ dp[i, a] \min(dp[i-1, a], dp[i, a - coins[i-1]] 1) $$Step 3 · 确定边界$a 0$ 时不需要任何硬币因此整个首列 $dp[i, 0] 0$$i 0$没有硬币时凑不出任何正金额属于非法解应把整个首行 $dp[0, a]$ 置为 $\infty$让 $\min()$ 自动将其淘汰。用 amt1 哨兵规避整数溢出多数语言无法在int中表示 $\infty$若直接用int最大值转移中的1可能造成溢出。书中给出的工程化做法是用amt 1充当非法解标记——因为凑出金额 $amt$ 理论上最多也只需要 $amt$ 枚硬币面额为 1 时任何超过 $amt$ 的数值都必然代表无解。返回前检查 $dp[n, amt]$ 是否仍等于 $amt1$若是则返回 $-1$。参考实现见 coin_change.pyMAX amt 1贯穿始终空间优化版coin_change_dp_comp先整体填充MAX再单独令dp[0] 0def coin_change_dp_comp(coins: list[int], amt: int) - int: 零钱兑换空间优化后的动态规划 n len(coins) MAX amt 1 dp [MAX] * (amt 1) dp[0] 0 for i in range(1, n 1): # 正序遍历 for a in range(1, amt 1): if coins[i - 1] a: dp[a] dp[a] # 若超过目标金额则不选硬币 i else: dp[a] min(dp[a], dp[a - coins[i - 1]] 1) return dp[amt] if dp[amt] ! MAX else -1注意这里空间压缩后内层同样是正序遍历——这正是硬币可无限取的语义要求与完全背包一脉相承。填表过程可对照书中coin_change_dp_step1.png~coin_change_dp_step15.png的 15 帧图解同目录 assets 下。驱动用例为coins [1, 2, 5]、amt 4运行结果应返回 22 2python3 codes/python/chapter_dynamic_programming/coin_change.py变体二零钱兑换 II求组合方案数!!! question 给定 $n$ 种硬币面额为 $coins[i-1]$目标金额为 $amt$每种硬币可取无限枚。求凑出目标金额的不同硬币组合数。转移方程max/min 换成求和状态改为用前 $i$ 种硬币恰好凑出金额 $a$ 的组合方案数$dp$ 仍为 $(n1) \times (amt1)$。当前状态等于不取第 $i$ 种硬币与取一枚第 $i$ 种硬币两个分支的方案数之和$$ dp[i, a] dp[i-1, a] dp[i, a - coins[i-1]] $$边界条件也随之改变$a 0$不选任何硬币即可凑出 0是一种可行方案故整个首列 $dp[i, 0] 1$$i 0$没有硬币时凑不出任何正金额整个首行 $dp[0, a] 0$。实现见 coin_change_ii.py其驱动用例coins [1, 2, 5]、amt 5对应 4 种组合11111、1112、122、5返回dp[n][amt] 4。空间优化版仍只需去掉硬币种类维度并保持正序def coin_change_ii_dp_comp(coins: list[int], amt: int) - int: 零钱兑换 II空间优化后的动态规划 n len(coins) dp [0] * (amt 1) dp[0] 1 for i in range(1, n 1): # 正序遍历 for a in range(1, amt 1): if coins[i - 1] a: dp[a] dp[a] # 若超过目标金额则不选硬币 i else: dp[a] dp[a] dp[a - coins[i - 1]] return dp[amt]两个变体的时间复杂度均为 $O(n \times amt)$空间复杂度经压缩后为 $O(amt)$。三个问题一览与延伸阅读问题目标转移算子是否精确匹配非法/边界初始值完全背包价值最大$\max$否不超过容量首行首列为 0零钱兑换硬币数最少$\min$是恰好凑出首列 0、首行 $amt1$非法解零钱兑换 II组合数最多求和是恰好凑出首列 1、首行 0三个问题共享同一套物品无限次 → 转移依赖本轮左邻状态 → 一维压缩时正序遍历的核心规律差异只体现在目标算子max/min/求和与边界初值上。仓库在 chapter_dynamic_programming 目录下为每个问题都提供了配套的多语言实现与驱动测试例如Cunbounded_knapsack.c、coin_change.cJavacoin_change.java以Math.min与Arrays.fill(dp, MAX)展示哨兵初始化写法Go / C / Rust / TypeScript 等同名文件可对照查看不同语言如何表达∞哨兵与二维数组初始化关于 0-1 背包含为何倒序遍历的完整推导可继续阅读 knapsack_problem.md三个问题在 summary.md 与 dp_solution_pipeline.md 中还有更系统的归类总结。对照实验时只需修改各驱动用例的wgt/val/cap或coins/amt即可验证任意规模输入下的边界行为例如把零钱兑换中的硬币面额改为不含 1 的集合如[2, 5]、amt 1会触发dp[n][amt] MAX分支并返回 $-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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考