小M和天平

小M和天平

能称得给定的质量，大致有两种情况，
一、给定的石子直接组合可以得到物品的质量，这就可以通过背包来直接得到了。

二、（一些石子 + 物品） = （另一些石子），也就是能够从石子中挑出两堆，这两堆的差值为我们所需称量的。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

int dp[N], a[N], n, m, sum;

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  while (scanf("%d", &n) != EOF) {
    memset(dp, 0, sizeof dp);
    sum = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      sum += a[i];
    }
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {//01背包，如何直接凑得我们想要的值。
      for (int j = sum; j >= a[i]; j--) {
        dp[j] |= dp[j - a[i]];
      }
    }
    for (int i = 1; i <= n; i++) {
    //01背包, 从后往前做一个01背包删除a[i]，通过得到一个差值，来凑得我们想要的值。
      for (int j = 1; j <= sum - a[i]; j++) {
        dp[j] |= dp[j + a[i]];
      }
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
      int x;
      scanf("%d", &x);
      puts(x <= sum && dp[x] ? "YES" : "NO");
    }
  }
  return 0;
}