problem

将个物品分成两堆，使得两堆重量之差不超过m。问两堆重量之和最多是多少。

solution

用表示前i个物品，左边一堆的重量减去右边一堆的重量为j，最大的重量之和。

对于一个物品有放在左边，放在右边，不放三种决策。

对于重量为x的物品
如果放在左边，就有
如果放在右边，就有
如果不放，就有$

最后答案就是

code

/*
* @Author: wxyww
* @Date:   2020-06-10 20:03:10
* @Last Modified time: 2020-06-10 20:06:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 110;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int f[N][N * N * 2];

int py = 10000;

int main() {
    int n = read(),m = read();
    memset(f,-0x3f,sizeof(f));
    f[0][py] = 0;

    for(int i = 1;i <= n;++i) {
        int x = read();
        for(int j = 0;j <= py + py;++j) {
            if(j >= x) f[i][j] = max(f[i - 1][j - x] + x,f[i][j]);
            if(j + x <= py + py) f[i][j] = max(f[i][j],f[i - 1][j + x] + x);
            f[i][j] = max(f[i][j],f[i - 1][j]);
        }
    }
    int ans = 0;
    for(int i = py - m;i <= py + m;++i)
        ans = max(ans,f[n][i]);

    cout<<ans;


    return 0;
}