失衡天平

这是一道背包DP，下面我们共同看一下
第一步——状态表示：
f[i][j]:表示走到第i个物品的时候，此时天平两边之差为j，此时所获最大价值为f[i][j]的值
第二步——状态转移方程：
我们走到第i个物品的时候，我们面临着三种选择：
1.不选当前物品
2.选当前物品，将当前物品放到重量较大的那个托盘
3.选择当前物品，将当前物品放到质量较小的那个托盘
通过这三种情况，我们可以得到对应的三种状态转移方程。
即：

1. f[i + 1][j] = f[i][j];
2. f[i + 1][j] = f[i][j + w[i]] + w[i];
3. f[i + 1][j] = f[i][abs(j - w[i])] + w[i];

我们对这三种情况去max就是f[i+1][j]的最大值了
第三步——初始化
f[0][0]=0;
memset(f, -0x3f, sizeof(f));
解释：我们的状态只能由f[0][0] = 0转移而来，其他的都不可以。
因为我们一开始的时候，天平是没有放物品的，同样也没有质量。
举个反例f[0][10] = 0;当i=0的时候，j不能等于非零数，还有，既然j大于0，也就是托盘里放了物品，价值应该是个大于0的数啊，这样很矛盾，同样，要是价值是一个大于0的数，同样不对。

第四步——边界
max{f[n][(0<=j<=m)]}
解释：我们走到第n个物品，当前天平差值小于等于m的情况中的最大的一个就是我们要求的了。
分析就到这里了，下面我们看代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;

int n, m;
int w[N];
int f[N][N * N];

int main() {
  cin >> n >> m;
  int sum = 0;
  for (int i = 1; i <= n; i ++ ) cin >> w[i], sum += w[i];

  memset(f, -0x3f, sizeof f);
  f[0][0] = 0;
  for (int i = 1; i <= n; i ++ )
    for (int j = 0; j <= sum; j ++ ) {
      f[i][j] = f[i - 1][j];
      f[i][j] = max(f[i][j], f[i - 1][abs(j - w[i])] + w[i]);
      f[i][j] = max(f[i][j], f[i - 1][j + w[i]] + w[i]);
    }

  int ans = 0;
  for (int i = 0; i <= m; i ++ )
    ans = max(ans, f[n][i]);

  cout << ans << endl;

  return 0;
}