[NOIP 1996 提高组] 砝码称重

题意

现在有 6 种砝码：

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

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

思路

先看最直接的暴力：

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 种砝码分别枚举使用多少枚，把所有可能得到的总重量都标记出来。

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

关键观察是：

每一枚砝码最多只能使用一次
题目只关心某个重量是否可达

因此我们把所有砝码一枚一枚拆开，每枚砝码都看成一件 0/1 物品。

设：

dp[w] 表示重量 w 是否能够被恰好称出

初始化：

dp[0] = true

表示什么都不选时可以凑出 0。

加入一枚面值为 value 的砝码时：

如果 dp[w - value] 为真，那么 dp[w] 也能变成真

所以转移就是一个布尔型 0/1 背包。

状态表

这张表说明状态的含义：

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

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

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

DP 公式

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

dp_0=true

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

dp_w\leftarrow dp_w\lor dp_{w-value}

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

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

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

代码

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
49
50
51
52
53
54#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 dp[MAXW];          // dp[w] = 是否能恰好称出重量 w
int total_weight;       // 所有砝码总重量

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

void solve() {
    memset(dp, 0, sizeof(dp));
    dp[0] = true;

    for (int i = 1; i <= TYPE_CNT; i++) {
        for (int c = 1; c <= cnt[i]; c++) {
            int w = weight_value[i];
            // 把每个砝码当成一件 0/1 物品。
            for (int sum = total_weight; sum >= w; sum--) {
                if (dp[sum - w]) {
                    dp[sum] = true;
                }
            }
        }
    }

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

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

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

    read_input();
    solve();

    return 0;
}

复杂度

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

总结

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

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

用布尔数组做可达性背包

一图流解析

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