题目链接：https://www.luogu.org/problem/P5020

这道题目是一道模拟题，但是又有一点多重背包的思想在里面。

首先我们定义一个 vis[i] 来表示和为 i 的情况在之前有没有出现过，

一开始当然所有的 vis[i] （除了 vis[0] ）都为 false ，只有 vis[0] 为 true ，

然后对于每一个 i 来说，我们从 a[i] 到 maxa （最大值）去判断 vis[j-a[i]] 是否为 true ，

如果 vis[j-a[i]] 为 true，那么 vis[j] 理应为 true ，所以需要将 vis[j] 置为 true ，

但是在置为 true 之前还需要判断一下 vis[j] 是不是已经为 true 了，

如果 vis[j] 已经为 true 了，那么就是说我这一步置不置为 true 没有必要了，

如果对于所有的 j ，我置不置为 true 都没有必要了，那么我就没有必要要这个 a[i] 了。

当然我们首先得给所有的 a[i] 从小到大排序，因为这里涉及到了一丢丢贪心的思想，那就是：

小的永远比大的重要~

依据这样的思想，实现代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 110, maxa = 25010;

int T, n, m, a[maxn];

bool vis[maxa];

int main() {

	scanf("%d", &T);

	while (T --) {

		scanf("%d", &n);

		memset(vis, 0, sizeof(vis));

		for (int i = 0; i < n; i ++) scanf("%d", a+i);

		sort(a, a+n);

		vis[0] = true;

		m = 0;

		for (int i = 0; i < n; i ++) {

			bool flag = false;

			for (int j = a[i]; j < maxa; j ++) {

				if (vis[ j - a[i] ]) {

					if (!vis[j]) {

						flag = true;

						vis[j] = true;

					}

				}

			}

			if (flag) m ++;

		}

		printf("%d\n", m);

	}

	return 0;

}