跳至主要內容

2026年秋第9次课

周子力大约 17 分钟教学文档算法设计与分析课程讲义动态规划硬币找零01背包状态压缩循环顺序

2026年秋第9次课

同样是“用一些规格凑出一个总量”,为什么有的状态保存True,有的保存最少枚数,有的保存最大价值?同样只用一维数组,为什么循环方向又不同?

上一次课通过买包子与最长公共子序列,讨论了状态值怎样转化为题目所求的答案。本课从买包子的可达性出发,先讲硬币找零问题,将“能否凑出”推进为“最少使用几枚”;再讲01背包问题,加入“每件只能选择一次”的限制,理解为何需要物品阶段,以及压缩空间后怎样保存这个限制。

本讲义用于贯穿课堂思路。各题的完整Python程序、输入输出、详细过程和分层练习集中在独立题目文档中;课堂围绕状态、转移、初始化、循环顺序与答案位置展开,不重复抄写完整实现。

学习目标

本课需要回答的五个问题

  • 优化的是什么? 区分能否凑出、最少使用次数、最大价值与组合数量。
  • 限制是什么? 分清每种无限使用和每件至多一次,以及恰好满足和不超过上限。
  • 状态为什么够用? 解释硬币找零为何可按金额递推,01背包为何先引入物品阶段。
  • 转移为什么合法? 从最后一枚硬币或当前物品选与不选出发,说明候选覆盖与最优子结构。
  • 压缩后读到哪一阶段? 判断一个数组位置保存的是旧值还是本轮新值,用具体反例解释循环方向。

课后应能手工推演两题的小规模状态表,写出关键更新语句,说明边界与无解处理,并根据“是否允许重复使用”检查一维更新顺序。

本课路线

顺序题目与材料入口课堂核心问题与已有知识的衔接
复习买包子已知某个数量可达,怎样比较到达它的成本?从布尔可达性转向最小值
1硬币找零问题最后一枚硬币来自哪种面额?无限使用、恰好凑出、min转移
201背包问题选当前物品后,剩余部分还能用它吗?物品阶段、容量上限、max转移
对照完全背包问题、零钱兑换使用次数和求解目标变化后,哪些规则必须跟着改变?正序与倒序、最优值与计数

本课按2学时90分钟组织:

环节时间内容课堂产出
复习热身8分钟用买包子回顾可达性,比较同一目标的三种提问区分True、最少枚数与组合数
精讲一20分钟硬币找零:最后一枚、边界、不可达标记、贪心反例手算金额0到11的最少枚数
编码与核对12分钟阅读题解Python主实现,运行可达、无解、零金额用例对齐代码、状态与返回值
精讲二25分钟01背包:选与不选、二维表、一维倒序解释主示例最大价值8的来源
动手与纠错20分钟独立完成课堂任务,修改正序误用与初始化错误用小例子证明错误而非只背口诀
方法复盘5分钟比较状态含义、使用限制、循环顺序和复杂度形成两题对照表

若安排3学时,可增加01背包二维版与一维版的逐行对照,以及“恰好装满”的边界改写。具体方案恢复留作后续扩展,本课两题均只要求最优值。

题目串联

一、从买包子出发:同一个组合模型,不同的问题目标

用容量为3、4的蒸笼凑6个包子,可以取两笼3个的,因此可达性为True。若进一步要求使用的笼数最少,答案就是2。

将“一笼包子数”换成“硬币面额”,就得到硬币找零的最小值问题。两者都允许每种规格无限使用,都可以写成非负整数选择:

a1x1+a2x2+⋯+anxn=s,xi≥0. a_1x_1+a_2x_2+\cdots+a_nx_n=s,\qquad x_i\geq0.

问题状态应保存什么如何合并候选
能否凑出sTrue或False有一个来源可达即可,用逻辑或
凑出s最少用几枚最少枚数,不可达时记无穷大子状态加1,再取min
凑出s共有几种组合组合数量对不重复的类别求和

例如面额 [1,2,5]、目标5,三个问题的答案依次是True、1、4。不能因为都在做“凑数”,就沿用同一种状态或初始化。

买包子的完整任务还要统计凑不出的正整数数量,并判断答案是否可能无穷。本课硬币找零只求一个指定目标,不需要寻找所有不可达数的统计上界。

二、硬币找零:根据最后一枚硬币定义最优值

题目材料、完整Python实现与练习:硬币找零问题。

明确任务与状态

面额均为正整数,每种无限使用,要求恰好凑出目标金额A,返回最少枚数;无解返回−1,金额0返回0。

定义 D(s)D(s):使用全部给定面额,恰好凑出金额s所需的最少硬币枚数。

D(0)=0,D(s)=+∞(s>0,初始). D(0)=0,\qquad D(s)=+\infty\quad(s>0\text{,初始}).

正金额不能初始化为0,否则意味着“不拿硬币就能凑出正金额”。这也与组合计数中“空组合有一种”的初始化不同:本题状态记录的是枚数。

枚举最后一枚,说明为什么取min

若最后一枚面额为c,去掉它后,剩余金额为s−c;若该金额可达,一种候选的枚数为 D(s−c)+1D(s-c)+1。

D(s)=min⁡c∈coinsc≤s(D(s−c)+1). D(s)=\min_{\substack{c\in coins\\c\leq s}}\bigl(D(s-c)+1\bigr).

所有凑出s的方案都包含某一枚可作为最后加入的硬币,枚举所有面额就覆盖了最优方案。固定c后,若剩余部分不是凑出s−c的最优方案,可以换成更少枚数的方案,再加回c,仍然合法。

面额为正保证s−c<s,所以按金额从小到大计算,依赖总已求出。同一组硬币可能按不同顺序被比较到,但取最小值不会把它重复计数。

为什么这里不需要记录“上一枚是哪种面额”? 每种面额无限可用,到达某个金额后,所有面额仍可继续选择;历史使用过哪些面额不影响下一步是否合法。只保存达到该金额的最少枚数就足够。

主示例:让每个状态都有明确解释

使用 coins = [1,2,5],目标11:

金额s01234567891011
D(s)011221223323

最后一步的候选为:

D(11)=min⁡(D(10)+1, D(9)+1, D(6)+1)=min⁡(3,4,3)=3. D(11)=\min(D(10)+1,\ D(9)+1,\ D(6)+1) =\min(3,4,3)=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的时间为 O(nA)O(nA)、辅助空间为 O(A)O(A);包括A=0边界时可写为 O(n(A+1))O(n(A+1)) 时间、O(A+1)O(A+1) 空间。

两个值得现场检验的判断

“每次取最大面额”不保证最少枚数:[1,3,4]凑6,贪心得到4+1+1共3枚,最优为3+3共2枚。

“最大公约数为1”也不保证某个指定金额可达:[3,4]凑5仍然无解。最大公约数不整除目标时可以提前排除,但整除只是必要条件。

衔接01背包: 如果不再允许某种规格无限使用,而是每件物品只剩一件,达到相同容量时,过去用过哪些物品会影响后续选择吗?只保留容量一个下标,还能直接照搬上述推导吗?

三、01背包:引入物品阶段,把“只能选一次”写进状态

题目材料、完整Python实现与练习:01背包问题。

先读清两个独立变化

有N件物品,体积、价值为vᵢ、wᵢ,背包容量V;每件最多选一次,求总体积不超过V时的最大价值。

与硬币找零相比,使用次数从无限变成每件至多一次,目标也从“恰好金额的最少枚数”变成“容量上限内的最大价值”。这两个条件都必须反映到状态与边界中。

这里不同历史方案可能已经用过不同物品,不能在只知剩余容量的情况下任意再追加一件。解决方法是固定物品处理顺序,让每一阶段只对一件新物品作选或不选的决策。

定义二维状态,分类当前物品

定义 F(i,j)F(i,j):只考虑前i件物品,总体积不超过j时,能够取得的最大价值。

F(0,j)=0,F(i,0)=0. F(0,j)=0,\qquad F(i,0)=0.

题目允许不装满,也允许不选任何物品,且物品体积为正。因此所有容量上限都存在价值0的空选择,可以全0初始化。

考虑第i件物品时:

决策剩余问题候选价值
不选前i−1件,容量上限仍为jF(i−1,j)F(i-1,j)
选择,且j≥vᵢ前i−1件,容量上限变为j−vᵢF(i−1,j−vi)+wiF(i-1,j-v_i)+w_i

F(i,j)={F(i−1,j),j<vi,max⁡(F(i−1,j),F(i−1,j−vi)+wi),j≥vi. F(i,j)= \begin{cases} F(i-1,j), & j<v_i,\\ \max\bigl(F(i-1,j),F(i-1,j-v_i)+w_i\bigr), & j\geq v_i. \end{cases}

两种选择都读取上一行。选了当前物品之后,剩余部分只允许使用前i−1件,才能保证当前物品不再出现。

所有合法方案恰好分成选与不选两类;固定当前选择后,替换为剩余容量下更优的前缀方案不会破坏合法性。因此取两类最大值即可,最终答案为 F(N,V)F(N,V)。

主示例:不能把“放得下”当成“应该选”

物品依次为 [(1,2), (2,4), (3,4), (4,5)],元组表示体积、价值,容量V=5:

已考虑物品容量0容量1容量2容量3容量4容量5
0件000000
第1件后022222
第2件后024666
第3件后024668
第4件后024668

第3件使容量5的结果改善:

F(3,5)=max⁡(F(2,5),F(2,2)+4)=max⁡(6,8)=8. F(3,5)=\max(F(2,5),F(2,2)+4)=\max(6,8)=8.

对应选择第2、3件,总体积2+3=5,价值4+4=8。

第4件虽然放得下,选择它却只能得到 F(3,1)+5=7F(3,1)+5=7,小于不选它时的8。因此最后一个状态保留8,最优方案并不包含最后一件。

压缩空间后,物品阶段不能丢

主实现用一个数组代替二维表,依次遍历物品,将容量从V倒序更新到当前体积v:dp[j] = max(dp[j], dp[j - v] + w)。

处理当前物品前,数组表示上一行。因为j−v<j,倒序时较小位置本轮尚未更新,仍是上一行值;因此只是复用存储空间,物品阶段在循环中仍然存在。

只有一件 (2,3)、容量4时:

更新方式计算容量4时读到的dp[2]最终最大价值
倒序上一阶段的03
正序本轮刚更新的36,重复选了唯一物品

这里的循环方向不是编程习惯,而是在决定能否读取本轮新值。二维独立保存上一行时,容量正序或倒序都可以;一维原地01背包才需要倒序。

原题N、V均不超过1000,一维主实现时间为 O(NV)O(NV),辅助空间为 O(V)O(V);二维教学版时间同为 O(NV)O(NV),辅助空间为 O(NV)O(NV)。压缩减少同时保存的数据,没有减少必须处理的状态数量。

方法比较

比较角度硬币找零01背包
求解目标恰好凑出金额的最少枚数体积不超过容量的最大价值
使用限制每种面额无限使用每件物品最多一次
基础状态D(s):全部面额下,凑出s的最少枚数F(i,j):前i件、容量上限j的最大价值
决策最后一枚面额是什么当前物品选或不选
候选合并加一枚后取min加当前价值后与不选取max
初始化0金额为0,正金额先设不可达无物品、容量0为0,全0初始化合法
本课主实现顺序金额递增,再枚举面额物品逐个引入,容量倒序
答案位置dp[A],不可达标记转为−1dp[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]。

D(6)=min⁡(D(5)+1,D(3)+1,D(2)+1)=min⁡(3,2,3)=2. D(6)=\min(D(5)+1,D(3)+1,D(2)+1)=\min(3,2,3)=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枚完全合法。两题对重复使用的规定不同,不能共用同一种来源限制。

任务五:初始化、无解与容量语义

判断以下说法并给出反例或理由:

  1. 硬币找零把所有状态初始化为0,也能通过min更新修正。
  2. 01背包只有物品 (3,5)、容量4,答案应为0,因为无法装满。
  3. 所有面额的最大公约数为1,就能保证指定目标有解。
  4. 01背包用了二维表,容量也必须倒序。
参考答案

四句都不成立。

  1. 0会小于所有正枚数候选,min无法把它更新为合法正值。正金额必须初始化为不可达。
  2. 本题不要求装满,选该物品得到价值5即为最优;只有改为“恰好装满”的变式才应报告无解。
  3. [3,4]的最大公约数为1,目标5仍然无法凑出;它只能保证充分大的整数可达,不能保证每个小目标可达。
  4. 二维01背包的两个分支均读取独立的上一行,所以容量正序或倒序都可以;倒序限制针对一维原地压缩。

课后实践: 分别运行两题独立文档中的Python主实现。硬币找零至少核对 [1,2,5]→11、[2]→3、[1]→0、[1,3,4]→6;01背包核对主示例、单件 (2,3) 容量4、两件相同的 (2,3) 容量4、所有物品都放不下四种情况。提交状态定义、边界、关键更新与运行结果,并用一句话说明循环顺序在保留什么信息。

后续对照阅读:完全背包问题、零钱兑换。前者改变每种物品的使用次数,后者改变状态所求的量,均应先重新解释状态,再调整代码。

上次编辑于:
贡献者: zlzhou