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

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 到 N，j从 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个砝码：

1. 不选：dp[i][k] = True。
2. 放左盘（加）：新的代数和 =(k-offset) + w。对应新的下标new_j = (k-offset) + w + offset = k + w。只要k+w在数组范围内，dp[i][k+w] = True。
3. 放右盘（减）：新的代数和 =(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和k+w不越界。

这个方程非常优美地涵盖了三种情况。最终，我们查看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 # 初始化一个 (N+1) 行，(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()

逐行关键点解析：

1. 输入处理：标准输入读取N和重量列表。这是蓝桥杯常见的输入格式。
2. total_sum与offset：total_sum决定了状态空间的大小。offset是核心技巧，用于处理负下标。
3. DP数组初始化：dp是一个二维布尔列表。第一维大小N+1，表示考虑砝码的个数（0到N）。第二维大小2*total_sum+1，涵盖了偏移后的所有可能代数和（从0到2*total_sum，对应真实代数和-total_sum到total_sum）。
4. 初始状态：dp[0][offset] = True。这是动态规划的“起点”，代表空集合的和为0。
5. 双重循环：
   • 外层循环i：遍历每一个砝码。注意weights[i-1]是因为我们的dp第一维i从1开始计数，而重量列表索引从0开始。
   • 内层循环j：遍历所有可能的偏移后状态。对于每个状态j，我们根据dp[i-1][j]及其相邻状态dp[i-1][j-w]和dp[i-1][j+w]来更新dp[i][j]。这里的j代表偏移后的代数和。
   • 三个if判断的顺序：先继承“不选”的状态，再判断“加”和“减”。这三个判断是“或”的关系，只要有一个为真，dp[i][j]就为真。代码中用三个独立的if语句实现，因为dp[i][j]可能被多次设置为True，但这不影响结果。
6. 边界检查：在判断j-w和j+w时，必须确保索引在[0, 2*total_sum]范围内，否则会数组越界。
7. 结果统计：遍历dp[N]（即考虑所有砝码后的最终状态行）。对于每个可达的状态j，计算其真实重量real_weight = j - offset。如果real_weight > 0，则将其加入一个集合result_set中。使用集合是为了自动去重。
8. 输出：最终集合的大小就是能称出的不同正整数的数量。

3.2 C++版本实现（空间优化版）

Python版本便于理解，但在竞赛中，C++通常有性能优势。下面给出一个使用了滚动数组进行空间优化的C++版本。滚动数组是DP中常见的优化技巧，可以将二维DP压缩到一维，大幅节省内存。

#include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int N; cin >> N; vector<int> 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 vector<bool> dp(2 * total_sum + 1, false); dp[offset] = true; // 初始状态 for (int i = 0; i < N; ++i) { int w = weights[i]; // 需要一个新的数组来记录本层结果，因为不能直接用旧状态覆盖 vector<bool> 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从offset+1开始，保证real_weight>0 if (dp[j]) { count++; } } cout << count << endl; return 0; }

C++版本要点：

1. 滚动数组：我们只使用一维数组dp，new_dp。在每一轮（考虑第i个砝码）开始时，new_dp先初始化为dp，这相当于继承了“不选当前砝码”的所有状态。然后，我们遍历dp（即上一轮的状态），如果某个状态j可达，则更新new_dp[j+w]和new_dp[j-w]。一轮结束后，用new_dp替换dp。这样空间复杂度从O(NM)降到了O(M)，其中M=2total_sum+1。
2. 遍历顺序：在更新new_dp时，我们遍历的是dp（旧状态），更新的是new_dp（新状态）。这个顺序很重要。如果直接在dp上更新，会出现“当前砝码被重复使用”的问题（类似于完全背包问题），而本题每个砝码最多用一次（0-1背包特性），所以需要区分新旧状态。
3. 结果统计：因为真实重量real_weight = j - offset，且real_weight > 0，所以只需要遍历j从offset+1到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)。

潜在的优化点与思考：

1. bitset优化（C++特有）：由于dp数组是布尔类型，我们可以使用C++ STL中的bitset来存储状态。bitset在内存中以位存储，并且位运算速度极快。可以将内层循环的遍历和条件判断，转化为bitset的左移、右移和或运算。这通常能带来常数级别的巨大性能提升。

   #include <bitset> bitset<200005> dp; // 假设总重不超过100000 dp.set(offset); // 初始化 for (int w : weights) { dp = dp | (dp << w) | (dp >> w); } // 统计dp[offset+1, ...]中1的个数

   这段代码极其简洁，dp << w实现了“加w”的操作，dp >> w实现了“减w”的操作，|操作符合并了“不选”、“加”、“减”三种状态。这是竞赛中处理此类布尔DP的利器。

2. 哈希集合（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 错误类型汇总

5.2 调试与测试技巧

1. 从小样例开始：不要一上来就用复杂数据。先用题目中的例子，或者自己构造极简例子。

   • 例1：N=1， weights=[1]。答案应为1（能称出1g）。
   • 例2：N=2， weights=[1,1]。可能组合：±1, ±1 => 和可能为 -2,0,2。正整数有1,2？不对，仔细算：单个1g可以称出1g。两个1g：同侧得2g，异侧得0g。所以能称出1g和2g。答案是2。
   • 例3：N=3， weights=[1,2,3]。可以手算或写个小程序暴力枚举验证。

2. 打印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. 对拍：写一个暴力枚举所有可能组合（3^N种）的程序，用于小数据量（N<=10）下的结果验证。确保你的DP程序输出和暴力程序完全一致。这是检验算法正确性的黄金标准。

4. 关注边界：特别注意total_sum=0（虽然题目可能不会出现），N=0等情况。确保你的程序能正确处理。

5.3 一个易错点的深入剖析：为什么不能用一维数组的直接更新？

很多同学学会0-1背包的一维数组写法（逆序更新）后，会想当然地套用到这里：

dp = [False] * (2*total_sum+1) 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[j+w]。当你逆序更新j时，dp[j+w]实际上是在你更新dp[j]的同一轮中被提前更新了（因为j+w > j，在逆序中j+w先于j被访问）。这相当于允许了“一个砝码同时产生加和减的效果”，或者更混乱的状态依赖，导致结果错误。

因此，对于这种带有“加减”两种方向转移的DP，最安全的方式是使用二维数组，或者像前面C++代码那样，显式地使用两个一维数组dp和new_dp来区分上一轮和本轮的状态。