【每日一题】失衡天平

解题思路

一共有 n 个物品，第 i 个物品的重量是 w[i]。可以将物品放在天平的两端，若两端重量相差小于 m，就可取走物品。
求取走的物品的总重量最大为多少？不限操作次数。

dp[i][j] 表示前 i 个物品天平左右相差 j 时的最大重量。
如果不选第 i 个物品，d[i][j] = d[i-1][j]。
如果 dp[i-1][j+w[i]] 是可行的，即 dp[i-1][j+w[i]] != -1，那么在较轻的那端放置第 i 个物品，dp[i][j] = dp[i-1][j+w[i]] + w[i]，此时，该端依然是较轻的那端。
当 j >= a[i] 时，如果 dp[i-1][j-w[i]] 可行，那么在较轻的那端放置第 i 个物品，dp[i][j] = dp[i-1][j-w[i]] + w[i]，此时，该端依然是较轻的那端，或两端相等。
当 j < a[i] 时，如果 dp[i-1][w[i]-j] 可行，那么在较轻的那端放置第 i 个物品，dp[i][j] = dp[i-1][w[i]-j] + w[i]，此时，该端变成较重的那端。
在以上情况中，取 dp[i][j] 的最大值。

最后，取 dp[n] 中差值在 [0,m] 之间的最大值。

C++代码

#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;

const int N = 1e5;

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> w(n+1);
    int sum = 0;
    for(int i=1; i<=n; ++i){
        scanf("%d", &w[i]);
        sum += w[i];
    }

    vector<vector<int>> dp(n+1, vector<int>(N, -1));
    dp[0][0] = 0;
    for(int i=1; i<=n; ++i){
        for(int j=0; j<=sum; ++j){
            dp[i][j] = dp[i-1][j];
            if(dp[i-1][j+w[i]] != -1)
                dp[i][j] = max(dp[i][j], dp[i-1][j+w[i]] + w[i]);
            if(dp[i-1][abs(j-w[i])] != -1)
                dp[i][j] = max(dp[i][j], dp[i-1][abs(j-w[i])] + w[i]);
        }
    }

    int ans = 0;
    for(int j=0; j<=m; ++j){
        ans = max(ans, dp[n][j]);
    }
    printf("%d\n", ans);
    return 0;
}