NOIP2018提高组货币系统详解：从问题分析到最优解法

4个月前 (07-05)比赛题解257

2018NOIP提高组的题目货币系统是NOIP竞赛中考察动态规划和数学思维的典型题目。本文将完整解析题目要求，并通过详细注释的代码展示如何将问题转化为完全背包问题来解决。

一、问题重述

给定一个货币系统(n,a)，求一个等价的货币系统(m,b)，使得m尽可能小。等价的意思是两种货币系统能够表示的金额完全相同。

二、核心算法思想

问题转化为求原货币系统的"基"（即不能被其他面值线性表示的面值）
使用动态规划求解完全背包问题
通过排序优化处理顺序

三、完整代码实现（带详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 105;
const int MAXV = 25005;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        // 排序货币面额（关键步骤1：确保处理顺序正确）
        sort(a.begin(), a.end());
        
        // DP[i]表示金额i能否被表示（关键步骤2：初始化动态规划数组）
        bool dp[MAXV] = {false};
        dp[0] = true;  // 金额0总是可以被表示
        
        int ans = 0;
        int max_val = a.back();  // 最大面额（优化循环边界）
        
        // 核心算法部分（关键步骤3：完全背包思想）
        for (int i = 0; i < n; i++) {
            int val = a[i];
            // 如果当前面额不能被前面的货币表示，则必须保留
            if (!dp[val]) {
                ans++;
                // 完全背包更新（关键步骤4：更新可表示的金额）
                for (int j = val; j <= max_val; j++) {
                    if (dp[j - val]) {
                        dp[j] = true;
                    }
                }
            }
        }
        
        cout << ans << endl;
    }
    return 0;
}