代码

#include<cstdio> 
#include<cstring>
#include<algorithm>
using namespace std;
long long f[25001],c[10002];
int main()
{
	long long n,ans;
	int t;
	scanf("%d",&t);
	while(t--)
	{
		memset(f,0,sizeof(f));
		scanf("%lld",&n);ans=n;
		for(long long i=1;i<=n;i++)
			scanf("%lld",&c[i]);
		sort(c+1,c+n+1);
		f[0]=1;
		for(int i=1;i<=n;i++)
		{
			if(f[c[i]])
			{
				ans--;
				continue;
			}
			for(int j=c[i];j<=c[n];j++)
				f[j]|=f[j-c[i]];
			
		}
		printf("%lld\n",ans);
	}
	return 0;
}

评测结果