[每日一题] [NC19158] 失衡天平

题目大意：将一组物品分成两组，每个物品都可以不出现在任何一组。希望两组的重量差异不超过M，最大化总重量。

https://ac.nowcoder.com/acm/problem/19158

基本就是一个背包问题的变体，对于前i个物品，差异为gap时的最大总重量进行dp即可。
转移为(i, gap) -> (i + 1, gap)和(i, gap) -> (i + 1, gap + wt[i + 1])和(i, gap) -> (i + 1, abs(gap - wt[i + 1]))。注意，gap的中间值是可以超过M的，需要给一个比较大的界，比如w1+...+wn。

#define MAXN 105
#define MAXW 20000
#define INF 20000
int N, M;
int wt[MAXN];
int dp[MAXN][MAXW];
int doit() {
  REP(i, N) {
    int w = wt[i];
    if (i == 0) {
      REP(j, MAXW) {
        dp[i][j] = -INF;
      }
      dp[i][0] = 0;
      dp[i][w] = w;
      continue;
    }
    REP(j, MAXW) {
      dp[i][j] = dp[i - 1][j];
    }
    REP(j, MAXW) {
      VI trans = {j + w, abs(j - w)};
      for (int t : trans) {
        if (0 <= t && t < MAXW) {
          dp[i][t] = max(dp[i][t], dp[i - 1][j] + w);
        }
      }
    }
  }
  int ans = 0;
  REP(j, M + 1) {
    ans = max(ans, dp[N - 1][j]);
  }
  return ans;
}
int main(int argc, char* argv[]) {
  read(N);read(M);
  read(wt, N);
  printint(doit());
  return 0;
}