失衡天平

这道题其实就是双塔问题。

每个物品有三种选择：放天平左边，放天平右边，不要这个物品。 代表前i个元素天平左右相差（左-右）的时候最大的重量是多少。如果放天平左边，就应该由转移来，如果放在天平右边就由转移来，不选则由转移来。
注意：左-右可能为负数，所以要对数轴进行一个平移。

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
#define pb(x) push_back(x)
#define lowbit(x) x & -x
I int read() {
    int s = 0 , w = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
    while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
    return s * w;
}

const int N = 105;
int a[105];
int dp[110][110005];
signed main() {
    int n = read() , m  =read();
    int cnt = 0;
    for(int i = 1 ;i <= n ; ++i ){
        a[i] = read();
        cnt += a[i];
    }
    memset(dp , -0x3f , sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1 ; i <= n ;++i){
        for(int j = 0 ; j <= cnt ; ++j){
            dp[i][j] = dp[i-1][j];
            int tmp = max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])]);
            dp[i][j] = max(dp[i][j],tmp+a[i]);
        }
    }
    int ans = 0;
    for(int i = 0 ; i <= m ;++i){
        ans = max(ans,dp[n][i]);
    }
    cout << ans << endl;

    return 0;
}