小M的天平

物品可以放左边也可以放在右边

其实可以看成一个物品可以作为重量也可以作为

那么看成个物品来一次$背包即可

但是这里稍微有点变化,物品的价值可能是负数

那么如果负数也按照我们倒序枚举会有问题,负数应该正序枚举

负数正序枚举能保证状态没有重复使用一个物品

当然如果你用的是二维数组来就不需要分两次了

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int dp[N], a[N], n, m, sum;
int main() {
  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;
}