[NOIP 1996 提高组] 砝码称重

题意

现在有 6 种砝码：

1g, 2g, 3g, 5g, 10g, 20g

每种砝码都有若干枚，问利用这些砝码一共能称出多少种不同的正整数重量。

思路

一句话本质：每种砝码有 cnt[i] 枚——把每枚砝码看成一个独立的 0/1 物品，用 bitset 做多重可行性背包，统计可达正整数重量数。

先看最直接的暴力：

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
45
46
47
48// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int TYPE_CNT = 6;
const int weight_value[TYPE_CNT + 1] = {0, 1, 2, 3, 5, 10, 20};
const int MAXW = 1005;

int cnt[TYPE_CNT + 1];     // 每种砝码的数量
bool reachable[MAXW];      // reachable[w] = 是否能称出重量 w
int total_weight;          // 所有砝码总重量

void dfs(int type_id, int current_sum) {
    if (type_id > TYPE_CNT) {
        if (current_sum > 0) {
            reachable[current_sum] = true;
        }
        return;
    }

    for (int use_cnt = 0; use_cnt <= cnt[type_id]; use_cnt++) {
        dfs(type_id + 1, current_sum + use_cnt * weight_value[type_id]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    total_weight = 0;
    for (int i = 1; i <= TYPE_CNT; i++) {
        cin >> cnt[i];
        total_weight += cnt[i] * weight_value[i];
    }

    memset(reachable, 0, sizeof(reachable));
    dfs(1, 0);

    int answer = 0;
    for (int w = 1; w <= total_weight; w++) {
        if (reachable[w]) {
            answer++;
        }
    }

    cout << "Total=" << answer << '\n';
    return 0;
}

brute.cpp 对 6 种砝码分别枚举使用多少枚，把所有可能得到的总重量都标记出来。

这个做法能帮助理解题意，但更统一、更标准的写法是把问题改成背包。

题目有 6 种砝码，每种有多枚——这和普通 01 背包有什么不同？

普通 01 背包每个物品独立存在于输入中，每个物品最多选一次。这题每种砝码有多枚相同重量的，本质是多重背包——每个物品类型有数量限制。由于总重 ≤ 1000，直接逐枚展开成 0/1 物品完全可行。

怎么用 DP 表示一个重量是否可称？

设 dp[w] 表示重量 w 能否凑出。初始 dp[0] = true。每加入一枚重量为 value 的砝码，原本能凑出的每个重量，加上这枚砝码后也能凑出。用 bitset 表达：dp |= (dp << value)——一行搞定整轮转移。

为什么用 bitset 而不是普通 bool 数组？

总重 ≤ 1000 很小，普通 bool 数组完全够用。但 bitset 更简洁，dp |= (dp << w) 等价于对 j 从 sum 到 w 倒序做 dp[j] |= dp[j-w]，而且位操作是底层并行，常数极小。

最后 dp.count() 统计可达重量总数，减 1 去掉 dp[0]（一个砝码都不用不算）。

状态表

这张表说明状态的含义：

状态	含义
`dp[w]`	重量 `w` 是否能够被恰好称出

从这个定义可以看出，这题状态里存的不是"最大值"或"方案数"，而只是可达性。这正是背包中的另一类常见状态。

最后统计 1..总重量 中有多少个 dp[w] = true 即可。

DP 公式

设 $dp_w$ 表示重量 $w$ 是否能够被恰好称出。初始化：

dp_0=true

把每个实际存在的砝码都当作一个 0/1 物品，重量为 $value$ ，则：

dp \leftarrow dp \lor (dp \ll value)

最终答案是所有正可达重量的数量：

\sum_{w=1}^{sum} [dp_w=true]

公式解释：状态只表示某个重量能否被称出。加入一个实际存在的砝码后，原来能称出 w-value 的方案再加上这个砝码，就能称出 w。

代码

本题有两种写法，核心思路完全一致（把每枚砝码展开成 0/1 物品做可达性背包）：

bitset 位运算（main.cpp）：dp |= (dp << w) 一行完成整轮转移，代码最简洁。
普通 bool 数组 + 01 背包倒序（main-rainboy.cpp）：用两层循环逐枚展开砝码，逆序转移，不依赖位运算，更容易看出转移逻辑。

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/**
 * 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
 * 多重背包可行性，bitset
 */
#include <bits/stdc++.h>
using namespace std;

const int maxw = 1005;
int cnt[6];
int w[6] = {1, 2, 3, 5, 10, 20};
bitset<maxw> dp;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    dp[0] = 1;
    for (int i = 0; i < 6; ++i) {
        cin >> cnt[i];
        for (int k = 0; k < cnt[i]; ++k)
            dp |= (dp << w[i]);
    }
    int ans = dp.count() - 1;
    cout << "Total=" << ans << "\n";
    return 0;
}

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/**
 * 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-09-06 20:35
 * update_at: 2026-09-06 20:35
 * 多重可行性背包，01 背包思维（普通 bool 数组）
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;         // 总重量上限
int cnt[6];                    // 每种砝码的数量
int w[6] = {1, 2, 3, 5, 10, 20}; // 六种砝码的重量
bool dp[MAXN];                 // dp[w] 表示重量 w 是否能被称出

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int sum = 0;
    for (int i = 0; i < 6; ++i) {
        cin >> cnt[i];
        sum += cnt[i] * w[i];
    }
    dp[0] = true;
    // 把每枚砝码看成一个独立的 0/1 物品（重量 = 价值）。逐枚展开后按 01 背包倒序转移。
    for (int i = 0; i < 6; ++i)
        for (int k = 0; k < cnt[i]; ++k)
            for (int j = sum; j >= w[i]; --j)
                if (dp[j - w[i]]) dp[j] = true;
    int ans = 0;
    for (int j = 1; j <= sum; ++j)
        if (dp[j]) ++ans;
    cout << "Total=" << ans << "\n";
    return 0;
}

复杂度

时间复杂度： $O(KW)$ ，其中 K 是砝码总数，W 是总重量
空间复杂度： $O(W)$

总结

这题的关键是把"有限个砝码"翻译成"有限个 0/1 物品"。

以后看到"每件东西最多用一次，并且只需要知道哪些和可达"这类条件时，可以优先想到：

用布尔数组做可达性背包

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。