复赛一：货币系统(money)

洛谷：p5020
OJ：i5020

这是一道 经典的货币系统最小化问题（出现在 NOIP 2018 提高组 T2《货币系统》）。
我们先来逐层分析题意与关键逻辑。

一、题目背景理解

给定一个货币系统[(n, a)]，其中有 n 种面额：a₁, a₂, …, aₙ（每种币可以无限使用）。

目标

我们要找一个 更简化的货币系统[(m, b)]，满足：(m,b) 与 (n,a) 等价；并且 m 尽可能小（即删掉冗余的币种）。

二、等价的定义

对于任意非负整数 x：

• 如果 x 在系统 (n,a) 中可以表示；
• 那么 x 在系统 (m,b) 中也必须可以表示；
• 反之亦然。

换句话说：

新系统 (m,b) 必须能凑出所有旧系统 (n,a) 能凑出的金额，且不能多凑出原系统凑不出的金额。

三、问题本质

本题其实等价于：删除多余的货币面额，使剩下的面额集合能凑出与原系统完全相同的所有金额。何为多余的面额

如果一个面额可以被其他面额的非负线性组合表示出来，那么它是 冗余的，可以删去。

例如：

a = [2, 5, 9]
→ 9 = 2*2 + 5*1，所以 9 可被表示
→ 因此可以删去 9。

四、关键数学思想：可表示性与最简集合

对于货币系统，若我们定义：
能表示的金额集合：
S = { x | 存在 t₁,t₂,…,tₙ≥0，使得 a₁t₁ + a₂t₂ + … + aₙtₙ = x }

则问题转化为：

找出一个最小的子集 b ⊆ a，使得
由 b 构成的 S(b) = S(a)。

五、算法思路（贪心 + 动态规划）

Step1: 排序

把 a 从小到大排序：a₁ ≤ a₂ ≤ … ≤ aₙ

Step 2: 动态规划判断“是否可由之前面额表示”

我们维护一个 dp[x] 数组：

• dp[x] = true 表示金额 x 可以由当前选中的面额凑出。
• 初始 dp[0] = true。

对于每个面额 a[i]：

• 如果 dp[a[i]] = true，说明这个面额 可由之前的面额组合凑出，因此是 冗余的；否则，将该面额 加入系统，并更新所有能表示的金额。

伪代码示例：

sort(a, a+n);
dp[0] = true;
ans = 0;
for (int i = 0; i < n; ++i) {
    if (!dp[a[i]]) {
        ++ans; // 这个面额是必要的
        for (int j = a[i]; j <= a[n-1]; ++j)
            if (dp[j - a[i]]) dp[j] = true;
    }
}

六、复杂度分析

• n ≤ 100
• a[i] ≤ 25000
• 用 DP 做可达性标记即可。
• 时间复杂度：O(n × max(a))

七、样例分析

输入

2
4
3 19 10 6
5
11 29 13 19 17

对第1组：a = [3, 6, 10, 19]

• 3：选入，系统 {3}
• 6：6=3×2 → 冗余
• 10：不能被 3 表示 → 加入，系统 {3,10}
• 19：19=3×3+10 → 可表示 → 冗余
  最小 m=2

对第2组：a = [11, 13, 17, 19, 29]

• 11：选入
• 13：选入
• 17：不能由11,13凑出 → 选入
• 19：不能由11,13,17凑出 → 选入
• 29：不能由之前凑出 → 选入
  最小 m=5

八、输出

2
5

总结要点

代码实现：

 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

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2024-09-30 19:28:38
 * 最后修改: 2025-10-05 18:29:31
 * 文件描述: 2018年提高组第一题  货币系统
****************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_COIN_VALUE = 250; // 最大面值
                  
int main() {
   // freopen("money.in","r",stdin);
   // freopen("money.out","w",stdout);
    int T; // 测试数据组数
    cin >> T;
    while (T--) {
        int n; // 货币种数
        cin >> n;
        vector<int> a(n); // 面额数组
        for (int i = 0; i < n; ++i) {
            cin >> a[i];   
        }
        sort(a.begin(), a.end()); // 将面额排序
        int max_coin=a.back();// 最大面值
        vector<bool> dp(max_coin + 1, false); // dp数组，表示金额是否可达
        dp[0] = true; // 金额0可达
        int m = 0; // 最小货币种数
        for (int i = 0; i < n; ++i) {
            int ai = a[i];
            if (!dp[ai]) {
                // 必要面额，计入答案，并做完全背包更新
                ++m;
                for (int j = ai; j <= max_coin; ++j) {
                    if (dp[j - ai]) dp[j] = 1;
                }
            }
            // 否则 can[ai]==true，说明 ai 已可由更小面额表示，属于冗余，跳过
        }
        cout << m << endl; // 输出最小的m
    }
    return 0;
}