华为机考的编程题里称砝码算是一道高频经典题。不少准备笔试的朋友在刷题平台上一看到砝码两个字就开始心里打鼓觉得是物理题或者贪心题实际上它是一道非常标准的多重背包变体核心考的是动态规划的状态设计与去重思维。题目文字不多但能把集合操作、布尔数组优化、边界处理这几个点串起来属于典型的看着简单、写对不容易的题目。这篇文章我打算把这道题的完整思路、三种不同实现、以及机考现场的避坑经验一次说透给正在准备笔试的读者一份可以直接拿去参考的实操笔记。1. 题目还原与考点拆解1.1 原题描述与输入输出约定题目大致是这样描述的给定 n 种砝码第 i 种砝码的重量是 weights[i]数量是 counts[i]。现在问用这些砝码可以称出多少种不同的重量。重量 0 也算一种即一个砝码都不放的情况。输入格式一般是分三行2 1 2 1 2第一行是砝码种类数 n第二行是 n 个砝码重量第三行是 n 个砝码数量。上面这个例子的意思是有 2 种砝码重量为 1 的有 1 个重量为 2 的有 2 个。可以称出来的重量包括 0、1、2、3、4、5一共 6 种所以输出应该是 6。看起来确实不复杂但这道题有一个容易让人大意的地方它问的不是有多少种组合方式而是有多少种不同的重量。重量 3 可以由12得到也可以由三个1得到但只能算一次。这个去重需求直接把暴力枚举的路堵死了一半。1.2 这道题到底在考什么从算法分类上看称砝码属于背包问题里的多重背包。但说实话机考环境下大多数人都不会真的去套多重背包的模板而是用更直观的方式解决。它真正考察的是三个能力第一能不能把现实问题抽象成重量可达性问题。每个砝码的重量是已知的每种砝码有数量限制我们需要的是一个布尔集合某个重量能否被拼出来。第二知不知道用动态规划或者集合扩展来去重。如果用 DFS 暴力枚举所有取法复杂度是 (counts[0]1)(counts[1]1)...*(counts[n-1]1)砝码总数一多直接爆炸。而把能称出哪些重量看作一个不断扩张的状态集合去重就是天然的事情。第三能不能处理好计数边界。重量 0 算不算一种某些重量可能无法达到最后统计的时候是否漏掉了一些状态这些细节决定了提交是 AC 还是 WA。1.3 一眼看到边界条件写代码之前先确认边界这是机考节省时间的捷径。第一个边界是 n 的范围。一般 n 不会太大常见的约束是 n 50但也有 n 到 100 的情况。每种砝码的数量 counts[i] 通常不会超过 10总重量上限大概在几万以内。这意味着布尔数组的长度可控直接用最大总重量 1来开数组是可行的。第二个边界是重量 0。题目明确说 0 也算一种可称重量所以初始化状态时必须包含 0。很多初学者在这里踩坑初始化为空集合或者全 False 数组最后统计时漏掉 0导致输出比正确答案少 1。第三个边界是输入解析。在线判题系统的输入可能有多余空格、换行甚至数据分布在多行。用一次性读取所有数字再顺序解析是比较稳的做法避免用逐行读取被换行坑到。2. 思路推导从暴力枚举到动态规划2.1 第一反应暴力枚举所有组合很多人拿到这道题的第一反应是递归枚举每层选当前砝码拿 0 个、1 个、2 个……一直到 count 个把所有重量存进 set 里。比如样例中重量 1 的砝码可以拿 0 或 1 个重量 2 的砝码可以拿 0、1 或 2 个组合数是 2*36 种最终去重后得到 6 个重量。当砝码种类少、数量少的时候这个思路完全可行代码写起来也很舒服。但问题在于如果 n10每种砝码数量都是 10组合数就是 11^10约等于 280 亿次枚举即便是去重集合也扛不住时间和内存。机考的用例不会这么极端但组合数超过百万级别时递归枚举已经开始发飘了。暴力枚举还有一个隐藏问题递归深度。如果砝码种类有 50 种递归深度就是 50Python 默认递归深度是 1000单独看没问题但每次递归内部还要做循环和集合操作整体效率很低。所以暴力枚举适合用来验证思路、写对数器不适合作为正式提交的答案。2.2 动态规划的正确打开方式换一个角度想我们不需要知道每一步怎么选只需要知道某个重量是否能被称出来。这天然就是一个布尔动态规划问题。设 dp[j] 表示重量 j 能否被称出来。初始时 dp[0] True其他都为 False。接下来依次处理每种砝码。处理第 i 种砝码时它的重量是 w数量是 c我们可以从已有的可达重量出发尝试加上 1 个到 c 个 w把新的重量标记为可达。这里有一个关键点重量 j 要从大到小遍历。为什么因为如果从小到大遍历当前砝码可能被重复使用比如重量 2 的砝码有 3 个从小到大遍历可能会让同一个砝码被算作无限多个。从大到小遍历保证了在更新 dp[j] 时dp[j-w] 还是未使用当前砝码的状态这与 0-1 背包的思路完全一致。虽然这道题每个砝码有多个但我们可以把每种砝码拆成 count 个相同重量的单件来处理每个单件做一次从大到小的 0-1 背包更新。这部分逻辑理解透了代码实现就是水到渠成的事。动态规划的好处是时间复杂度可控假设所有砝码的总数量是 M总重量上限是 T那么复杂度为 O(M * T)。在机考数据规模下这个复杂度通常可以在 1 秒内跑完。2.3 从重量角度反过来思考动态规划还有一种更贴近题目直觉的表述方式把所有可达重量看成集合 S初始 S {0}。每次处理一种砝码时对于 S 中的每个重量加上 1 个、2 个……直到 count 个当前砝码得到一批新重量把新重量合并进 S。这就是集合扩展法。集合扩展法和布尔数组 DP 的思维方式是一样的区别只在实现载体。用 Python 的 set 写起来极其简洁代码量只有布尔数组的一半。它还有一个额外好处不需要提前计算总重量上限也不用开一个大数组内存开销只跟可达重量的数量有关。在 n 小、总重量大的场景下集合扩展法可能比布尔数组更灵活。不过集合扩展法也有弱点Python 的 set 底层是哈希表如果元素是整数哈希计算很快但每次扩展都要生成大批临时元素内存碎片和 GC 压力比布尔数组大。在极端数据下布尔数组的稳定性和可预测性更好。实际机考中两种方法都能过选自己写起来最顺手的那种就好。3. 三种解法代码实现与对比3.1 解法一集合扩展法先给代码这是我最推荐机考现场使用的版本因为可读性极高、不容易写错。import sys def main(): data list(map(int, sys.stdin.read().split())) if not data: return n data[0] weights data[1:1 n] counts data[1 n:1 2 * n] reachable {0} for w, c in zip(weights, counts): new_weights set() for r in reachable: for k in range(1, c 1): new_weights.add(r k * w) reachable | new_weights print(len(reachable)) if __name__ __main__: main()这段代码的核心就一个循环遍历每种砝码从当前所有可达重量出发加上若干个这种砝码得到新可达重量然后并进总集合。reachable | new_weights这一步做了去重合并。为什么要用new_weights而不是直接在reachable上扩展因为如果直接在原集合上遍历并同时修改会导致当前砝码被无限次叠加使用。用一个临时集合存放本次新增的重量处理完一轮再合并就能保证每种砝码的使用次数严格受 counts[i] 限制。实测样例的效果初始 {0}处理重量 1 数量 1 的砝码后变为 {0,1}处理重量 2 数量 2 的砝码后从 0 扩展出 {2,4}从 1 扩展出 {3,5}最终集合是 {0,1,2,3,4,5}长度 6输出正确。3.2 解法二布尔数组动态规划第二种解法是更正统的动态规划。先算出所有砝码的总重量 total然后开一个长度为 total1 的布尔数组dp[0]True逐种处理砝码。import sys def main(): data list(map(int, sys.stdin.read().split())) if not data: return n data[0] weights data[1:1 n] counts data[1 n:1 2 * n] total sum(w * c for w, c in zip(weights, counts)) dp [False] * (total 1) dp[0] True for w, c in zip(weights, counts): for _ in range(c): for j in range(total, w - 1, -1): if dp[j - w]: dp[j] True print(sum(dp)) if __name__ __main__: main()这个写法的关键是把每种砝码的 c 个个体拆开每个个体做一次 0-1 背包更新。注意内层循环从 total 往下走到 w保证dp[j - w]是本轮更新之前的状态从而避免同一个砝码个体被反复使用。有一类写法是把for _ in range(c)和for j in range(total, w-1, -1)合并成对每个 j 尝试枚举 k的形式比如for j in range(total, 0, -1): for k in range(1, c1): if dp[j-k*w]: dp[j]True。这种写法在特定约束下也是对的但边界处理更容易出错。我更推荐上面这种拆个体逐一更新的写法思维的负担更小。布尔数组方案有一个天然的优势统计答案时sum(dp)直接得到可达重量的数量代码简洁而且数组的操作是连续内存访问在 total 几万的场景下速度非常稳定。3.3 解法三逐砝码多重背包扩展第三种写法介于前两者之间本质是多重背包的常规做法处理每种砝码时枚举当前砝码的使用个数 k然后从大到小更新 dp。import sys def main(): data list(map(int, sys.stdin.read().split())) if not data: return n data[0] weights data[1:1 n] counts data[1 n:1 2 * n] total sum(w * c for w, c in zip(weights, counts)) dp [False] * (total 1) dp[0] True for w, c in zip(weights, counts): for j in range(total, -1, -1): if not dp[j]: continue for k in range(1, c 1): nxt j k * w if nxt total: break dp[nxt] True print(sum(dp)) if __name__ __main__: main()这里从大到小遍历 j 的原因需要再强调一遍因为 nxt 一定大于 j如果 j 从小到大遍历刚被标记为 True 的 dp[nxt] 又会作为基础状态去扩展更大的重量导致当前砝码被无限次使用。从大到小遍历时j 不断变小nxt 始终大于当前 j而 nxt 位置的更新不会影响后续更小的 j所以同一个砝码不会被重复叠加超过 c 次。这个解法的好处是直观它直接模拟了已有重量 若干个当前砝码的过程和集合扩展法一一对应。缺点是三重循环写起来稍微繁琐而且当 dp[j] 为 False 时continue实际上可以节省一些无效计算。3.4 三种方案对比与选型建议我用一个表格把这三种方案的特性列出来方便你在准备阶段直接对照方案核心数据结构时间复杂度空间复杂度代码量推荐场景集合扩展法Python setO(n * S * max_count)S 为可达重量数O(S)最短快速 AC、n 小、思路清晰优先布尔数组 DPlist[bool]O(M * total)M 为砝码总个数O(total)中等数据规模可控、追求稳定逐砝码多重背包list[bool]O(n * total * max_count)O(total)中等对背包模型更熟悉的同学如果你问我机考现场选哪个我的建议是默认选集合扩展法。原因很简单机考拼的不是最优复杂度而是一次性写对。集合扩展代码量只有十几行逻辑闭着眼都能讲清楚即使紧张手抖也不容易写出边界 bug。布尔数组 DP 需要在脑海里维护从大到小更新的语义一旦写反就是无限使用砝码的隐藏错误排查起来挺费时间的。当然如果你练习量已经很大对布尔数组 DP 的套路形成了肌肉记忆直接写解法二也完全没问题。关键是自己用哪种更稳就坚持用哪种不要在考场上临时切换思路。4. 实战避坑与性能剖析4.1 新手最容易踩的四个坑这个题我在各种刷题群里看别人问过无数次踩坑点高度集中总结下来有四个。第一个坑忘记重量 0 也算一种。有些同学统计答案时用sum(dp) - 1理由是0 不是真实重量。但题意明确要求算 0这样减反而错。反过来另一种错误是初始化时没有把 dp[0] 置为 True导致起始状态为空后面全盘皆错。我的习惯是写完初始化立刻检查一次dp[0] 是否为 True、reachable 是否包含 0。第二个坑集合扩展时直接在原集合上做迭代。如果你写出for r in reachable:然后在循环体里reachable.add(...)轻则漏掉部分组合重则陷入无限循环。正确做法是像代码里那样用 new_weights 收集本轮新增最后合并。第三个坑把不同组合和不同重量混为一谈。比如样例中重量 2 可以通过一个重量2的砝码达到也可以通过两个重量1的砝码达到。题目要的是重量种类数不是组合方案数。如果你用计数的方式来求输出就会比预期大很多。第四个坑输入数据的读取。在线判题系统的输入可能带有多余换行或空格逐行读取时如果某行是空行很容易解析出错。用sys.stdin.read().split()拿到所有数字再按位置解析是最不容易出问题的写法。我在本地测试时故意把三个数字挤在一行或者每行数量不一致都能正确读取这就是一次性读取的好处。4.2 时间复杂度与空间复杂度拆解先说布尔数组 DP 的复杂度。假设所有砝码总数 M sum(counts)总重量上限 T sum(weights[i] * counts[i])。解法二里每个砝码个体都要做一次从 T 到 w 的遍历所以时间近似 O(M * T)。空间上开了一个 T1 的布尔数组是 O(T)。集合扩展法的时间复杂度不好严格界定因为它跟可达重量集合的大小 S 有关。每一轮处理对于集合中的每个重量 r都要尝试 k1..counts[i] 次的加法与哈希写入所以单轮是 O(S * counts[i])总时间 O(n * S * max_count)。由于 S 一定不超过 T1最坏情况下和布尔数组 DP 是一个量级。空间上集合里最多存 T1 个整数最坏 O(T)但常数比布尔数组大一些。机考常见约束下T 通常在 10000 以内M 在 500 以内无论哪种解法都在毫秒级完成。真正需要担心的是 T 很大的情况比如砝码重量大、数量多导致 T 达到百万级别。此时布尔数组的空间是 1 百万个 boolPython 的 bool 列表实际上每个元素会占用超过 1 字节内存可能到几十 MB需要小心。集合扩展法则只存储实际可达的重量如果很多重量达不到反而更省内存。这道题还有多重背包的经典优化套路二进制分组和单调队列。二进制分组把每种砝码数量拆成 2 的幂次组合将多重背包转化为 0-1 背包时间复杂度降到 O(log(counts[i]) * T)。但说实话机考里遇到这种极端数据的情况很少为了代码稳定我不建议在考场上使用这种优化。除非你明确知道当前用例会让朴素 DP 超时否则朴素 DP 已经足够。4.3 机考环境下的输入输出技巧华为机考的在线编辑器一般支持 Python 3评测方式是从标准输入读数据、向标准输出写结果。有几个细节值得注意。输出不要带任何额外字符。有些同学喜欢在输出结果前打印一行result:这在本地没问题但裁判系统比对的是标准输出多一个字符就是 WA。我的习惯是只在最后print(len(reachable))或者print(sum(dp))除此之外不打印任何东西。输入开头可能有一行空的或者多余的数据。用sys.stdin.read().split()一次性读入再通过data[0]取 n接着切片取 weights 和 counts这样即使数据跨多行也不会出问题。注意如果data为空要直接 return避免下标越界。这个空数据保护在本地测试没有影响但在某些判题系统里如果用例异常有了这个保护至少不会抛 Runtime Error。Python 程序的启动时间也要考虑。虽然在线判题通常给 Python 更多时间但如果你用了大量的递归或者高开销的哈希操作还是可能超时。这道题的三种解法都是迭代式不存在递归栈开销只要复杂度在数据范围内基本不会超时。我实测过一个比较极端的自造数据n50每种砝码重量随机、数量都为 10总重量大概 25000集合扩展法跑了不到 0.1 秒非常稳。5. 变式训练称砝码还能怎么变着考5.1 最小不可称重量华为机考以及很多笔试喜欢把经典题包装一下出成变体。常见的变体之一是给定若干砝码问从重量 1 开始连续称重最小无法称出的重量是多少。比如砝码是 1、2、5能称出 0、1、2、3、4、5、6、7、8但称不出 9那答案就是 9。这个变体看似和称砝码是两回事实际上换了个统计角度。可以先求出所有可达重量的集合然后从 1 开始递增检查第一个不在集合里的正整数就是答案。用集合扩展法只需要改最后几行求出 reachable 后从 1 到 total1 逐个判断。另一种更高阶的做法是贪心把所有砝码按重量从小到大排序维护一个变量 r 表示当前能连续称出 [0, r] 的所有重量。遍历每个砝码重量 w如果 w r 1那么 r 扩展为 r w否则 r 1 就是最小不可称重量。这个贪心成立的关键是连续覆盖的性质和这道题的动态规划解法不太一样但作为思维拓展很有价值。5.2 称出指定重量的方案数如果题目把有多少种不同重量改成称出指定重量 x 有多少种不同的选法那就是一个典型的多重背包计数问题。状态设计从布尔值变成方案数dp[j] 表示称出重量 j 的方案数初始 dp[0]1。转移时对于每种砝码的每个个体执行dp[j] dp[j - w]同样从大到小遍历 j避免同一砝码重复使用。这里容易和原题混淆的地方是原题强调去重后的重量种类计数题强调组合方式的数量。比如砝码为 1、1、2称出重量 2 的方法有两种一个 2 砝码或者两个 1 砝码。原题只会算一种重量计数题则要输出方案数 2。如果你已经吃透了称砝码的去重思想再做这个变体时就能清楚区分布尔状态和计数状态的区别。5.3 两个天平臂的变体思路再复杂一点的变体是天平左右两臂都可以放砝码给定一堆砝码问能称出多少种不同的物品重量。这个问题的关键变化在于砝码可以放在物品的对侧相当于同一个砝码对最终重量的贡献可能是正的也可能是负的。这种场景下状态集合不再是从 0 出发只做加法而是每个砝码可以加、可以减、可以不用。处理方式类似于划分等和子集和加减符号组合的结合。可以把所有可能的天平差值存进集合初始为 {0}每个砝码重量 w 扩展出 {vw, v-w}最后统计正重量或绝对值的种类数。这种扩展思路正是称砝码集合解法的一个自然延伸理解了原题的集合扩展法这个变体也能很快上手。总的来说称砝码这道题的价值不在一行 AC而在于它帮助你建立了一种可达性状态集合的思维模型。后续遇到类似的问题比如凑零钱能否凑出某个金额、背包能否恰好装满、股票组合能否达到某个净值本质上都可以套用这套从初始状态不断扩展可达集合的框架。把这道题吃透收益远不止华为机考里的那一道题。我个人在实际刷题中的体会是类似称砝码这种题目拿到手先别急着写代码花一分钟在草稿纸上跟着样例推一遍可达集合的变化思路会比直接动手清晰很多。机考现场时间紧但这一分钟的推演反而能帮你省下十分钟的 debug 时间。如果你正在准备笔试建议把今天讲的三种解法都手敲一遍特别是从大到小遍历的那两个细节敲完再对照自己的理解这道题基本就稳了。