失衡天平

思路

首先注意到数据范围只有100，所以我这里选择二维dp

通过证明不难发现，能带走的最多的重量，无论是分几次拿走的，一定可以变成一次能拿走的方案。

表示前 i 个武器放入天平的两端差距为 j 的天平上武器重量的和的最大值

所以状态转移方程就是

for(int i = 1 ; i <= n ;++i){//1到n个数
        for(int j = 0 ; j <= cnt ; ++j){//cnt表示能得到的最大重量
            dp[i][j] = dp[i-1][j];
            int tmp = max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])]);//i-1个数分别向左天平和右天平加数
            dp[i][j] = max(dp[i][j],tmp+a[i]);//更新最大值
        }
    }

看转移方程应该就很好理解了，那我就给代码了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
    ll 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;
}
int a[105];
int dp[110][110005];//前i个差距为m的最大值
int 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;
}