思路与算法

按面额递增，已有保留面额能凑出当前面额则删除，否则该面额必须保留，并用完全背包更新至最大原面额的可达金额。

正确性说明

当前最小不可由更小保留面额组成的值，在任何等价系统中都是不可分解的正金额，必须作为面额出现，否则表达式只能用更小可表出金额相加而与不可分解矛盾。反之能由保留面额组成的面额不增加生成金额集合，可删除。因此逐个保留不可分解面额既充分又必要，得到最少种数。

复杂度

每组O(nA+n log n)时间、O(A+n)空间，A<=25000；T组分别初始化可达数组。

易错点

面额可重复；完全背包要正序，不能做每张只用一次的01背包。只需判定原面额能否生成，不必枚举无界总金额。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int &x : a)
            cin >> x;
        sort(a.begin(), a.end());
        vector<unsigned char> dp(a.back() + 1);
        dp[0] = 1;
        int ans = 0;
        for (int v : a)
            if (!dp[v]) {
                ans++;
                for (int j = v; j < (int)dp.size(); j++)
                    dp[j] |= dp[j - v];
            }
        cout << ans << "\n";
    }
}