题解 | #失衡天平#

失衡天平

首先应该想到进行多次操作可以归结到一次操作上,对于一个状态,我们只需要关心对应差值的最大质量,因此具有了最优最优子结构,那么我们考虑dp 设f[i][j]为考虑前i件物品,差值为j的最大重量那么对于每一个物品,我们有三种情况

1. 不选该物品, f[i][j] = max(f[i - 1][j], f[i][j]);
2. 选该物品,且放在质量较轻的一侧 f[i][j] = max(f[i][j], f[i - 1][j - a[i]] + a[i]);
3. 选,且放在质量较重的一侧 f[i][j] = max(f[i][j], f[i - 1][j + a[i]] + a[i]);

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 110, M = 2e4 + 10, base = 10000;
int f[N][M], n, a[N], m;
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	memset(f, -0x3f, sizeof f);
	f[0][base] = 0;
	for(int i = 1; i <= n; i ++)
		for(int j = 0; j < M; j ++)
		{
			f[i][j] = max(f[i][j], f[i - 1][j]);//不选第i件物品
			if(j - a[i] >= 0) f[i][j] = max(f[i][j], f[i - 1][j - a[i]] + a[i]); //放在质量小的那一边
			if(j + a[i] < M) f[i][j] = max(f[i][j], f[i - 1][j + a[i]] + a[i]); // 放在质量大的那一边
		}
	int res = 0;
	for(int i = base - m; i <= base + m; i ++)
		res = max(res, f[n][i]);
	cout << res << endl;	
	return 0;
}