【正经题解】货币系统

将a数组从小到大排序
最小的数必须要选，然后利用完全背包的思想，从$a_i$ 到最大值筛选一遍，将可以组成的打上标记
在判断后面的数字时，如果已经被标记过了，就不再选，没有被标记过就标记一下，再筛选一次数(即一次完全背包)

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n,a[N],maxx,ans,vis[25000],f[25000],t;

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        maxx=ans=0;
        scanf("%d",&n);
        for(int i=1;i<=25000;i++) vis[i]=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            maxx=max(maxx,a[i]);
        }
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++)
        {
            if(vis[a[i]]) continue;
            ans++,vis[a[i]]=1;
            for(int k=a[i];k<=maxx;k++)
            {
                if(vis[k-a[i]]) vis[k]=1;
            }
        }
        printf("%d\n",ans);
    }
}