[蓝桥杯 2021 省 AB] 砝码称重

题意

有 N 个砝码，每个砝码重量为 W_i。砝码可以放在天平两边，也可以不放。问一共能称出多少种不同的正整数重量。

思路

一句话本质：每个砝码有三种选择——放左边等效于减去该重量、放右边等效于加上该重量、不放等效于不变，转化为带偏移量的可行性背包。

先看最直接的暴力枚举，帮助理解题意：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
w = [int(x) for x in data[1:1+n]]

ans = set()

def dfs(i, left, right):
    if i == n:
        diff = abs(left - right)
        if diff > 0:
            ans.add(diff)
        return
    dfs(i + 1, left + w[i], right)
    dfs(i + 1, left, right + w[i])
    dfs(i + 1, left, right)

dfs(0, 0, 0)
print(len(ans))

brute.py 对每个砝码枚举三种选择：放左盘、放右盘、不选。所有 N 个砝码决定完后，记录左右盘重量差的绝对值作为可称出的重量。复杂度 O(3^N)，只能用于 N ≤ 15 的小数据验证。

每个砝码放在天平上，到底改变了什么？

天平称重的本质是两边重量差。放左边让右边等效减去这个重量（差值减 w），放右边让右边等效加上这个重量（差值加 w）。所以每个砝码对最终差值的净贡献要么是 -w，要么是 +w，要么是 0（不放）。

直接 DP 表示差值有什么问题？

差值可能为负（左边比右边重），而 C++ 数组下标不能为负数。

怎么解决负数下标？

引入偏移量 offset。设所有砝码总重为 sum，可能的差值范围是 [-sum, sum]。把这个区间整体平移 sum，变成 [0, 2·sum]。不称任何重量时差值为 0，对应偏移后的下标 offset = sum。所以初始 dp[offset] = true。

每个砝码的转移怎么写？

设当前砝码重量为 w。对每个已有的可达状态 j（dp[j] = true），下一轮可以使：

不放：ndp[j] = true
放右边（差值 +w）：ndp[j + w] = true（需 j + w ≤ 2·sum）
放左边（差值 -w）：ndp[j - w] = true（需 j - w ≥ 0）

三个方向覆盖了每个砝码的全部可能。

答案怎么统计？

差值 > 0 才对应一种有效的正整数重量。统计 dp 数组中索引 offset + 1 到 2·sum 范围内 true 的个数即为答案。

状态表

状态	含义
`dp[j]`	经过若干砝码选择后，差值 `j - offset` 是否可达

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:13
 * update_at: 2026-08-08 23:13
 * 砝码可放左或右，用偏移量 (-sum~sum → 0~2*sum)
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
int n, sum;
int w[105];
bool dp[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
        sum += w[i];
    }

    int offset = sum;
    dp[offset] = true;

    for (int i = 1; i <= n; ++i) {
        bool ndp[maxn] = {};
        for (int j = 0; j <= 2 * sum; ++j) {
            if (!dp[j]) continue;
            ndp[j] = true;
            ndp[j + w[i]] = true;
            ndp[j - w[i]] = true;
        }
        memcpy(dp, ndp, sizeof(dp));
    }

    int ans = 0;
    for (int j = offset + 1; j <= 2 * sum; ++j)
        if (dp[j]) ++ans;
    cout << ans << "\n";
    return 0;
}

复杂度

时间复杂度：O(N · sum)，sum 为砝码总重，不超过 10^5
空间复杂度：O(sum)

总结

这题的核心是把"砝码可放两边"这个条件翻译成带偏移量的可行状态转移。偏移量是处理负数下标的标准技巧。以后看到"可正可负的选择对某值的积累影响"时，先想偏移量能否把范围映射到非负区间。

[蓝桥杯 2021 省 AB] 砝码称重

目录

题意

思路

状态表

代码

复杂度

总结