买包子
买包子
基础 完全背包 裴蜀定理 Python蒸笼容量是 4 和 5,为什么凑不出的数目恰好是 6 个;换成 4 和 6,答案却变成 INF?
本节学习目标
- 会建模: 把“若干笼包子恰好凑成 个”转成完全背包的可达性状态,并先用最大公约数区分有限与无穷两种答案。
- 会追踪: 按
[4, 5]逐步填写可达数组,说明内层循环为什么要从小到大,以及从哪一处开始可以停止统计。 - 会核对: 检查
INF分支、样例中 与容量的位置、上界 10000 的来源,以及“凑不出的个数”与“最大凑不出的数”的区别。
题目描述
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 种蒸笼,其中第 种蒸笼恰好能放 个包子。每种蒸笼都有非常多笼,可以认为是无限笼。
每当有顾客想买 个包子,卖包子的大叔就会迅速选出若干笼,使这若干笼中恰好一共有 个包子。比如一共有 3 种蒸笼,分别能放 3、4 和 5 个包子;顾客想买 11 个时,大叔会选 2 笼 3 个的再加 1 笼 5 个的(也可能选 1 笼 3 个的再加 2 笼 4 个的)。
当然有时大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼,分别能放 4、5 和 6 个包子,顾客想买 7 个时就凑不出来。本题要统计:一共有多少种正整数数目是凑不出来的。
参数、结果与输入格式
- 输入共 个整数:第一行是蒸笼种类数 (),随后给出每种容量 ()。官方题面把 写成 行,样例常压缩成一行;按空白分隔读取时两种排版等价。
- 每种蒸笼可以取无限多笼,容量允许重复。题目只要求统计数量,不要求输出选笼方案。
- 输出一个整数,表示凑不出的正整数个数;若这样的数有无穷多个,输出
INF。 - 个包子视为一笼都不选,一定可凑出,且它不是正整数,不计入答案。
- 样例中的第一个数是 ,不是第一种容量。
10000 不是输入上限
题目给出的约束是 。常见的 10000 是解题时为枚举范围取的上界,把两者混淆,就无法说清这个数字从哪来、什么时候会失效。推导见统计到哪里为止。
贯穿示例
输入: 2 4 5
输出: 6
说明: N=2,容量为 4 和 5;凑不出的正整数是 1, 2, 3, 6, 7, 11,共 6 个。
输入: 2 4 6
输出: INF
说明: 两种容量都是偶数,所有奇数都凑不出,有无穷多个。
全文用 [4, 5] 作主示例,[4, 6] 用来对照 INF 分支。
配套视频解析
题目分析
从枚举组合到完全背包可达性
设第 种蒸笼选了 笼,题目就是判断方程
是否有解,并统计无解的 有多少个。 没有上限、每种容量可重复使用,这是完全背包;与01背包问题里每种物品最多取一次不同。
本题求的是“能否凑出”,不是“有多少种凑法”,所以状态取布尔值就够了。也不要把它和买不到的数字混为一谈:那题求最大的凑不出的数,本题求凑不出的数的个数。
先分情况:什么时候会有无穷多个
核心结论
记 。若 ,任何组合都是 的倍数,所有非 倍数的正整数都凑不出,答案直接是 INF;只有 时才需要用动态规划数出那有限多个凑不出的数。
由裴蜀定理, 时存在整数组合得到 1;在 的前提下,所有足够大的正整数都能用非负系数凑出,因此不可凑出的只有有限个。
这一步必须放在动态规划之前。对 的用例,无论把数组开多大,数出来的都只是“上界以内”的假答案。例如 [4, 6] 的 ,可凑出的全是偶数;[7] 的 ,可凑出的全是 7 的倍数,二者都输出 INF。
定义状态与转移
定义布尔状态 dp[x]:只用已经处理过的蒸笼容量,能否恰好凑出 个包子。
依次把每种容量 加入可选集合。对每个 ,若加入前 dp[x - a] 已为真,再取一笼 就能凑出 :
其中 是枚举上界。 从小到大遍历时,dp[x - a] 在本轮可能刚被更新,正好表示同一容量被取用多次。
为什么内层必须从小到大
若内层改成从大到小,dp[x - a] 在本轮还未更新,每种容量最多只能用一次,模型退化成 01 背包。
以 [4, 5] 的 为例: 需要同一轮两次使用容量 5。从大到小时处理 ,dp[5] 仍为假,10 会被误判为凑不出;从小到大时, 已把 dp[5] 置真,随后 才能读到它。
统计到哪里为止
只把数组开到某个上界还不够,必须说明上界之外的整数都可达。
停止条件
设 。若从 开始出现连续 个可达整数 ,则任意 都可写成其中某一个再加上若干个 ,因而全部可达。
主实现据此在填表后扫描最早出现的连续 个可达数,只统计它之前的不可达正整数。
上界取 :在模 的每个余数类里,最小可达数可看作 个余数节点上的最短路,最多经过 条边、每边权不超过 ,故小于 ;再由停止条件, 之后的整数全部可达。当 时 ,这正是竞赛代码里直接写 10000 的来历——它是范围保证下的经验上界,不是题目的输入约束。
为什么结果正确
- gcd 分支: 时所有组合都是 的倍数,非倍数有无穷多个,返回
INF与题意一致。 - 可达性等价:
dp[x]为真当且仅当存在非负整数 使 。按容量依次加入、内层递增遍历,恰好覆盖了“最后一次取的是当前容量”的所有组合,不重不漏;重复容量去重后也不改变可达集合。 - 统计范围:连续 个可达数之后全部可达,窗口之前逐个检查,既不会漏掉小的不可达数,也不会把上界之外无限延伸的情况误算进来。
实现代码
Python 主实现
count_unreachable(capacities) 返回凑不出的正整数个数,或在无穷多时返回字符串 "INF"。以下程序可完整复制到 Python 文件中运行。
from functools import reduce
from math import gcd
def count_unreachable(capacities):
"""返回凑不出的正整数个数;若有无穷多个,返回字符串 'INF'。"""
sizes = sorted(set(capacities))
if not sizes or sizes[0] <= 0:
raise ValueError("蒸笼容量必须是正整数列表")
# 第一步:裴蜀定理,gcd > 1 时凑不出的数有无穷多个。
if reduce(gcd, sizes) > 1:
return "INF"
# 第二步:gcd = 1 时不可凑出的数有限,取上界 max(A)^2。
limit = sizes[-1] ** 2
reachable = [False] * (limit + 1)
reachable[0] = True
for a in sizes:
for x in range(a, limit + 1):
if reachable[x - a]:
reachable[x] = True
# 第三步:找到最早连续 min(A) 个可达数,之后的整数都可达。
m, run = sizes[0], 0
for x in range(limit + 1):
run = run + 1 if reachable[x] else 0
if run == m:
return sum(1 for t in range(1, x - m + 1) if not reachable[t])
raise RuntimeError("上界不足:请增大 limit")
if __name__ == "__main__":
cases = [[4, 5], [4, 6], [3, 4], [1, 5], [7], [4, 5, 6], [6, 10, 15]]
for caps in cases:
print(f"{caps} -> {count_unreachable(caps)}")
输出:
[4, 5] -> 6
[4, 6] -> INF
[3, 4] -> 3
[1, 5] -> 0
[7] -> INF
[4, 5, 6] -> 4
[6, 10, 15] -> 15
sorted(set(...)) 去重只影响循环次数,不改变可达集合。run 记录当前连续可达的长度,第一次达到 时即可返回,不必枚举到 limit 末尾;若始终达不到,说明上界不足,应报错而不是悄悄返回一个偏小的答案。
读取题目输入
把主实现保存成文件后,将示例用的 if __name__ == "__main__": 代码块替换为下面 4 行,就是可直接提交的入口。split() 不区分空格与换行,因此官方的 行排版与样例的一行排版都能读取。
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
print(count_unreachable(data[1:1 + n]))
这一段依赖同一文件中已定义的 count_unreachable,不是独立程序;直接运行它没有标准输入会读到空列表。
竞赛简写版(固定上界)
如果确信 ,可以把上界固定为 10000,省去窗口扫描。该程序也可独立运行。
from functools import reduce
from math import gcd
LIMIT = 10000 # 官方数据 1 <= Ai <= 100
def solve(capacities):
if reduce(gcd, capacities) > 1:
return "INF"
reachable = [False] * (LIMIT + 1)
reachable[0] = True
for a in set(capacities):
for x in range(a, LIMIT + 1):
reachable[x] = reachable[x] or reachable[x - a]
return sum(not reachable[x] for x in range(1, LIMIT + 1))
if __name__ == "__main__":
for caps in ([4, 5], [4, 6], [3, 4], [6, 10, 15]):
print(f"{caps} -> {solve(caps)}")
输出:
[4, 5] -> 6
[4, 6] -> INF
[3, 4] -> 3
[6, 10, 15] -> 15
两版答案一致。简写版把“上界之外全部可达”当作已知结论,既不检查连续窗口,也不在容量变大时调整 LIMIT;一旦离开 的约定,它可能给出偏大的错误计数。主实现用 并显式核对窗口,适用范围更容易说清。
算法执行过程
观察任务
| 阶段 | 观察任务 |
|---|---|
| 计算前 | 先算 ,预测答案是有限整数还是 INF;指出样例里哪个数是 |
| 逐步填表 | 每加入一种容量,写出新变可达的数,特别注意同一容量被用多次的情形 |
| 核对结果 | 确认 [4, 5] 得到 6,并列出这 6 个不可达的数 |
| 上界核对 | 找出最早连续 个可达数,说明其后为何不必再统计 |
主示例:容量 4 和 5 的可达数轴
表中 1 表示可凑出、0 表示凑不出。只用容量 4 时,可达的只有 4 的倍数。
| 阶段 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| 只用容量 4 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 加入容量 5 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
| 阶段 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|
| 只用容量 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 加入容量 5 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
dp[0] = 1 只是“什么都不选”的起点,不参与答案统计。
逐步填表:容量 5 这一轮
进入本轮前,dp 在 0、4、8、12、16 处为 1。按 递增处理 :
| 当前 | 本轮 dp[x - 5] | 更新后 dp[x] | 关键说明 |
|---|---|---|---|
| 5 | dp[0] = 1 | 1 | ,新增一笼 5 |
| 6 | dp[1] = 0 | 0 | 仍凑不出 |
| 7 | dp[2] = 0 | 0 | 仍凑不出 |
| 8 | dp[3] = 0 | 1 | 保持由容量 4 得到的可达性 |
| 9 | dp[4] = 1 | 1 | |
| 10 | dp[5] = 1,本轮刚更新 | 1 | ,同一容量用了两次 |
| 11 | dp[6] = 0 | 0 | 仍凑不出 |
| 12 | dp[7] = 0 | 1 | 保持由容量 4 得到的可达性 |
| 13 | dp[8] = 1 | 1 | |
| 14 | dp[9] = 1,本轮刚更新 | 1 | |
| 15 | dp[10] = 1 | 1 | |
| 16 | dp[11] = 0 | 1 | 保持由容量 4 得到的可达性 |
与 两行是内层递增顺序的直接证据:若是倒序,dp[5]、dp[9] 尚未置真,这两个数会被漏掉。
找到连续窗口并统计
本例 。最早连续 4 个可达数出现在 ,即 ;此后每个整数都可由其中某个数反复加 4 得到,无需再统计。
检查 到 :不可达的是 ,共 6 个,与样例输出一致。注意 11 是这些数中最大的一个,而答案 6 是它们的个数。
gcd 分支对照
| 容量 | 可凑出的形式 | 输出 | |
|---|---|---|---|
[4, 5] | 1 | 12 起所有整数,之前有 6 个缺口 | 6 |
[4, 6] | 2 | 只有偶数 | INF |
[7] | 7 | 只有 7 的倍数 | INF |
[4, 5, 6] | 1 | 8 起所有整数,之前缺口为 1, 2, 3, 7 | 4 |
[6, 10, 15] | 1 | 整体互质,但两两都不互质 | 15 |
边界与反例
| 输入或检查方式 | 正确结果或结论 | 检查重点 |
|---|---|---|
[1] | 0 | 容量含 1,所有正整数都可达 |
[1, 5] | 0 | 窗口从 0 就开始,答案立即为 0 |
[7] | INF | 只有一种容量且大于 1,别误当作“只有 6 个数凑不出” |
[2, 3] | 1 | 只缺 1 |
[3, 4] | 3 | 缺 1, 2, 5 |
[4, 4, 5] | 6 | 重复容量不改变可达集合 |
[2, 3] 倒序内层 | 答案被高估 | 每种容量最多用一次,模型已改变 |
[9999, 10000] | 超出题目约束 | 主实现的 会占用过大内存,见进阶思考 |
与零钱兑换比较:那题的状态是“恰好凑出金额的组合数”,本题是“能否凑出”的布尔值。两段代码都有递增的内层循环,但状态含义不同,不能直接照搬答案。
复杂度分析
设 为去重后的容量种数,,(按题目约束 ,故 )。以布尔数组的一次读写、一次整数比较和一次 gcd 为单位成本。
先看结论
| 实现或任务 | 时间复杂度 | 辅助空间复杂度 |
|---|---|---|
主实现 count_unreachable | ||
| 固定上界简写版 | ||
仅走 INF 分支 |
时间复杂度
求 需要 。填表时每种容量扫描 个位置,每处只做常数次读取与赋值,共 ;随后扫描连续窗口与统计缺口各至多 ,不改变 的量级。
固定上界版把 换成常数 10000,在题目约束下可写作 ;省去窗口扫描并不会改变渐近量级,只是少了一次线性遍历。若 ,两版都在 gcd 之后立即返回,不会进入填表。
辅助空间复杂度
两版都只创建一个长度为 (或 10001)的布尔数组,分别为 与 ;输入列表本身的存储不计入辅助空间。两版都使用循环,没有递归栈。
这里的 依赖 ,不是输入规模 。若放宽到 , 会达到 ,空间与时间都不再可行;此时应按模 建图求每个余数类的最小可达数,把空间压到 ,见进阶思考。
易错点
| 易错点 | 反例或后果 | 正确处理 |
|---|---|---|
| 直接做 DP,不先判断 | [4, 6] 会被数成有限个,而所有奇数都凑不出 | 先算 , 立即返回 INF |
| 把“凑不出的个数”当成“最大凑不出的数” | 样例答案是 6,不是 11 | 统计不可达正整数的数量,11 只是其中最大者 |
| 认为 10000 是题目给出的容量上限 | 会误以为 可以任意大 | 官方约束是 ;10000 是推导出的枚举上界 |
| 内层循环从大到小 | [4, 5] 中 被漏判 | 从小到大遍历,让同轮更新可被后续读到 |
dp[0] 初始化为 False | 任何数都凑不出,答案严重偏大 | dp[0] = True 表示一笼都不选 |
| 统计时把 0 计入 | 答案多 1 | 只统计 |
把样例 2 4 5 读成三种容量 | 得到完全无关的答案 | 第一个数是 ,容量是 4 和 5 |
| 认为 就存在一对互质容量 | [6, 10, 15] 两两不互质,但整体 | 用全体容量的 ,不要只检查数对 |
| 套用两元 Frobenius 公式 | 它只适用于两种互质面额求最大值 | 本题是多容量、且求的是个数,用可达性 DP |
输出 INF 后还继续统计并打印整数 | 与题目输出格式不符 | INF 分支直接返回字符串 |
| 认为去掉连续窗口检查也能保证正确 | 容量超出约束时上界可能不足 | 显式核对连续 个可达数,或说明上界的适用范围 |
| 忽略重复容量或认为必须先排序 | 结果不变但多做无用循环 | 去重不改变可达集合;排序只是便于取 与 |
课堂练习
先独立作答,再逐题展开答案核对。
基础核对
1. 对 [1]、[2, 3]、[3, 4]、[4, 5, 6]、[7],输出分别是什么?[4, 5] 输出的 6 是最大凑不出的数吗?
参考答案
依次为 0、1、3、4、INF。
[4, 5] 中不可达的是 1, 2, 3, 6, 7, 11,答案 6 是个数;其中最大的不可达数是 11。
2. 样例输入 2 4 5 中三个整数各代表什么?为什么统计要从 1 开始,而 dp[0] 仍要设为 True?
参考答案
2 是蒸笼种类数 ,4 和 5 是两种容量。
dp[0] = True 表示“一笼都不选就能凑出 0 个”,它是所有转移的起点;但 0 不是正整数,也不属于题目要统计的“顾客想买的数目”,所以答案只统计 。
过程推演
3. 只用容量 3 和 5,写出 1 到 10 的可达情况,给出答案,并指出最早连续 3 个可达数从哪开始。
参考答案
可达情况:1✗、2✗、3✓、4✗、5✓、6✓、7✗、8✓、9✓、10✓。
,最早连续 3 个可达数是 8, 9, 10,所以只统计 1 到 7,其中不可达的是 1, 2, 4, 7,答案为 4。
4. 若把主实现的内层改成 for x in range(limit, a - 1, -1),[4, 5] 中的 dp[10] 会发生什么?说明原因。
参考答案
dp[10] 会被判为不可达。
倒序遍历时处理 的时刻,dp[5] 还没在本轮更新(它要在 时才被置真,而 尚未轮到),因此读到的仍是 False。这样每种容量最多被用一次,模型退化为 01 背包, 这类组合全部丢失,最终答案会被高估。
进阶思考
5. [6, 10, 15] 的整体 是 1,但任意两种容量都不互质。能否用两元公式 求这道题的答案?程序输出的 15 是数量还是最大值?
参考答案
不能。 只适用于恰好两种互质面额且求“最大凑不出的数”的情形;本题有三种容量,且问的是“凑不出的个数”。
程序输出的 15 是个数。这个例子还说明:不能因为 就断定存在一对互质容量,、、,但三者整体互质,答案仍是有限的 15。
6. 若把容量放宽到 ,为什么 不再可用?怎样改用“连续 个可达数”或模 的最短路,把辅助空间压到 ?
参考答案
会达到 ,布尔数组占用的内存和 的时间都难以承受;这个上界只是 时够用的便利取值,不是通用结论。
更本质的做法是只关心模 的余数:把 个余数看作节点,对每个容量 连边 、权为 ,从余数 0 出发做最短路,得到每个余数类最小可达数 。于是 全部可达,最大不可达数可由 给出,个数也可按余数类直接累加。节点数与边数只与 和 有关,空间为 ,不再随 增长。
继续学习: 阅读完全背包问题比较“能否凑出”与“最多/最少几笼”的状态差异,阅读钱币找零问题与零钱兑换比较计数型状态;数论背景可对照买不到的数字。
