牛客 每日一题 失衡天平 dp

失衡天平

题目链接

题意

给一个数组（代表一个东西的重量），每次选一些东西出来分成两堆，两堆的重量的差不能超过m，问最多可以获得的重量是多少。
（可以选多次，但一个东西只能选一次）

题解。

被他可以选多次忽悠了。
例如样例给的：
5 4
1 5 61 65 100
第一次选 1 5
第二次选 61 65
答案就是132.
但是选多次跟选一次是一样的。因为 可以选1 + 65 5 + 61.
这样的话，就dp
dp[i][j]代表 前i个分成两组，两边的差的绝对值为j的最大重量和。
于是遍历到当前i点的时候ai可以放到左边也可以放到右边。
所以状态转移：

dp[i][j + a[i]] = max(dp[i][j + a[i]],dp[i - 1][j] + a[i]);
dp[i][j - a[i]] = max(dp[i][j - a[i]],dp[i - 1][j] + a[i]);

代码:

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};
int lb(int x){
   return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 105;
int a[maxn];
int dp[maxn][20005];
int main()
{
   
	int n,m;
	scanf("%d%d",&n,&m);
	for (int i= 1 ; i <= n; i ++ )
		scanf("%d",&a[i]);
	for (int i = 0; i<= n; i ++ )
	{
   
		for (int  j= 0; j <= 20000; j ++ )
		{
   
			dp[i][j] = -inf;
		}
	}
	dp[0][10000] = 0;
	for (int i =1 ; i <= n; i ++ )
	{
   
		for (int j = 0; j <= 20000; j ++ )
		{
   
			dp[i][j] = max(dp[i][j],dp[i - 1][j]);
			if(j + a[i] <= 20000)
				dp[i][j + a[i]] = max(dp[i][j + a[i]],dp[i - 1][j] + a[i]);
			if(j - a[i] >= 0)
				dp[i][j - a[i]] = max(dp[i][j - a[i]],dp[i - 1][j] + a[i]);
		}
	}
	int ans =0 ;
	for (int i = 0; i <= m; i ++ )
	{
   
		// printf("%d %d\n",dp[n][10000 + i],dp[n][10000 - i]);
		ans = max(ans,dp[n][10000 + i]);
		ans = max(ans,dp[n][10000 - i]);
	}
	printf("%d\n",ans);

}