动态规划实战：从背包问题到蓝桥杯“砝码称重”的算法精解

1. 项目概述从一道经典赛题到动态规划的实战演练最近在整理算法题库时又翻到了第十二届蓝桥杯省赛的这道“砝码称重”题。这道题可以说是动态规划DP入门与巩固的绝佳范例它没有复杂的图论结构也不涉及高深的数学知识但恰恰是这种“朴素”的题目最能考验我们对DP核心思想——状态定义与转移——的理解是否扎实。很多朋友初次接触时可能会被“称重”这个场景带偏去思考物理上的天平平衡问题但其实它的内核是一个标准的背包问题变种。简单来说题目会给你N个砝码每个砝码有各自的重量问你用这些砝码在天平可以放在左右两盘的帮助下能够称出多少种不同的正整数重量。这听起来是不是有点像我们熟悉的“子集和”问题没错但关键区别在于“天平”。在普通的0-1背包问题中物品只有“选”或“不选”来增加总重量。而在这里对于一个砝码你有三种选择不选、放在左盘视为加、放在右盘视为减。放在右盘时它相当于一个“负重量”用来平衡左盘的其他砝码或物品。这个小小的变化就让问题从一维的“能否达到某个和”变成了需要考虑“正负和”的二维更准确说是状态偏移问题。今天我就结合自己多次刷题和教学的经验把这道题的解题思路、代码实现、以及那些容易踩坑的细节掰开揉碎了讲清楚。无论你是正在备赛的选手还是想巩固DP基础的同学相信这篇都能给你带来实实在在的收获。2. 核心思路解析如何将天平问题转化为动态规划面对这道题我们首先要做的是跳出具体的物理天平模型将其抽象成一个纯粹的数学与计算机模型。这是解决所有算法问题的第一步也是最关键的一步。2.1 问题重述与数学建模题目通常的输入是砝码个数N以及一个数组weights[]存放每个砝码的重量。我们的目标是求出所有可能称出的不同正整数的重量的个数。关键约束每个砝码最多只能使用一次。天平两端的托盘都可以放置砝码。我们可以把要称量的物品假设重量为target放在左盘。那么天平平衡的方程就是左盘物品重量 左盘砝码重量之和 右盘砝码重量之和移项后得到左盘物品重量 右盘砝码重量之和 - 左盘砝码重量之和我们可以把所有放在左盘的砝码重量视为正放在右盘的砝码重量视为负-不用的砝码视为0。那么对于一组特定的选择我们计算一个总“代数和”sum Σ(sign_i * weight_i)其中sign_i属于{-1, 0, 1}。这个sum就代表了左盘物品的重量因为sum 右 - 左而物品在左盘平衡了它。因此所有可能称出的重量就是所有砝码通过系数{-1, 0, 1}线性组合后所能得到的所有不同的正整数值。举个例子有两个砝码1g 和 3g。 可能的组合只用1g放左盘(1)可称1g放右盘(-1)可称1g物品放左盘。只用3g放左盘(3)可称3g放右盘(-3)可称3g。用1g和3g(1, 3) 4g(1, -3) -2g取绝对值2g(-1, 3) 2g(-1, -3) -4g取绝对值4g。 所以能称出的正整数重量有1, 2, 3, 4。共4种。注意这里有一个非常重要的点sum可能是负数但物品重量是正的。由于天平左右对称如果sum是负数其绝对值|sum|也一定是一种可行的称量方案只需把左右盘对调即可。因此我们最终关心的是sum的绝对值所能覆盖的正整数范围。2.2 动态规划状态定义理解了数学模型后我们自然想到用动态规划来枚举所有可能的组合。这是一个典型的“决策”过程对于第i个砝码我们需要决定给它分配系数-1 0 或 1。最直接的状态定义是dp[i][j]表示考虑前i个砝码能否得到代数和j。 但这里的j代数和可能是负数。数组下标不能为负所以我们需要进行坐标偏移。设所有砝码总重量为total_sum。那么理论上代数和j的范围是[-total_sum, total_sum]。我们可以设定一个偏移量offset total_sum这样新的下标j j offset的范围就是[0, 2*total_sum]完美地映射到数组下标。因此我们定义dp[i][j]布尔型True/False。表示考虑前i个砝码能否组成代数和为(j - offset)的方案。 其中i从 0 到 Nj从 0 到2*total_sum。初始状态dp[0][offset] True。表示不考虑任何砝码时代数和为0是可达的。2.3 状态转移方程推导对于第i个砝码重量为w我们从dp[i-1]的状态来推导dp[i]。 如果dp[i-1][k]为True即前i-1个砝码可以组成代数和为(k-offset)那么对于第i个砝码不选dp[i][k] True。放左盘加新的代数和 (k-offset) w。对应新的下标new_j (k-offset) w offset k w。只要kw在数组范围内dp[i][kw] True。放右盘减新的代数和 (k-offset) - w。对应新的下标new_j k - w。只要k-w在数组范围内dp[i][k-w] True。状态转移方程可以写作dp[i][k] dp[i-1][k] || dp[i-1][k - w] || dp[i-1][k w]这里需要注意边界检查确保k-w和kw不越界。这个方程非常优美地涵盖了三种情况。最终我们查看dp[N][j]中所有为True的状态计算abs(j - offset)统计其中不同的正整数个数就是答案。3. 代码实现与逐行详解理论清晰之后我们来看代码实现。我会提供Python和C两种版本的代码并附上详细的注释。这里以Python版本为主进行讲解因为其可读性更高。3.1 Python版本实现与解析def solve(): N int(input()) # 砝码个数 weights list(map(int, input().split())) # 砝码重量列表 total_sum sum(weights) # 计算所有砝码总重确定代数和范围 offset total_sum # 偏移量让负下标变正 # dp数组大小考虑N个砝码代数和范围[-total_sum, total_sum]偏移后是[0, 2*total_sum] # 我们使用二维数组dp[i][j]表示前i个砝码能否得到偏移后的代数和j # 初始化一个 (N1) 行(2*total_sum 1) 列的二维布尔数组全部为False dp [[False] * (2 * total_sum 1) for _ in range(N 1)] # 初始状态没有砝码时代数和为0是可达的。0偏移后就是offset。 dp[0][offset] True # 动态规划过程 for i in range(1, N 1): # i从1到N代表考虑前i个砝码 w weights[i - 1] # 第i个砝码的重量注意列表下标从0开始 for j in range(2 * total_sum 1): # 遍历所有可能的偏移后代数和j # 状态继承不选第i个砝码 if dp[i - 1][j]: dp[i][j] True # 状态转移第i个砝码放左盘加 if j - w 0 and dp[i - 1][j - w]: dp[i][j] True # 状态转移第i个砝码放右盘减 if j w 2 * total_sum and dp[i - 1][j w]: dp[i][j] True # 统计结果 result_set set() for j in range(2 * total_sum 1): if dp[N][j]: # 如果考虑所有砝码后偏移后代数和j可达 real_weight j - offset # 计算真实的代数和 if real_weight 0: # 我们只关心正整数的重量 result_set.add(real_weight) print(len(result_set)) if __name__ __main__: solve()逐行关键点解析输入处理标准输入读取N和重量列表。这是蓝桥杯常见的输入格式。total_sum与offsettotal_sum决定了状态空间的大小。offset是核心技巧用于处理负下标。DP数组初始化dp是一个二维布尔列表。第一维大小N1表示考虑砝码的个数0到N。第二维大小2*total_sum1涵盖了偏移后的所有可能代数和从0到2*total_sum对应真实代数和-total_sum到total_sum。初始状态dp[0][offset] True。这是动态规划的“起点”代表空集合的和为0。双重循环外层循环i遍历每一个砝码。注意weights[i-1]是因为我们的dp第一维i从1开始计数而重量列表索引从0开始。内层循环j遍历所有可能的偏移后状态。对于每个状态j我们根据dp[i-1][j]及其相邻状态dp[i-1][j-w]和dp[i-1][jw]来更新dp[i][j]。这里的j代表偏移后的代数和。三个if判断的顺序先继承“不选”的状态再判断“加”和“减”。这三个判断是“或”的关系只要有一个为真dp[i][j]就为真。代码中用三个独立的if语句实现因为dp[i][j]可能被多次设置为True但这不影响结果。边界检查在判断j-w和jw时必须确保索引在[0, 2*total_sum]范围内否则会数组越界。结果统计遍历dp[N]即考虑所有砝码后的最终状态行。对于每个可达的状态j计算其真实重量real_weight j - offset。如果real_weight 0则将其加入一个集合result_set中。使用集合是为了自动去重。输出最终集合的大小就是能称出的不同正整数的数量。3.2 C版本实现空间优化版Python版本便于理解但在竞赛中C通常有性能优势。下面给出一个使用了滚动数组进行空间优化的C版本。滚动数组是DP中常见的优化技巧可以将二维DP压缩到一维大幅节省内存。#include iostream #include vector #include cmath using namespace std; int main() { int N; cin N; vectorint weights(N); int total_sum 0; for (int i 0; i N; i) { cin weights[i]; total_sum weights[i]; } int offset total_sum; // 使用一维dp数组dp[j]表示在当前考虑砝码的阶段能否组成偏移后代数和j vectorbool dp(2 * total_sum 1, false); dp[offset] true; // 初始状态 for (int i 0; i N; i) { int w weights[i]; // 需要一个新的数组来记录本层结果因为不能直接用旧状态覆盖 vectorbool new_dp dp; // 继承“不选”的情况 for (int j 0; j 2 * total_sum; j) { if (dp[j]) { // 如果上一轮j状态可达 if (j w 2 * total_sum) { new_dp[j w] true; // 放左盘加 } if (j - w 0) { new_dp[j - w] true; // 放右盘减 } } } dp move(new_dp); // 更新dp为当前层结果 } int count 0; // 统计所有正整数的重量 for (int j offset 1; j 2 * total_sum; j) { // j从offset1开始保证real_weight0 if (dp[j]) { count; } } cout count endl; return 0; }C版本要点滚动数组我们只使用一维数组dpnew_dp。在每一轮考虑第i个砝码开始时new_dp先初始化为dp这相当于继承了“不选当前砝码”的所有状态。然后我们遍历dp即上一轮的状态如果某个状态j可达则更新new_dp[jw]和new_dp[j-w]。一轮结束后用new_dp替换dp。这样空间复杂度从O(NM)降到了O(M)其中M2total_sum1。遍历顺序在更新new_dp时我们遍历的是dp旧状态更新的是new_dp新状态。这个顺序很重要。如果直接在dp上更新会出现“当前砝码被重复使用”的问题类似于完全背包问题而本题每个砝码最多用一次0-1背包特性所以需要区分新旧状态。结果统计因为真实重量real_weight j - offset且real_weight 0所以只需要遍历j从offset1到2*total_sum即可无需使用集合去重因为DP状态本身不会重复计数同一种重量。4. 算法复杂度分析与优化思考理解了代码我们再来分析一下算法效率并看看有没有可以优化的地方。时间复杂度动态规划有两层循环。外层循环遍历N个砝码内层循环遍历所有可能的状态从0到2*total_sum记为M。因此时间复杂度为O(N * M)其中M 2 * total_sum 1。total_sum是所有砝码重量之和。如果砝码重量很大或者数量很多导致total_sum很大这个算法可能会比较慢。但在蓝桥杯的评测环境下通常total_sum会被控制在一个合理的范围例如10^5以内使得O(N * M)的复杂度可以接受。空间复杂度二维DP未优化版本O(N * M)。一维DP滚动数组优化版本O(M)。潜在的优化点与思考bitset优化C特有由于dp数组是布尔类型我们可以使用C STL中的bitset来存储状态。bitset在内存中以位存储并且位运算速度极快。可以将内层循环的遍历和条件判断转化为bitset的左移、右移和或运算。这通常能带来常数级别的巨大性能提升。#include bitset bitset200005 dp; // 假设总重不超过100000 dp.set(offset); // 初始化 for (int w : weights) { dp dp | (dp w) | (dp w); } // 统计dp[offset1, ...]中1的个数这段代码极其简洁dp w实现了“加w”的操作dp w实现了“减w”的操作|操作符合并了“不选”、“加”、“减”三种状态。这是竞赛中处理此类布尔DP的利器。哈希集合Python在Python中我们也可以不用二维布尔数组而使用集合来记录当前可达的所有代数和。每考虑一个砝码就基于旧集合生成一个新集合。reachable {0} for w in weights: new_set set() for s in reachable: new_set.add(s) # 不选 new_set.add(s w) # 放左盘 new_set.add(s - w) # 放右盘 reachable new_set # 最后统计reachable中正数的个数这种方法代码更直观且自动去重。但当total_sum很大且砝码很多时集合的大小可能会膨胀效率不如数组直接寻址快。不过对于中小规模数据这是一种非常清晰的写法。5. 常见错误与调试技巧实录即便思路清晰在实现时也难免会遇到各种问题。下面我总结几个常见的“坑”并分享调试方法。5.1 错误类型汇总错误现象可能原因解决方案结果比正确答案少1. 只考虑了砝码全放同一边即只做加法忽略了放右盘减法的情况。2. 初始化错误例如dp[0][0]True但没加偏移量。3. 结果统计时只统计了joffset的漏掉了joffset但绝对值是正数的情况应统计abs(j-offset)0。1. 检查状态转移方程确保包含了j-w和jw或加、减两种转移。2. 确认offset的使用初始状态应为dp[0][offset]True。3. 统计时遍历所有j计算abs(real_weight)用集合存储正整数。结果比正确答案多1. 统计了重量0。2. 砝码被重复使用完全背包问题。1. 在统计结果时判断条件应为real_weight 0而不是real_weight 0。2. 检查DP循环顺序。如果是用一维数组必须从后往前遍历0-1背包或使用新旧两个数组。本例中由于有加减两种操作从后往前遍历也不方便推荐使用二维数组或显式的新旧数组。数组越界Runtime Error状态转移时访问dp[i-1][j-w]或dp[i-1][jw]没有检查下标是否在[0, 2*total_sum]范围内。在访问j-w和jw前加上边界条件判断if j-w 0和if jw 2*total_sum。内存超限MLE使用了未压缩的二维DP数组且N或total_sum较大。例如N100, total_sum10^5二维数组大小约为100 * 200001布尔型也可能超限。使用滚动数组优化到一维或者使用C的bitset。在Python中如果数据极大可能需要考虑其他算法或使用array(b)等更节省内存的结构。时间超限TLE算法复杂度O(N*M)过高total_sum太大。检查题目数据范围。如果total_sum确实太大如10^6以上O(N*M)的DP可能不可行需要考虑是否存在更优的数学性质或折半搜索等算法。对于蓝桥杯本题通常DP是正解。5.2 调试与测试技巧从小样例开始不要一上来就用复杂数据。先用题目中的例子或者自己构造极简例子。例1N1 weights[1]。答案应为1能称出1g。例2N2 weights[1,1]。可能组合±1, ±1 和可能为 -2,0,2。正整数有1,2不对仔细算单个1g可以称出1g。两个1g同侧得2g异侧得0g。所以能称出1g和2g。答案是2。例3N3 weights[1,2,3]。可以手算或写个小程序暴力枚举验证。打印DP表对于小的测试用例将DP表特别是二维的打印出来是理解程序运行过程的最有效方式。你可以看到每个砝码加入后可达状态是如何扩散的。# 在DP循环后打印dp数组仅用于调试小数据 def print_dp(dp, offset): for i in range(len(dp)): states [] for j in range(len(dp[i])): if dp[i][j]: states.append(str(j - offset)) print(f前{i}个砝码可达和: {, .join(states)})对拍写一个暴力枚举所有可能组合3^N种的程序用于小数据量N10下的结果验证。确保你的DP程序输出和暴力程序完全一致。这是检验算法正确性的黄金标准。关注边界特别注意total_sum0虽然题目可能不会出现N0等情况。确保你的程序能正确处理。5.3 一个易错点的深入剖析为什么不能用一维数组的直接更新很多同学学会0-1背包的一维数组写法逆序更新后会想当然地套用到这里dp [False] * (2*total_sum1) dp[offset] True for w in weights: for j in range(2*total_sum, -1, -1): # 错误写法 if j - w 0 and dp[j - w]: dp[j] True if j w 2*total_sum and dp[j w]: dp[j] True这段代码是错误的。原因在于0-1背包逆序更新是为了保证每个物品只被用一次它基于的转移方程是dp[j] dp[j] or dp[j - w]只有一种转移方向从j-w到j。而在我们的问题中转移方程是dp[j] dp[j] or dp[j-w] or dp[jw]。当你逆序更新j时dp[jw]实际上是在你更新dp[j]的同一轮中被提前更新了因为jw j在逆序中jw先于j被访问。这相当于允许了“一个砝码同时产生加和减的效果”或者更混乱的状态依赖导致结果错误。因此对于这种带有“加减”两种方向转移的DP最安全的方式是使用二维数组或者像前面C代码那样显式地使用两个一维数组dp和new_dp来区分上一轮和本轮的状态。