算法2

(暴力枚举) $O(n^2)$

这个题目的思路就是直接把原来的数组从小到大排序一下 然后从最小的跑背包 如果后面大的能够被前面小的面额组成
的话 那么他根本没有存在的意义 直接跳过就好了 最后答案就是原来的数组个数减去没用的数

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int a[maxn];
int f[maxn];

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