方法：完全背包求方案数

思路：首先最小面值的货币必不可能被凑出，所以最小面值的货币必须得留下，初始化所有可以直接由最小面值的货币凑成的货币。
（记录一个vis）使用完全背包的思想去遍历后续的货币是否已经被凑出,如果无法获得，则ans++，将该种货币标记

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=3e4+10;
int n;
int a[105],vis[INF];
int32_t main(){
    int T;
    cin>>T;
    while(T--){
        memset(vis,0,sizeof(vis));
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        //初始化标记数组，只需要初始化到a[n]/a[1]即可
        for(int i=1;i<=a[n]/a[1];i++) vis[i*a[1]]=1;
        int ans=1;
        for(int i=1;i<=n;i++){
            //该种面值的货币已经被凑出则continue，否则ans++
            if(vis[a[i]]==1) continue;
            ans++;
            vis[a[i]]=1;
            //完全背包，将后续可以由该种面值凑出来的货币全部标记上
            for(int j=a[i]+1;j<=a[n];j++){
                if(vis[j]==0&&vis[j-a[i]]==1){
                    vis[j]=1;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}