2026年秋第9次课
2026年秋第9次课
同样是“用一些规格凑出一个总量”,为什么有的状态保存True,有的保存最少枚数,有的保存最大价值?同样只用一维数组,为什么循环方向又不同?
上一次课通过买包子与最长公共子序列,讨论了状态值怎样转化为题目所求的答案。本课从买包子的可达性出发,先讲硬币找零问题,将“能否凑出”推进为“最少使用几枚”;再讲01背包问题,加入“每件只能选择一次”的限制,理解为何需要物品阶段,以及压缩空间后怎样保存这个限制。
本讲义用于贯穿课堂思路。各题的完整Python程序、输入输出、详细过程和分层练习集中在独立题目文档中;课堂围绕状态、转移、初始化、循环顺序与答案位置展开,不重复抄写完整实现。
学习目标
本课需要回答的五个问题
- 优化的是什么? 区分能否凑出、最少使用次数、最大价值与组合数量。
- 限制是什么? 分清每种无限使用和每件至多一次,以及恰好满足和不超过上限。
- 状态为什么够用? 解释硬币找零为何可按金额递推,01背包为何先引入物品阶段。
- 转移为什么合法? 从最后一枚硬币或当前物品选与不选出发,说明候选覆盖与最优子结构。
- 压缩后读到哪一阶段? 判断一个数组位置保存的是旧值还是本轮新值,用具体反例解释循环方向。
课后应能手工推演两题的小规模状态表,写出关键更新语句,说明边界与无解处理,并根据“是否允许重复使用”检查一维更新顺序。
本课路线
| 顺序 | 题目与材料入口 | 课堂核心问题 | 与已有知识的衔接 |
|---|---|---|---|
| 复习 | 买包子 | 已知某个数量可达,怎样比较到达它的成本? | 从布尔可达性转向最小值 |
| 1 | 硬币找零问题 | 最后一枚硬币来自哪种面额? | 无限使用、恰好凑出、min转移 |
| 2 | 01背包问题 | 选当前物品后,剩余部分还能用它吗? | 物品阶段、容量上限、max转移 |
| 对照 | 完全背包问题、零钱兑换 | 使用次数和求解目标变化后,哪些规则必须跟着改变? | 正序与倒序、最优值与计数 |
本课按2学时90分钟组织:
| 环节 | 时间 | 内容 | 课堂产出 |
|---|---|---|---|
| 复习热身 | 8分钟 | 用买包子回顾可达性,比较同一目标的三种提问 | 区分True、最少枚数与组合数 |
| 精讲一 | 20分钟 | 硬币找零:最后一枚、边界、不可达标记、贪心反例 | 手算金额0到11的最少枚数 |
| 编码与核对 | 12分钟 | 阅读题解Python主实现,运行可达、无解、零金额用例 | 对齐代码、状态与返回值 |
| 精讲二 | 25分钟 | 01背包:选与不选、二维表、一维倒序 | 解释主示例最大价值8的来源 |
| 动手与纠错 | 20分钟 | 独立完成课堂任务,修改正序误用与初始化错误 | 用小例子证明错误而非只背口诀 |
| 方法复盘 | 5分钟 | 比较状态含义、使用限制、循环顺序和复杂度 | 形成两题对照表 |
若安排3学时,可增加01背包二维版与一维版的逐行对照,以及“恰好装满”的边界改写。具体方案恢复留作后续扩展,本课两题均只要求最优值。
题目串联
一、从买包子出发:同一个组合模型,不同的问题目标
用容量为3、4的蒸笼凑6个包子,可以取两笼3个的,因此可达性为True。若进一步要求使用的笼数最少,答案就是2。
将“一笼包子数”换成“硬币面额”,就得到硬币找零的最小值问题。两者都允许每种规格无限使用,都可以写成非负整数选择:
| 问题 | 状态应保存什么 | 如何合并候选 |
|---|---|---|
| 能否凑出s | True或False | 有一个来源可达即可,用逻辑或 |
| 凑出s最少用几枚 | 最少枚数,不可达时记无穷大 | 子状态加1,再取min |
| 凑出s共有几种组合 | 组合数量 | 对不重复的类别求和 |
例如面额 [1,2,5]、目标5,三个问题的答案依次是True、1、4。不能因为都在做“凑数”,就沿用同一种状态或初始化。
买包子的完整任务还要统计凑不出的正整数数量,并判断答案是否可能无穷。本课硬币找零只求一个指定目标,不需要寻找所有不可达数的统计上界。
二、硬币找零:根据最后一枚硬币定义最优值
题目材料、完整Python实现与练习:硬币找零问题。
明确任务与状态
面额均为正整数,每种无限使用,要求恰好凑出目标金额A,返回最少枚数;无解返回−1,金额0返回0。
定义 :使用全部给定面额,恰好凑出金额s所需的最少硬币枚数。
正金额不能初始化为0,否则意味着“不拿硬币就能凑出正金额”。这也与组合计数中“空组合有一种”的初始化不同:本题状态记录的是枚数。
枚举最后一枚,说明为什么取min
若最后一枚面额为c,去掉它后,剩余金额为s−c;若该金额可达,一种候选的枚数为 。
所有凑出s的方案都包含某一枚可作为最后加入的硬币,枚举所有面额就覆盖了最优方案。固定c后,若剩余部分不是凑出s−c的最优方案,可以换成更少枚数的方案,再加回c,仍然合法。
面额为正保证s−c<s,所以按金额从小到大计算,依赖总已求出。同一组硬币可能按不同顺序被比较到,但取最小值不会把它重复计数。
为什么这里不需要记录“上一枚是哪种面额”? 每种面额无限可用,到达某个金额后,所有面额仍可继续选择;历史使用过哪些面额不影响下一步是否合法。只保存达到该金额的最少枚数就足够。
主示例:让每个状态都有明确解释
使用 coins = [1,2,5],目标11:
| 金额s | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| D(s) | 0 | 1 | 1 | 2 | 2 | 1 | 2 | 2 | 3 | 3 | 2 | 3 |
最后一步的候选为:
一种达到最优值的组合是5+5+1。程序返回3,不是输出组合本身,也不是统计有几种组合。
再用 [2]、目标3检查无解:金额1不可达,金额3唯一可能依赖的金额1也不可达,因此保持不可达并返回−1。
关键实现与复杂度
题解的Python主实现采用“金额递增在外、枚举面额在内”,关键更新为 dp[s] = min(dp[s], dp[s - coin] + 1),并检查来源可达。
用A+1代替无穷大是安全的:因为面额至少为1,凑出A的合法方案最多使用A枚。最终标记未改变才返回−1;不要在内部直接使用−1参与最小值比较。
按整数基本运算为单位成本,n种面额、正目标A的时间为 、辅助空间为 ;包括A=0边界时可写为 时间、 空间。
两个值得现场检验的判断
“每次取最大面额”不保证最少枚数:[1,3,4]凑6,贪心得到4+1+1共3枚,最优为3+3共2枚。
“最大公约数为1”也不保证某个指定金额可达:[3,4]凑5仍然无解。最大公约数不整除目标时可以提前排除,但整除只是必要条件。
衔接01背包: 如果不再允许某种规格无限使用,而是每件物品只剩一件,达到相同容量时,过去用过哪些物品会影响后续选择吗?只保留容量一个下标,还能直接照搬上述推导吗?
三、01背包:引入物品阶段,把“只能选一次”写进状态
题目材料、完整Python实现与练习:01背包问题。
先读清两个独立变化
有N件物品,体积、价值为vᵢ、wᵢ,背包容量V;每件最多选一次,求总体积不超过V时的最大价值。
与硬币找零相比,使用次数从无限变成每件至多一次,目标也从“恰好金额的最少枚数”变成“容量上限内的最大价值”。这两个条件都必须反映到状态与边界中。
这里不同历史方案可能已经用过不同物品,不能在只知剩余容量的情况下任意再追加一件。解决方法是固定物品处理顺序,让每一阶段只对一件新物品作选或不选的决策。
定义二维状态,分类当前物品
定义 :只考虑前i件物品,总体积不超过j时,能够取得的最大价值。
题目允许不装满,也允许不选任何物品,且物品体积为正。因此所有容量上限都存在价值0的空选择,可以全0初始化。
考虑第i件物品时:
| 决策 | 剩余问题 | 候选价值 |
|---|---|---|
| 不选 | 前i−1件,容量上限仍为j | |
| 选择,且j≥vᵢ | 前i−1件,容量上限变为j−vᵢ |
两种选择都读取上一行。选了当前物品之后,剩余部分只允许使用前i−1件,才能保证当前物品不再出现。
所有合法方案恰好分成选与不选两类;固定当前选择后,替换为剩余容量下更优的前缀方案不会破坏合法性。因此取两类最大值即可,最终答案为 。
主示例:不能把“放得下”当成“应该选”
物品依次为 [(1,2), (2,4), (3,4), (4,5)],元组表示体积、价值,容量V=5:
| 已考虑物品 | 容量0 | 容量1 | 容量2 | 容量3 | 容量4 | 容量5 |
|---|---|---|---|---|---|---|
| 0件 | 0 | 0 | 0 | 0 | 0 | 0 |
| 第1件后 | 0 | 2 | 2 | 2 | 2 | 2 |
| 第2件后 | 0 | 2 | 4 | 6 | 6 | 6 |
| 第3件后 | 0 | 2 | 4 | 6 | 6 | 8 |
| 第4件后 | 0 | 2 | 4 | 6 | 6 | 8 |
第3件使容量5的结果改善:
对应选择第2、3件,总体积2+3=5,价值4+4=8。
第4件虽然放得下,选择它却只能得到 ,小于不选它时的8。因此最后一个状态保留8,最优方案并不包含最后一件。
压缩空间后,物品阶段不能丢
主实现用一个数组代替二维表,依次遍历物品,将容量从V倒序更新到当前体积v:dp[j] = max(dp[j], dp[j - v] + w)。
处理当前物品前,数组表示上一行。因为j−v<j,倒序时较小位置本轮尚未更新,仍是上一行值;因此只是复用存储空间,物品阶段在循环中仍然存在。
只有一件 (2,3)、容量4时:
| 更新方式 | 计算容量4时读到的dp[2] | 最终最大价值 |
|---|---|---|
| 倒序 | 上一阶段的0 | 3 |
| 正序 | 本轮刚更新的3 | 6,重复选了唯一物品 |
这里的循环方向不是编程习惯,而是在决定能否读取本轮新值。二维独立保存上一行时,容量正序或倒序都可以;一维原地01背包才需要倒序。
原题N、V均不超过1000,一维主实现时间为 ,辅助空间为 ;二维教学版时间同为 ,辅助空间为 。压缩减少同时保存的数据,没有减少必须处理的状态数量。
方法比较
| 比较角度 | 硬币找零 | 01背包 |
|---|---|---|
| 求解目标 | 恰好凑出金额的最少枚数 | 体积不超过容量的最大价值 |
| 使用限制 | 每种面额无限使用 | 每件物品最多一次 |
| 基础状态 | D(s):全部面额下,凑出s的最少枚数 | F(i,j):前i件、容量上限j的最大价值 |
| 决策 | 最后一枚面额是什么 | 当前物品选或不选 |
| 候选合并 | 加一枚后取min | 加当前价值后与不选取max |
| 初始化 | 0金额为0,正金额先设不可达 | 无物品、容量0为0,全0初始化合法 |
| 本课主实现顺序 | 金额递增,再枚举面额 | 物品逐个引入,容量倒序 |
| 答案位置 | dp[A],不可达标记转为−1 | dp[V],不要求用满V |
| 时间与辅助空间 | 正目标下O(nA)、O(A) | 原题范围内O(NV)、O(V) |
循环方向必须连同模型与状态一起判断
| 写法 | 使用规则 | 为什么这样安排 |
|---|---|---|
| 金额递增、面额在内,取min | 面额无限使用的最少枚数 | 较小金额的结果可直接追加任何面额 |
| 面额在外、金额正序,取min | 同样可以求无限使用的最少枚数 | 本轮新状态允许继续使用当前面额 |
| 物品在外、容量倒序,取max | 每件最多使用一次 | 来源仍为上一物品阶段 |
| 物品在外、容量正序,取max | 每种可以无限使用 | 来源可含本轮已经使用的当前物品 |
这些是明确状态与存储方式之后的结论。尤其要区分两点:最小值重复比较同一方案不会改变结果,而计数求和可能把不同顺序重复累计;“恰好装满”的最大价值也不能沿用本题全0初始化,应将非零体积初始设为不可达。
本课的解题检查顺序
先读出使用次数与总量约束,再确定状态保存可达性、最小值还是最大值;根据最后一次决策列出候选,说明依赖哪个阶段;最后安排循环与存储,核对答案位置,并用零状态、不可达和重复使用反例验证。
课堂任务
任务一:同样的面额,回答不同问题
对 [1,2,5]、目标5,分别回答:能否凑出、最少几枚、共有几种组合?写出这三种状态在目标0时各自的起点值。
参考答案
三个答案分别为True、1、4。
目标0时:可达性为True;最少枚数为0;组合数为1,对应唯一空组合。三者都从“不作选择”出发,但状态记录的量不同,不能照搬同一个初始值。
任务二:手算最少枚数并反驳贪心
对 coins=[1,3,4]、目标6,写出D(0)到D(6),展开最后一个状态,说明为什么最大面额优先不保证最优。
参考答案
状态表为 [0,1,2,1,1,2,2]。
最优为3+3共2枚;最大面额优先得到4+1+1共3枚。候选必须比较整体枚数,不能只看当前面额大小。
任务三:读懂二维表中的物品阶段
01背包主示例中,说明F(2,5)、F(3,5)、F(4,5)的值,分别指出新增物品为什么会或不会改善结果。F(1,5)=2是否表示背包装满了?
参考答案
三个值分别为6、8、8。前两件都选,体积3、价值6;第3件与第2件搭配得到8;第4件若选择,只能与容量1下的价值2搭配,总价值7,不如保留8。
F(1,5)=2只表示容量上限5时,第一件物品最多贡献价值2,实际体积仅为1,不要求用满。
任务四:用一件物品检查循环方向
只有一件体积2、价值3的物品,容量4。分别写出一维正序与倒序处理后的数组。再比较硬币只有面额2、目标金额4时,为什么允许得到使用2枚的答案。
参考答案
01背包初始为 [0,0,0,0,0]。正序后得到 [0,0,3,3,6],错误地用同一件物品两次;倒序后为 [0,0,3,3,3],每件最多使用一次。
硬币找零中面额2无限供应,金额2的最优结果可以继续加一枚2元,金额4需要2枚完全合法。两题对重复使用的规定不同,不能共用同一种来源限制。
任务五:初始化、无解与容量语义
判断以下说法并给出反例或理由:
- 硬币找零把所有状态初始化为0,也能通过min更新修正。
- 01背包只有物品
(3,5)、容量4,答案应为0,因为无法装满。 - 所有面额的最大公约数为1,就能保证指定目标有解。
- 01背包用了二维表,容量也必须倒序。
参考答案
四句都不成立。
- 0会小于所有正枚数候选,min无法把它更新为合法正值。正金额必须初始化为不可达。
- 本题不要求装满,选该物品得到价值5即为最优;只有改为“恰好装满”的变式才应报告无解。
[3,4]的最大公约数为1,目标5仍然无法凑出;它只能保证充分大的整数可达,不能保证每个小目标可达。- 二维01背包的两个分支均读取独立的上一行,所以容量正序或倒序都可以;倒序限制针对一维原地压缩。
课后实践: 分别运行两题独立文档中的Python主实现。硬币找零至少核对 [1,2,5]→11、[2]→3、[1]→0、[1,3,4]→6;01背包核对主示例、单件 (2,3) 容量4、两件相同的 (2,3) 容量4、所有物品都放不下四种情况。提交状态定义、边界、关键更新与运行结果,并用一句话说明循环顺序在保留什么信息。
后续对照阅读:完全背包问题、零钱兑换。前者改变每种物品的使用次数,后者改变状态所求的量,均应先重新解释状态,再调整代码。
