跳至主要內容

买包子

李承昊大约 18 分钟教学文档算法设计与分析动态规划完全背包数论Python

买包子

基础 完全背包 裴蜀定理 Python

蒸笼容量是 4 和 5,为什么凑不出的数目恰好是 6 个;换成 4 和 6,答案却变成 INF?

本节学习目标

  • 会建模: 把“若干笼包子恰好凑成 xx 个”转成完全背包的可达性状态,并先用最大公约数区分有限与无穷两种答案。
  • 会追踪: 按 [4, 5] 逐步填写可达数组,说明内层循环为什么要从小到大,以及从哪一处开始可以停止统计。
  • 会核对: 检查 INF 分支、样例中 NN 与容量的位置、上界 10000 的来源,以及“凑不出的个数”与“最大凑不出的数”的区别。

前置知识:循环与列表、gcd、布尔数组;背包模型可先阅读完全背包问题与动态规划的分类。

题目描述

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 NN 种蒸笼,其中第 ii 种蒸笼恰好能放 AiA_i 个包子。每种蒸笼都有非常多笼,可以认为是无限笼。

每当有顾客想买 xx 个包子,卖包子的大叔就会迅速选出若干笼,使这若干笼中恰好一共有 xx 个包子。比如一共有 3 种蒸笼,分别能放 3、4 和 5 个包子;顾客想买 11 个时,大叔会选 2 笼 3 个的再加 1 笼 5 个的(也可能选 1 笼 3 个的再加 2 笼 4 个的)。

当然有时大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼,分别能放 4、5 和 6 个包子,顾客想买 7 个时就凑不出来。本题要统计:一共有多少种正整数数目是凑不出来的。

参数、结果与输入格式

  • 输入共 N+1N+1 个整数:第一行是蒸笼种类数 NN(1≤N≤1001\le N\le100),随后给出每种容量 AiA_i(1≤Ai≤1001\le A_i\le100)。官方题面把 AiA_i 写成 NN 行,样例常压缩成一行;按空白分隔读取时两种排版等价。
  • 每种蒸笼可以取无限多笼,容量允许重复。题目只要求统计数量,不要求输出选笼方案。
  • 输出一个整数,表示凑不出的正整数个数;若这样的数有无穷多个,输出 INF。
  • 00 个包子视为一笼都不选,一定可凑出,且它不是正整数,不计入答案。
  • 样例中的第一个数是 NN,不是第一种容量。

10000 不是输入上限

题目给出的约束是 Ai≤100A_i\le100。常见的 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 分支。

配套视频解析

题目分析

从枚举组合到完全背包可达性

设第 ii 种蒸笼选了 kik_i 笼,题目就是判断方程

∑i=1NkiAi=x,ki∈N \sum_{i=1}^{N} k_i A_i = x,\qquad k_i\in\mathbb{N}

是否有解,并统计无解的 xx 有多少个。kik_i 没有上限、每种容量可重复使用,这是完全背包;与01背包问题里每种物品最多取一次不同。

本题求的是“能否凑出”,不是“有多少种凑法”,所以状态取布尔值就够了。也不要把它和买不到的数字混为一谈:那题求最大的凑不出的数,本题求凑不出的数的个数。

先分情况:什么时候会有无穷多个

核心结论

记 g=gcd⁡(A1,…,AN)g=\gcd(A_1,\dots,A_N)。若 g>1g>1,任何组合都是 gg 的倍数,所有非 gg 倍数的正整数都凑不出,答案直接是 INF;只有 g=1g=1 时才需要用动态规划数出那有限多个凑不出的数。

由裴蜀定理,g=1g=1 时存在整数组合得到 1;在 Ai≤100A_i\le100 的前提下,所有足够大的正整数都能用非负系数凑出,因此不可凑出的只有有限个。

这一步必须放在动态规划之前。对 g>1g>1 的用例,无论把数组开多大,数出来的都只是“上界以内”的假答案。例如 [4, 6] 的 g=2g=2,可凑出的全是偶数;[7] 的 g=7g=7,可凑出的全是 7 的倍数,二者都输出 INF。

定义状态与转移

定义布尔状态 dp[x]:只用已经处理过的蒸笼容量,能否恰好凑出 xx 个包子。

dp[0]=True,dp[x]=False(x≥1,初始) dp[0]=\text{True},\qquad dp[x]=\text{False}\quad(x\ge1\text{,初始})

依次把每种容量 aa 加入可选集合。对每个 x≥ax\ge a,若加入前 dp[x - a] 已为真,再取一笼 aa 就能凑出 xx:

dp[x]←dp[x] or dp[x−a],a≤x≤L. dp[x]\leftarrow dp[x]\ \text{or}\ dp[x-a],\qquad a\le x\le L.

其中 LL 是枚举上界。xx 从小到大遍历时,dp[x - a] 在本轮可能刚被更新,正好表示同一容量被取用多次。

为什么内层必须从小到大

若内层改成从大到小,dp[x - a] 在本轮还未更新,每种容量最多只能用一次,模型退化成 01 背包。

以 [4, 5] 的 x=10x=10 为例:10=5+510=5+5 需要同一轮两次使用容量 5。从大到小时处理 x=10x=10,dp[5] 仍为假,10 会被误判为凑不出;从小到大时,x=5x=5 已把 dp[5] 置真,随后 x=10x=10 才能读到它。

统计到哪里为止

只把数组开到某个上界还不够,必须说明上界之外的整数都可达。

停止条件

设 m=min⁡(Ai)m=\min(A_i)。若从 tt 开始出现连续 mm 个可达整数 t,t+1,…,t+m−1t,t+1,\dots,t+m-1,则任意 x≥tx\ge t 都可写成其中某一个再加上若干个 mm,因而全部可达。

主实现据此在填表后扫描最早出现的连续 mm 个可达数,只统计它之前的不可达正整数。

上界取 L=max⁡(Ai)2L=\max(A_i)^2:在模 mm 的每个余数类里,最小可达数可看作 mm 个余数节点上的最短路,最多经过 m−1m-1 条边、每边权不超过 max⁡(Ai)\max(A_i),故小于 m⋅max⁡(Ai)≤Lm\cdot\max(A_i)\le L;再由停止条件,LL 之后的整数全部可达。当 Ai≤100A_i\le100 时 L≤10000L\le10000,这正是竞赛代码里直接写 10000 的来历——它是范围保证下的经验上界,不是题目的输入约束。

为什么结果正确

  • gcd 分支:g>1g>1 时所有组合都是 gg 的倍数,非倍数有无穷多个,返回 INF 与题意一致。
  • 可达性等价:dp[x] 为真当且仅当存在非负整数 kik_i 使 ∑kiAi=x\sum k_i A_i=x。按容量依次加入、内层递增遍历,恰好覆盖了“最后一次取的是当前容量”的所有组合,不重不漏;重复容量去重后也不改变可达集合。
  • 统计范围:连续 mm 个可达数之后全部可达,窗口之前逐个检查,既不会漏掉小的不可达数,也不会把上界之外无限延伸的情况误算进来。

实现代码

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 记录当前连续可达的长度,第一次达到 mm 时即可返回,不必枚举到 limit 末尾;若始终达不到,说明上界不足,应报错而不是悄悄返回一个偏小的答案。

读取题目输入

把主实现保存成文件后,将示例用的 if __name__ == "__main__": 代码块替换为下面 4 行,就是可直接提交的入口。split() 不区分空格与换行,因此官方的 NN 行排版与样例的一行排版都能读取。

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
print(count_unreachable(data[1:1 + n]))

这一段依赖同一文件中已定义的 count_unreachable,不是独立程序;直接运行它没有标准输入会读到空列表。

竞赛简写版(固定上界)

如果确信 Ai≤100A_i\le100,可以把上界固定为 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;一旦离开 Ai≤100A_i\le100 的约定,它可能给出偏大的错误计数。主实现用 L=max⁡(Ai)2L=\max(A_i)^2 并显式核对窗口,适用范围更容易说清。

算法执行过程

观察任务

阶段观察任务
计算前先算 gcd⁡\gcd,预测答案是有限整数还是 INF;指出样例里哪个数是 NN
逐步填表每加入一种容量,写出新变可达的数,特别注意同一容量被用多次的情形
核对结果确认 [4, 5] 得到 6,并列出这 6 个不可达的数
上界核对找出最早连续 min⁡(Ai)\min(A_i) 个可达数,说明其后为何不必再统计

主示例:容量 4 和 5 的可达数轴

表中 1 表示可凑出、0 表示凑不出。只用容量 4 时,可达的只有 4 的倍数。

阶段012345678
只用容量 4100010001
加入容量 5100011001
阶段910111213141516
只用容量 400010001
加入容量 511011111

dp[0] = 1 只是“什么都不选”的起点,不参与答案统计。

逐步填表:容量 5 这一轮

进入本轮前,dp 在 0、4、8、12、16 处为 1。按 xx 递增处理 x≥5x\ge5:

当前 xx本轮 dp[x - 5]更新后 dp[x]关键说明
5dp[0] = 110+50+5,新增一笼 5
6dp[1] = 00仍凑不出
7dp[2] = 00仍凑不出
8dp[3] = 01保持由容量 4 得到的可达性
9dp[4] = 114+54+5
10dp[5] = 1,本轮刚更新15+55+5,同一容量用了两次
11dp[6] = 00仍凑不出
12dp[7] = 01保持由容量 4 得到的可达性
13dp[8] = 118+58+5
14dp[9] = 1,本轮刚更新19+59+5
15dp[10] = 1110+510+5
16dp[11] = 01保持由容量 4 得到的可达性

x=10x=10 与 x=14x=14 两行是内层递增顺序的直接证据:若是倒序,dp[5]、dp[9] 尚未置真,这两个数会被漏掉。

找到连续窗口并统计

本例 m=min⁡(4,5)=4m=\min(4,5)=4。最早连续 4 个可达数出现在 12,13,14,1512,13,14,15,即 t=12t=12;此后每个整数都可由其中某个数反复加 4 得到,无需再统计。

检查 11 到 1111:不可达的是 1,2,3,6,7,111,2,3,6,7,11,共 6 个,与样例输出一致。注意 11 是这些数中最大的一个,而答案 6 是它们的个数。

gcd 分支对照

容量gcd⁡\gcd可凑出的形式输出
[4, 5]112 起所有整数,之前有 6 个缺口6
[4, 6]2只有偶数INF
[7]7只有 7 的倍数INF
[4, 5, 6]18 起所有整数,之前缺口为 1, 2, 3, 74
[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]超出题目约束主实现的 L=max⁡(Ai)2L=\max(A_i)^2 会占用过大内存,见进阶思考

与零钱兑换比较:那题的状态是“恰好凑出金额的组合数”,本题是“能否凑出”的布尔值。两段代码都有递增的内层循环,但状态含义不同,不能直接照搬答案。

复杂度分析

设 NN 为去重后的容量种数,M=max⁡(Ai)M=\max(A_i),L=M2L=M^2(按题目约束 M≤100M\le100,故 L≤10000L\le10000)。以布尔数组的一次读写、一次整数比较和一次 gcd 为单位成本。

先看结论

实现或任务时间复杂度辅助空间复杂度
主实现 count_unreachableO(NL)O(NL)O(L)O(L)
固定上界简写版O(N⋅10000)O(N\cdot10000)O(10000)O(10000)
仅走 INF 分支O(Nlog⁡M)O(N\log M)O(1)O(1)

时间复杂度

求 gcd⁡\gcd 需要 O(Nlog⁡M)O(N\log M)。填表时每种容量扫描 LL 个位置,每处只做常数次读取与赋值,共 O(NL)O(NL);随后扫描连续窗口与统计缺口各至多 O(L)O(L),不改变 O(NL)O(NL) 的量级。

固定上界版把 LL 换成常数 10000,在题目约束下可写作 O(N⋅10000)O(N\cdot10000);省去窗口扫描并不会改变渐近量级,只是少了一次线性遍历。若 g>1g>1,两版都在 gcd 之后立即返回,不会进入填表。

辅助空间复杂度

两版都只创建一个长度为 L+1L+1(或 10001)的布尔数组,分别为 O(L)O(L) 与 O(10000)O(10000);输入列表本身的存储不计入辅助空间。两版都使用循环,没有递归栈。

这里的 LL 依赖 MM,不是输入规模 NN。若放宽到 Ai≤104A_i\le10^4,L=M2L=M^2 会达到 10810^8,空间与时间都不再可行;此时应按模 mm 建图求每个余数类的最小可达数,把空间压到 O(m)O(m),见进阶思考。

易错点

易错点反例或后果正确处理
直接做 DP,不先判断 gcd⁡\gcd[4, 6] 会被数成有限个,而所有奇数都凑不出先算 g=gcd⁡(Ai)g=\gcd(A_i),g>1g>1 立即返回 INF
把“凑不出的个数”当成“最大凑不出的数”样例答案是 6,不是 11统计不可达正整数的数量,11 只是其中最大者
认为 10000 是题目给出的容量上限会误以为 AiA_i 可以任意大官方约束是 Ai≤100A_i\le100;10000 是推导出的枚举上界
内层循环从大到小[4, 5] 中 10=5+510=5+5 被漏判从小到大遍历,让同轮更新可被后续读到
dp[0] 初始化为 False任何数都凑不出,答案严重偏大dp[0] = True 表示一笼都不选
统计时把 0 计入答案多 1只统计 x≥1x\ge1
把样例 2 4 5 读成三种容量得到完全无关的答案第一个数是 N=2N=2,容量是 4 和 5
认为 gcd⁡=1\gcd=1 就存在一对互质容量[6, 10, 15] 两两不互质,但整体 gcd⁡=1\gcd=1用全体容量的 gcd⁡\gcd,不要只检查数对
套用两元 Frobenius 公式 ab−a−bab-a-b它只适用于两种互质面额求最大值本题是多容量、且求的是个数,用可达性 DP
输出 INF 后还继续统计并打印整数与题目输出格式不符INF 分支直接返回字符串
认为去掉连续窗口检查也能保证正确容量超出约束时上界可能不足显式核对连续 mm 个可达数,或说明上界的适用范围
忽略重复容量或认为必须先排序结果不变但多做无用循环去重不改变可达集合;排序只是便于取 min⁡\min 与 max⁡\max

课堂练习

先独立作答,再逐题展开答案核对。

基础核对

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 是蒸笼种类数 NN,4 和 5 是两种容量。

dp[0] = True 表示“一笼都不选就能凑出 0 个”,它是所有转移的起点;但 0 不是正整数,也不属于题目要统计的“顾客想买的数目”,所以答案只统计 x≥1x\ge1。

过程推演

3. 只用容量 3 和 5,写出 1 到 10 的可达情况,给出答案,并指出最早连续 3 个可达数从哪开始。

参考答案

可达情况:1✗、2✗、3✓、4✗、5✓、6✓、7✗、8✓、9✓、10✓。

m=min⁡(3,5)=3m=\min(3,5)=3,最早连续 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] 会被判为不可达。

倒序遍历时处理 x=10x=10 的时刻,dp[5] 还没在本轮更新(它要在 x=5x=5 时才被置真,而 5<105<10 尚未轮到),因此读到的仍是 False。这样每种容量最多被用一次,模型退化为 01 背包,10=5+510=5+5 这类组合全部丢失,最终答案会被高估。

进阶思考

5. [6, 10, 15] 的整体 gcd⁡\gcd 是 1,但任意两种容量都不互质。能否用两元公式 ab−a−bab-a-b 求这道题的答案?程序输出的 15 是数量还是最大值?

参考答案

不能。ab−a−bab-a-b 只适用于恰好两种互质面额且求“最大凑不出的数”的情形;本题有三种容量,且问的是“凑不出的个数”。

程序输出的 15 是个数。这个例子还说明:不能因为 gcd⁡=1\gcd=1 就断定存在一对互质容量,gcd⁡(6,10)=2\gcd(6,10)=2、gcd⁡(6,15)=3\gcd(6,15)=3、gcd⁡(10,15)=5\gcd(10,15)=5,但三者整体互质,答案仍是有限的 15。

6. 若把容量放宽到 Ai≤104A_i\le10^4,为什么 L=M2L=M^2 不再可用?怎样改用“连续 mm 个可达数”或模 mm 的最短路,把辅助空间压到 O(m)O(m)?

参考答案

L=M2L=M^2 会达到 10810^8,布尔数组占用的内存和 O(NL)O(NL) 的时间都难以承受;这个上界只是 Ai≤100A_i\le100 时够用的便利取值,不是通用结论。

更本质的做法是只关心模 m=min⁡(Ai)m=\min(A_i) 的余数:把 mm 个余数看作节点,对每个容量 aa 连边 r→(r+a) mod mr\to(r+a)\bmod m、权为 aa,从余数 0 出发做最短路,得到每个余数类最小可达数 d[r]d[r]。于是 d[r]+kmd[r]+k m 全部可达,最大不可达数可由 max⁡rd[r]−m\max_r d[r]-m 给出,个数也可按余数类直接累加。节点数与边数只与 mm 和 NN 有关,空间为 O(m)O(m),不再随 M2M^2 增长。

继续学习: 阅读完全背包问题比较“能否凑出”与“最多/最少几笼”的状态差异,阅读钱币找零问题与零钱兑换比较计数型状态;数论背景可对照买不到的数字。

上次编辑于:
贡献者: zilizhou,molittle