题目描述

数据范围

1≤n≤100
,
1≤a[i]≤25000,
1≤T≤20

样例

输入样例：

2 
4 
3 19 10 6 
5 
11 29 13 19 17 

输出样例：

2
5

算法1

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int ans;
int n, m, a[N], f[N];
int main(){
    int T;
    cin >> T;
    while(T --){
        cin >> n;
        ans = n;
        memset(a, 0, sizeof(a));
        memset(f, 0, sizeof(f));
        for(int i = 1;i <= n;i ++) cin >> a[i];
        sort(a + 1, a + n + 1);
        f[0] = 1;
        for(int i = 1;i <= n;i ++){
            if(f[a[i]]){
                ans --;
                continue;
            }
            for(int j = a[i];j <= a[n];j ++){
                f[j] |= f[j - a[i]];        
            }
        }
        cout << ans << endl;
    }
    return 0;
}