失衡天平

题目描述：

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

输入描述：

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

输出描述：

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

示例：

5 4
1 5 61 65 100

132

思路：

观察数据的范围 ，这个范围的数据，极有可能是DP来做的，当时看了很久似乎并没没有思路 ，动态规划。知道是动态规划之后我们最主要的就是要明白状态表示，和动态转移方程。

类似于背包问题，我们用 $dp\left[i\right]\left[j\right]dp[i][j]$dp[i][j] 表示从前 i 个当中选，差值不大于 j 的最大重量 。

有了状态表示，我们怎么找到转移方程。我们可以发现 $dp\left[i\right]\left[j\right]dp[i][j]$dp[i][j] 当中的部分一定包含了了 $dp[i-1]\left[j\right]dp[i-1][j]$dp[i−1][j] ,那么我们剩下要考虑的就是 $a\left[i\right]a[i]$a[i] 这件武器能不能加入 到$dp\left[i\right]\left[j\right]dp[i][j]$dp[i][j] 方案中。能加入到$dp\left[i\right]\left[j\right]dp[i][j]$dp[i][j] 方案中的那么 差值一定是 不超过 $a\left[i\right]+ja[i]+j$a[i]+j 或者$abs(j-a[i\left]\right)abs(j-a[i])$abs(j−a[i]) 当中最大那个。

那么就有状态转移方程：

for(int i = 1 ; i <= n ;++i){
        for(int j = 0 ; j <= cnt ; ++j){
            dp[i][j] = dp[i-1][j];
            int tmp = max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])]);
            dp[i][j] = max(dp[i][j],tmp+a[i]);
        }
    }

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105];
int dp[110][110005];//前i个差距为m的最大值
int main(){
    int n,m;
    cin>>n>>m;
    int cnt = 0;
    for(int i = 1 ;i <= n ; ++i ){
        cin>>a[i];
        cnt += a[i];
    }
    memset(dp,-0x3f,sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1 ; i <= n ;++i){
        for(int j = 0 ; j <= cnt ; ++j){
            dp[i][j] = dp[i-1][j];
            int tmp = max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])]);
            dp[i][j] = max(dp[i][j],tmp+a[i]);
        }
    }
    int ans = 0;
    for(int i = 0 ; i <= m ;++i){
        ans = max(ans,dp[n][i]);
    }
    cout<<ans<<endl;
}