Jam's balance
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2344 Accepted Submission(s): 958
Problem Description
Jim has a balance and N weights. (1≤N≤20)
The balance can only tell whether things on different side are the same weight.
Weights can be put on left side or right side arbitrarily.
Please tell whether the balance can measure an object of weight M.
Input
The first line is a integer T(1≤T≤5) , means T test cases.
For each test case :
The first line is , means the number of weights.
The second line are number, i'th number w i (1≤w i ≤100) means the i'th weight's weight is w i .
The third line is a number . is the weight of the object being measured.
Output
You should output the "YES"or"NO".
Sample Input
1
2
1 4
3
2
4
5
Sample Output
NO
YES
YES
Hint
For the Case 1:Put the 4 weight alone
For the Case 2:Put the 4 weight and 1 weight on both side
Source
BestCoder Round #70
Recommend
hujie | We have carefully selected several similar problems for you: 6361 6360 6359 6358 6357
算法分析：
题意，现在有一个天平，有n个砝码，每个砝码有各自的重量，天平上的两端都可以放置砝码，并且通过天平只能知道两边是否平衡，给出了m组询问，每次询问一个重量，问这些砝码可否被称出来。
因为砝码只有20个，所以我们可以考虑一下枚举子集，枚举出砝码所有可以组成的情况，并且标记一下，然后就可以O(1)O(1)查询了。
还要注意一点就是，比如我我们有两个秤砣：2、8；我们不仅记录2、8、2+8、还要记录8-2这种情况，所以每次再跑一遍， 减去每个的重量标记即可。
二进制枚举解析：点这里
代码实现：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn = 2005;
int a[maxn], vis[2*maxn], n, m, x, t;
int main()
{cin >> t;while(t--){mem(vis,0); cin >> n;for(int i = 0; i < n; i++) cin >> a[i];for(int i = 0; i < (1 << n); i++){int sum = 0;for(int j = 0; j < n; j++){if(i & (1 << j))sum += a[j];}vis[sum] = 1;for(int j = 0; j < n; j++){if(sum - a[j] >= 0)vis[sum-a[j]] = 1;}}cin >> m;for(int i = 0; i < m; i++){cin >> x;if(vis[x]) puts("YES");else puts("NO");}}return 0;
}