代码

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

const int bagg = 1000;
const int numm = 100005;
using namespace std;

int	 t, n;
int	 now[bagg];
int	 f[numm];
int	 ans;
int	 cup[numm];
void bag() {
	//  printf("%d",f[now[1]*2]);
	for (int i = 1; i <= n; i++) {
		if (f[now[i]]) {
			ans++;
			continue;
		}
		for (int j = now[i]; j <= now[n]; j++) {
			f[j] = f[j - now[i]] | f[j];
		}
	}
}
int main() {
	scanf("%d", &t);
	for (int i = 1; i <= t; i++) {
		scanf("%d", &n);
		ans = 0;
		memset(f, 0, sizeof(f));
		memset(cup, 0, sizeof(cup));
		for (int j = 1; j <= n; j++) {
			scanf("%d", &now[j]); 
		}
        f[0]=1;
		sort(now + 1, now + 1 + n);
		// f[now[1]] = true;
		bag();
		//if(!ans) printf("%d\n",n);
		printf("%d\n", n - ans);
	}
	return 0;
}
/*20
3
170 962 891
3
162 4 379
3
250 615 750
3
570 46 299
3
415 634 110
3
564 297 987
3
256 396 992
3
424 480 234
3
264 940 380
3
265 165 224
3
640 68 136
3
933 602 427
3
184 736 648
3
894 103 344
3
851 740 370
3
622 28 231
3
822 264 895
3
250 1000 500
3
679 469 938
3
187 564 282
*/

评测结果