题解 | #失衡天平#

失衡天平

题目描述

终于Alice走出了大魔王的陷阱，可是现在傻傻的她忘了带武器了，这可如何是好???这个时候，一个神秘老人走到她面前答应无偿给她武器，但老人有个条件，需要将所选武器分别放在天平的两端，若天平平衡则可以将天平上的所有武器拿走，还好这个天平锈迹斑斑，只要两端重量相差小于等于m就会保持平衡，Alice傻傻的认为越重的武器越好，求Alice最多能拿走的武器总重量。（不限操作次数）

输入描述

第一行2个整数 n, m; 第二行n个整数x，分别表示n件武器的重量。 1 <= n <= 100; 0 <= m <= 100; 1 <= x <= 100;

输出描述

一个整数，表示Alice最多能拿走的武器总重量。

解析

状态表示

f[i][j]代表将前i个武器分成两组，两边的差的绝对值为j的最大重量和。

状态计算

对于a[i]，Alice有三种操作：

①不取a[i]

②取a[i]，放在天平左边

③取a[i]，放在天平右边

所以，状态转移方程为：f[i][j] = max{f[i - 1][abs(j- a[i])] + a[i],f[i - 1][j + a[i]] + a[i],f[i - 1][j])

代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1e4 + 100;
int n,m,a[110],ans = 0,f[110][N];

int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> a[i];
    //f[i][j]代表 前i个分成两组，两边的差的绝对值为j的最大重量和。
    memset(f,-0x3f,sizeof f);
    f[0][0] = 0;
    for(int i = 1;i <= n;i ++){
        for(int j = 0;j <= N;j ++){
            f[i][j] = f[i - 1][j];//不取a[i]
            f[i][j] = max(f[i][j],f[i - 1][abs(j - a[i])] + a[i]);//取a[i]，放左边
            f[i][j] = max(f[i][j],f[i - 1][abs(j + a[i])] + a[i]);//取a[i]，放右边
        }
    }
    for(int i = 0;i <= m;i ++) ans = max(ans,f[n][i]);
    cout << ans << '\n';
    return 0;
}