复赛一：货币系统(money)

洛谷：p5020
OJ：i5020

算法思路：

题目要求找到一个与原货币系统等价的最小货币系统，使得货币种数 ( m ) 尽可能小。

等价的货币系统定义：

两个货币系统等价，当且仅当对于任意非负整数金额 ( x )，要么都能被两个系统表示，要么都不能被表示。

问题转化：

我们需要从原有的货币面额中选出尽可能少的面额，使得在原货币系统中能够表示的所有金额，在新货币系统中仍然能够表示；反之，在原系统中不能表示的金额，在新系统中也不能表示。

算法步骤：

1. 输入与预处理：

• 读取货币种数 ( n ) 和面额数组 ( a )。
• 对面额数组进行排序，方便后续处理。

1. 初始化：

• 使用一个布尔数组 ( dp ) 来记录哪些金额是可达的。初始化 dp[0] = true（金额0可达）。

1. 贪心选择必要的面额：

• 初始化最小货币种数 ( m = 0 )。
• 遍历排序后的面额数组，对于每个面额 c = a[i] ：
  • 检查当前面额是否是必要的：
  • 如果 dp[c] = true，说明当前面额c可以由之前选取的面额组合而成，是多余的，不需要加入新的货币系统。
  • 如果 dp[c] = false，说明当前面额 c 无法由之前的面额组合而成，是必要的，需要加入新的货币系统。
  • 更新状态：
  • 如果当前面额是必要的，增加货币种数 m 。
  • 使用当前面额 c 更新 dp 数组，使得新的金额可达：
    [
    dp[j] = dp[j] ∨ dp[j – c], 对于所有 j ≥ c
    ]
• 这个过程实际上是在检查每个面额是否是必要的，如果它无法由之前的面额组合表示，那么它就是必要的。

1. 输出结果：

• 输出最小的货币种数 m 。

算法核心思想：

• 贪心策略： 我们希望选择尽可能少的面额来覆盖原系统中的所有可达金额。
• 可达性判定： 使用动态规划的方法，记录哪些金额是可达的。对于每个面额，判断它是否可以由之前的面额组合而成。
• 必要性判定： 如果一个面额无法由之前的面额组合而成，那么它就是必要的，必须加入新的货币系统。

举例说明：

以输入样例1为例：

4
3 6 10 19

算法步骤：

1. 面额排序：将面额数组按从小到大排序，得到：a=[3,6,10,19]
2. 初始化：
   • 最大面额 max_coin=19
   • 初始化动态规划数组 dp[0..19]为 false，但 dp[0]=true，表示金额0可达。
   • 设定必要的货币种数 m=0
3. 遍历面额数组，判断每个面额是否必要：
   （1）面额 c=3：
   检查是否必要：
   dp[3]=false，因此面额3是必要的。更新必要的货币种数 m=m+1=1
   更新 dp 数组：
   对于 j从 c到 max_coin，即 j=3 到 19：dp[j]=dp[j]∨dp[j−c]
   更新过程：
   dp[3]=dp[3]∨dp[0]=false∨true=true
   dp[6]=dp[6]∨dp[3]=false∨true=true
   dp[9]=dp[9]∨dp[6]=false∨true=true
   以此类推，更新 dp[12],dp[15],dp[18] 为 true
   
   （2）面额 c=6：
   • 检查是否必要：
     • dp[6]=true，说明金额6已可达，面额6是不必要的。跳过，不更新 m和 dp数组。
   （3）面额 c=10：
   检查是否必要：
   dp[10]=false，因此面额10是必要的。更新必要的货币种数 m=m+1=2
   更新 dp 数组：
   对于 j=10 到 19：
   dp[10]=dp[10]∨dp[0]=false∨true=true
   dp[13]=dp[13]∨dp[3]=false∨true=true
   dp[16]=dp[16]∨dp[6]=false∨true=true
   dp[19]=dp[19]∨dp[9]=false∨true=true
   （4）面额 c=19c = 19c=19：
   • 检查是否必要：
     • dp[19]=true，说明金额19已可达，面额19是不必要的。跳过，不更新 m 和 dp 数组。
4. 最终结果：
   • 必要的面额有 3 和 10，最小的货币种数 m=2

总结：

该算法通过动态规划和贪心策略，确定了哪些面额是必要的，从而找到与原货币系统等价且货币种数最少的系统。

代码实现：

 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

/**************************************************************** 
 * Description: 2018年提高组第一题  货币系统
 * Author: Alex Li
 * Date: 2024-09-30 19:28:38
 * LastEditTime: 2024-09-30 19:38:55
****************************************************************/
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int MAX_COIN_VALUE = 250; // 最大面值
                  
int main() {
    int T; // 测试数据组数
    cin >> T;
    while (T--) {
        int n; // 货币种数
        cin >> n;
        vector<int> a(n); // 面额数组
        int max_coin = 0; // 最大面值
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            max_coin = max(max_coin, a[i]);
        }
        sort(a.begin(), a.end()); // 将面额排序
        vector<bool> dp(max_coin + 1, false); // dp数组，表示金额是否可达
        dp[0] = true; // 金额0可达
        int m = 0; // 最小货币种数
        for (int i = 0; i < n; ++i) {
            int c = a[i]; // 当前面额
            if (dp[c]) {
                // 如果当前面额可达，则是多余的
                continue;
            } else {
                // 否则，是必要的，更新dp数组
                m++; // 增加必要的货币种数
                for (int j = c; j <= max_coin; ++j) {
                    dp[j] = dp[j] || dp[j - c];
                                 }
            }
        }
        cout << m << endl; // 输出最小的m
    }
    return 0;
}