2018年NOIP货币系统解题报告（洛谷P5020）：动态规划与完全背包的巧妙应用
一、题目解读
2018年NOIP货币系统问题（洛谷P5020）要求给定一组货币面额，判断是否存在一种组合方式，使得所有不超过最大面额的金额都能被表示。例如，若面额集合为{1,3,5}，则金额1~8均可被表示，而{2,3}无法表示金额5。题目核心在于寻找最少的面额数量，以满足所有金额的可达性。
二、解题思路
采用动态规划（Dynamic Programming）结合完全背包的思想。关键在于两点：面额排序与状态转移。
1. 排序优化：对货币面额升序排序，确保小面额优先参与组合，降低后续计算复杂度。
2. 完全背包模型：将每个面额视为可无限使用的“物品”，目标为填充金额区间[0, max_val]。
3. 状态定义：dp[i]表示金额i是否可被面额组合表示。初始状态dp[0]=true（金额0无需面额）。
4. 状态转移方程：若当前面额val未被表示（!dp[val]），则必须保留该面额，并通过dp[j] = dp[j-val] || dp[j]更新后续金额的可表示性。
三、解题步骤
1. 输入与预处理：读取面额数量n及集合a，排序a。
2. 初始化dp数组：仅dp[0]=true，其余为false。
3. 迭代面额更新dp：
若dp[val]为false，说明val无法被之前面额表示，必须保留该面额，并更新dp[val~max_val]。
利用完全背包逻辑：for j=val to max_val, dp[j] |= dp[j-val]。
4. 统计答案：累计所有未被表示的面额数量（即新增的面额）。
5. 输出结果：最少面额数。
四、代码与注释
#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());
// 2. dp[i]：金额i是否可被表示
bool dp[MAXV] = {false};
dp[0] = true; // 金额0总能被表示
int ans = 0; // 最少面额数
int max_val = a.back(); // 最大面额值
for (int i = 0; i < n; i++) {
int val = a[i];
// 3. 若val无法被当前面额组合表示，必须保留
if (!dp[val]) {
ans++; // 新增面额
// 4. 完全背包更新：val可无限使用，填充后续金额
for (int j = val; j <= max_val; j++) {
if (dp[j - val]) { // 若j-val可被表示，则j也可被表示
dp[j] = true;
}
}
}
}
cout << ans << endl; // 输出结果
}
return 0;
}五、总结
本解法巧妙利用排序与完全背包模型，将货币系统问题转化为动态规划中的“物品组合可达性”问题。核心在于：保留无法被组合表示的面额，并利用其填充后续金额。算法时间复杂度为O(n*max_val)，通过排序优化避免了重复计算。对于类似涉及组合可达性的问题，可借鉴此思路，结合状态压缩或记忆化搜索进一步优化。
原创内容 转载请注明出处
