货币系统 https://www.acwing.com/problem/content/534/

给定不同面额的货币，每个货币可以选无限个，要求求得该组货币的最简组合，eg：
3，6，10，19 中6可以用两个三表示，19可以用3和10表示，故可以删去6和19
得到3，10为最优解

设原货币组为a，最优解为b，对于最优解
1.a1,a2 ... an一定可以被表示出来
2.在最优解里，b1,b2 ... bm 一定都是从a1,a2 .. an种选择
    假设有一个bi与a中任何一个元素不想等，但bi一定可以由a表示
    例：bi = a1 + a2 + a3
    而a一定可以用b表示，则bi可以由b表示出来，则bi不满足最优解
3.b1,b2 ... bm一定不能被其他bi表示出来

1.从小到大排序
2.从小往大看，看ai能不能有a1~ai-1里的数表示出来
    可以被表示，则不选该数
    不可被表示，必须选该数

相当于用前一个货币系统的方式，求出f
其中f[x]为0时，该x不可由前面数得到，x就是最优解中的数字

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

const int N = 110, M = 25010;
int T, n, f[M], a[N];

int main()
{
    cin >> T;
    while ( T -- )
    {
        cin >> n;
        memset(f, 0, sizeof f);
        for ( int i = 0; i < n; i ++ ) cin >> a[i];
        sort(a, a + n);
        f[0] = 1;
        int res = 0;
        for ( int i = 0; i < n; i ++ )
        {
            if ( !f[a[i]] ) res ++;
            for ( int j = a[i]; j <= a[n - 1]; j ++ ) 
                f[j] += f[j - a[i]];
        }
        cout << res << endl;
    }
    return 0;
}