动态规划解砝码称重：从可达性到重量差，掌握背包问题变体

1. 从一道经典算法题说起砝码称重的本质最近在整理蓝桥杯的备赛笔记翻到了“砝码称重”这道题。它几乎是算法竞赛入门动态规划DP的必刷题也是很多同学在理解“状态表示”和“状态转移”时遇到的第一个坎。题目本身不复杂给定几个砝码的重量问用这些砝码能称出多少种不同的重量。听起来是不是有点像小时候玩的“用几个砝码在天平上能称出多少种东西”的游戏但把它抽象成算法问题尤其是用动态规划去解里面的门道就多了。这道题的核心远不止是算出几个数字。它背后考察的是你如何将一个看似是“组合”的问题转化成一个“可达性”问题并用一个布尔数组来高效地记录所有可能的状态。很多初学者会卡在“砝码可以放天平两边”这个条件上觉得情况变复杂了。其实这正是题目的精妙之处它迫使你不能用简单的加法思维而必须引入“负重量”或者“差值”的概念来建模。今天我就结合ALGO-936这道具体的题目把砝码称重的几种经典解法掰开揉碎了讲一遍。我们会从最直观的暴力搜索DFS开始看看它的局限在哪里然后重点深入两种主流的动态规划思路——一种是基于“重量和”的背包思想另一种是基于“重量差”的更优解法。最后我们还会聊聊如何优化空间以及一些在竞赛中容易忽略的边界条件和调试技巧。无论你是正在备赛蓝桥杯还是单纯想巩固一下动态规划基础相信这篇都能给你带来一些新的启发。2. 问题定义与暴力搜索的困境我们先来明确一下ALGO-936 “砝码称重” 的具体问题描述。通常这类题目的输入格式是第一行给出砝码的种类数 N第二行给出 N 个正整数分别代表每种砝码的重量。同时每种砝码通常有无限个完全背包或者有限个多重背包。对于经典的蓝桥杯真题及ALGO-936我们一般按“每种砝码只有一个”来处理即 01背包的变体。但最关键的条件是砝码可以放在天平的左右两盘中。这意味着什么假设天平左盘放要称的物体重量为X右盘放砝码。那么如果砝码和物体放在同一边比如都放在左盘实际作用是“抵消”物体的一部分重量相当于物体的重量被减轻了。从砝码的贡献来看它提供了“负”的重量。如果砝码放在对面右盘那么它提供的是“正”的重量。当然砝码也可以不使用。因此对于每一个砝码weight[i]它有三种状态不加这个砝码贡献0。把这个砝码加到“正”的一边贡献weight[i]。把这个砝码加到“负”的一边贡献-weight[i]。我们的目标是找出所有由这些砝码通过上述三种选择组合起来所能达到的最终重量可以是正数、负数或零。注意我们关心的是能称出的不同重量的数量。由于天平称重时物体放在左边右边放砝码组合所以能称出的物体重量X实际上等于右边砝码组合的总重量如果砝码在右边提供正贡献或者等于左边砝码组合的总重量提供负贡献即抵消。更直接的理解是所有砝码通过加、减或不选能构成多少个不同的非负整数和因为物体重量通常为正且对称性使得正负重量是对称的绝对值相同的正负值代表能称出同一个物体重量。最直观的解法是深度优先搜索DFS。我们可以递归地枚举每个砝码的三种选择计算最终的和并用一个集合如Python的set来记录所有出现过的和的绝对值因为重量取绝对值。def dfs_bruteforce(weights): unique_weights set() n len(weights) def backtrack(index, current_sum): if index n: if current_sum 0: # 通常只记录正重量0重量不算能称出的物体 unique_weights.add(current_sum) return # 三种选择不选、加、减 backtrack(index 1, current_sum) # 不选 backtrack(index 1, current_sum weights[index]) # 加 backtrack(index 1, current_sum - weights[index]) # 减 backtrack(0, 0) return len(unique_weights)这种解法思路简单但复杂度是 O(3^N)。当 N 稍微大一点比如超过20计算量就会爆炸完全无法用于竞赛。它最大的问题是存在大量重复计算比如不同的砝码选择顺序可能得到相同的和。因此我们必须寻找更高效的算法而动态规划正是用来解决这种“重叠子问题”和“最优子结构”的利器。注意在竞赛中除非N非常小10否则绝对不要使用纯DFS解法。它主要帮助我们理解问题的搜索空间。3. 动态规划解法一转化为“可达和”问题第一种DP思路是抛开天平的左右概念直接思考给定一系列有正负贡献的砝码我们能得到哪些“和”。这本质上是一个“可达性”问题。我们设dp[i][j]为一个布尔值表示用前i个砝码i从1到N能否凑出总重量j。这里的j可能是负数所以我们需要一个偏移量offset来将负下标映射到数组的正索引上。设所有砝码总重为sum。那么理论上可能凑出的重量范围是[-sum, sum]。我们可以定义一个长度为2*sum 1的数组其中dp[j]表示当前能否凑出重量j - sum这样dp[sum]就对应重量0。状态转移方程是核心。对于第i个砝码重量为w如果我们已经知道了前i-1个砝码能凑出的所有状态dp_prev那么前i个砝码能凑出的新状态dp_curr为继承之前的状态dp_curr[j] dp_prev[j]如果之前能凑出重量j-w那么加上当前砝码正放就能凑出jdp_curr[j] | dp_prev[j-w]如果之前能凑出重量jw那么减去当前砝码反放相当于当前砝码贡献负值就能凑出jdp_curr[j] | dp_prev[jw]注意这里的j是加了偏移量后的数组索引在具体编程时要小心处理数组边界。初始化dp[offset] True表示不使用任何砝码时能凑出重量0。我们用一个具体的例子来走一遍流程。假设砝码重量为 [1, 4, 6]总重 sum11。初始化dp长度为 232*111偏移量 offset11。dp[11] True对应重量0。处理第一个砝码 w1从后往前或使用两个数组更新。新的可达状态有0继承、011、0-1-1。所以dp[offset1]和dp[offset-1]变为 True。处理第二个砝码 w4此时已有状态-1, 0, 1。对于每个已有状态 s新增 s4 和 s-4。结果状态集合变为-5, -4, -3, -1, 0, 1, 3, 4, 5。处理第三个砝码 w6同理最终得到所有可达状态。最后我们遍历dp数组统计j从 1 到 sum对应正重量中为 True 的个数就是能称出的不同正重量数量。这种方法的优点是直观直接体现了“状态可达”的思想。它的时间复杂度是 O(N * sum)空间复杂度如果用滚动数组优化可以做到 O(sum)。当砝码总重 sum 不是特别大时比如几万以内这个算法是可行的。但它的缺陷是sum可能很大如果砝码重且数量多导致 DP 数组过大效率降低。4. 动态规划解法二基于“重量差”的优化思路第二种DP思路更巧妙也是竞赛中更常见的解法。它不直接记录所有可能的总和而是记录“两边的重量差”或者更精确地说记录用部分砝码能构成哪些“重量值”。我们重新定义dp[i][j]表示用前i个砝码能否称出重量j。这里的j是要称的物体的重量是一个非负整数。那么这个状态是如何转移的呢考虑第i个砝码重量为w。在称重时它有三种放置方式不选那么称重能力完全取决于前i-1个砝码。即如果dp[i-1][j]为 True则dp[i][j]也为 True。放在同侧与物体同边这意味着这个砝码帮助“抵消”了物体的一部分重量。如果前i-1个砝码能称出重量j w一个比当前目标j更重的物体那么加上这个砝码在同侧抵消掉w就正好能称出重量j。所以如果dp[i-1][j w]为 True则dp[i][j]为 True。放在异侧与物体异边这意味着这个砝码直接作为标准重量来称物体。如果前i-1个砝码能称出重量|j - w|那么加上这个砝码在异侧就能称出重量j。这里取绝对值是因为如果j w说明物体重需要前i-1个砝码称出j-w的重量来平衡剩余部分如果j w说明砝码重可以把物体和一部分砝码放在同一边相当于前i-1个砝码需要称出w-j的重量但能称出的重量集合是对称的所以用绝对值|j-w|来表示前i-1个砝码能否构成这个差值。综合起来状态转移方程为dp[i][j] dp[i-1][j] || dp[i-1][j w] || dp[i-1][|j - w|]其中dp[i-1][j w]只有在j w不超过最大可能称重范围时才有效。初始化dp[0][0] True表示没有砝码时能称出重量0虽然0重量通常不计入答案。实现细节与范围最大能称出的重量j不会超过所有砝码的总重sum。因此我们的dp数组第二维大小可以设为sum 1。在检查dp[i-1][j w]时需要确保j w sum。我们依然用 [1, 4, 6] 这个例子总重 sum11。初始化dp为 (N1) x (sum1) 的布尔数组dp[0][0] True。处理 w1对于 j 从 0 到 11dp[0][j]只有 j0 为 True。dp[1][j]可能由dp[0][j]不选、dp[0][j1]同侧、dp[0][|j-1|]异侧转移而来。计算后dp[1][0] True,dp[1][1] True。处理 w4基于dp[1]计算dp[2]。例如计算dp[2][4]不选dp[1][4]是 False。同侧dp[1][448]是 False。异侧dp[1][|4-4|0]是 True。因此dp[2][4] True。最终dp[2]为 True 的 j 有0, 1, 3, 4, 5。处理 w6基于dp[2]计算dp[3]。最终dp[3]为 True 的正重量 j (1j11) 有1, 3, 4, 5, 6, 7, 8, 9, 10, 11。共10种。这种方法的空间复杂度为 O(N * sum)同样可以用滚动数组优化到 O(sum)。它的优势在于 DP 数组的第二维j直接就是目标重量非负更符合问题输出且不需要处理负索引偏移思维上更贴近“称重”这个动作本身。5. 代码实现、空间优化与细节处理理论讲完了我们来看看如何用代码实现第二种DP思路并对其进行空间优化。这里以Python为例因为其代码清晰易懂。基础二维DP实现def weighing_weight_basic(weights): total_sum sum(weights) n len(weights) # 初始化二维DP数组dp[i][j]表示前i个砝码能否称出重量j dp [[False] * (total_sum 1) for _ in range(n 1)] dp[0][0] True # 没有砝码时称出重量0 for i in range(1, n 1): w weights[i-1] for j in range(total_sum 1): # 情况1不选当前砝码 if dp[i-1][j]: dp[i][j] True continue # 情况2当前砝码放在同侧与物体同边 if j w total_sum and dp[i-1][j w]: dp[i][j] True continue # 情况3当前砝码放在异侧与物体异边 if dp[i-1][abs(j - w)]: dp[i][j] True # 统计能称出的正重量个数 count 0 for j in range(1, total_sum 1): if dp[n][j]: count 1 return count这个实现很直观但dp是一个 (N1) x (sum1) 的矩阵当 sum 很大时会占用较多内存。观察状态转移方程可以发现dp[i]的状态只依赖于dp[i-1]。因此我们可以用滚动数组将空间优化到一维。一维滚动数组优化 优化时我们必须注意遍历顺序。因为dp[i][j]可能依赖于dp[i-1][j w]一个更大的j如果从左到右遍历j在更新dp[j]代表新的dp[i][j]时dp[j w]可能已经被更新成dp[i][j w]了而不是我们需要的dp[i-1][j w]。因此我们需要从右向左遍历j或者使用一个额外的数组来保存上一行的状态。这里采用一个常用技巧使用两个集合set来代表当前行和上一行的可达重量状态。集合只存储为 True 的j值非常节省空间尤其当可达状态稀疏时。def weighing_weight_optimized(weights): total_sum sum(weights) # 使用集合存储当前可达的重量状态 prev_states {0} # 初始状态重量0可达 for w in weights: curr_states set(prev_states) # 继承上一轮的状态不选当前砝码 for s in prev_states: # 当前砝码放在异侧正贡献 new_weight s w if new_weight total_sum: curr_states.add(new_weight) # 当前砝码放在同侧负贡献注意重量取绝对值因为称出的物体重量为正 new_weight abs(s - w) if new_weight 0: # 通常不记录0重量 curr_states.add(new_weight) prev_states curr_states # 最终prev_states中包含了所有能称出的重量包括0 # 返回正重量的个数 return len([x for x in prev_states if x 0])这种集合法的代码非常简洁而且易于理解。它本质上是在迭代地计算所有可能的重量组合的绝对值。时间复杂度最坏是 O(N * M)其中 M 是状态集合的大小在实践中往往比 sum 小很多。空间复杂度则取决于状态集合的大小。关键细节与易错点重量0是否计入答案题目通常要求统计能称出的不同正重量的数量因此重量0不计入最终结果。在初始化或最后统计时要注意过滤。数组越界在二维数组实现中访问dp[i-1][jw]时必须确保jw total_sum。绝对值的处理在“异侧”情况的状态转移中使用abs(j - w)是精髓它统一处理了j w和j w两种情况。输入格式蓝桥杯的题目输入可能包含砝码个数 N然后是一行重量。需要根据具体题目描述调整读取逻辑。性能考量如果总重 sum 非常大例如超过10^5DP数组方法可能会超时或超内存。这时集合法通常更有优势但如果砝码数量 N 也很大导致状态爆炸集合法也可能变慢。需要根据数据范围选择策略。对于竞赛题通常 sum 在 10^5 以内N 在 100 以内DP方法是完全可行的。6. 算法扩展、变体与实战思考掌握了基础解法我们来看看这个问题的一些变体和扩展这能帮助我们更深入地理解其本质。变体一每种砝码有多个多重背包如果题目变成每种砝码有count[i]个我们该如何处理此时问题从“01选择”变成了“多重选择”。我们依然可以用DP的思想但状态转移需要遍历每个砝码选取的个数k从0到count[i]并且砝码可以放在左边负贡献或右边正贡献。这会使复杂度增加。一种优化方法是使用二进制拆分将每种砝码的个数拆分成若干个2的幂次的和如1,2,4,...将多重背包转化为01背包问题然后再套用上述的DP模型。另一种思路是直接使用基于“可达和”的DP但更新时对于每个砝码进行count[i]次更新每次更新考虑正负两种情况。变体二求出具体方案如果题目不仅要求数量还要求输出所有能称出的重量或者输出称出某个特定重量的方案该怎么办对于输出所有重量我们的DP数组或集合已经记录了所有可达状态直接输出即可。对于输出具体方案我们需要在DP的过程中记录“状态转移路径”。可以额外使用一个path数组path[i][j]记录在状态(i, j)时最后一个砝码的选择方式不选、正放、负放以及前一个状态。最后从目标状态(N, target)反向回溯即可得到一组解。注意方案可能不唯一。与其他背包问题的关联“砝码称重”可以看作是带负权值的背包问题的一个特例。标准的01背包问题中物品只有“放入”和“不放入”两种选择且价值非负。而在这里物品砝码有三种选择“不放入”、“放入正背包”、“放入负背包”。这拓宽了我们对背包问题模型的理解。解决这类问题的关键在于设计出能够容纳“负贡献”的状态表示无论是通过偏移量还是通过“差值”或“绝对值”的思想。实战竞赛技巧先估算数据范围这是选择算法的第一步。看N和砝码重量的上限估算出总重sum的大致范围。如果sum在几千到几万DP数组法很稳妥。如果sum很大但N较小集合法可能更优。如果N也很小甚至可以考虑DFS剪枝或位运算枚举。优先实现集合法在时间允许的情况下集合法的代码更短更不易出错省去了边界判断作为解题的首选实现往往性价比很高。调试时输出中间状态如果结果不对可以打印出每轮迭代后的dp数组或状态集合与手动计算的小例子对比很容易发现状态转移的错误。注意输入输出的格式蓝桥杯经常需要从文件读写或者要求输出一个整数。确保你的代码最后输出的是要求的答案没有多余的空格或换行。这道题虽然经典但每次重做都能加深对状态压缩和转移的理解。它像一把钥匙打开了解决一类“选择与组合”问题的大门。当你再遇到类似“一些元素有正负两种贡献求最终可能结果”的问题时不妨想想今天的砝码和天平。