每日一题 失衡天平 (背包dp)

一.题意

将一组物品分成两组，每个物品都可以不出现在任何一组。希望两组的重量差异不超过M，求最大化总重量。

二.题解

首先明显的背包，不过第二维代表的含义稍微做了点修改， 代表选取前 i 个物品重量差不超过 j 的最大总重量，那么很明显的有:

1. 不选取第 i 个物品:
2. 选取第 i 个物品并放在天平较重的一边 :
3. 选取第 i 个物品并放在天平较轻的一边，同时考虑这个较轻的一边总重量可能会超过另一边，所以需要加上绝对值:

当然这题最重要的就是注意初始化，把 dp 数组初始化为一个很小的数，同时设 ，保证所有状态的 dp 都是由 0 推出。

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ld long double
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;
const int mod=1e9+7;

ll a[N],dp[N][10000];
ll n,m,s,ans=0;

int main(){
    io; cin>>n>>m; s=0;
    for(int i=1;i<=n;i++) cin>>a[i],s+=a[i];
    memset(dp,-inf,sizeof(dp)); dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=s;j++){
            dp[i][j]=dp[i-1][j];
            dp[i][j]=max(dp[i][j],dp[i-1][abs(j-a[i])]+a[i]);
            dp[i][j]=max(dp[i][j],dp[i-1][a[i]+j]+a[i]);
        }
    }
    for(int i=0;i<=m;i++) if(dp[n][i]>ans) ans=dp[n][i];
    cout<<ans;
    return 0;
}