Description

 终于Alice走出了大魔王的陷阱，可是现在傻傻的她忘了带武器了，这可如何是好???这个时候，一个神秘老人走到她面前答应无偿给她武器，但老人有个条件，需要将所选武器分别放在天平的两端，若天平平衡则可以将天平上的所有武器拿走，还好这个天平锈迹斑斑，只要两端重量相差小于等于m就会保持平衡，Alice傻傻的认为越重的武器越好，求Alice最多能拿走的武器总重量。（不限操作次数）

Solution

 分析了一下问题，情况很多，显然贪心做不了，考虑做 ， 令 为前 个物品取得天平两端相差 的最优策略, 那么有 . 加 是因为当 出现负数时，此时重量大的天平和重量小的天平一侧角色互换.

  那么最终答案就是

Code

#include<bits/stdc++.h>
using namespace std;

const long long inf = 1e18;
const int N = 105 * 100 + 5;

int dp[105][2 * N], a[105];

int main() {
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  memset(dp, -0x3f, sizeof(dp));
  dp[0][0] = 0;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j <= N; j++) {
      dp[i][j] = dp[i - 1][j];
      dp[i][j] = max(dp[i][j], dp[i - 1][abs(j - a[i])] + a[i]);
      dp[i][j] = max(dp[i][j], dp[i - 1][j + a[i]] + a[i]);
    }
  }
  int ans = -1;
  for(int i = 0; i <= m; i++) ans = max(ans, dp[n][i]); 
  cout << ans << "\n";
  return 0;
}