失衡天平（dp）

https://ac.nowcoder.com/acm/problem/19158

题意：
有一个天平，每次只要放上去的东西重量相差不超过m即可拿走，问最多能带走物品的重量为多少？

分析：

在这个问题中，我们关心的只有两边的差值，如果两边差值小于等于m，那么天平就是等价的，那么对于当前差值j，你再加一件物品后的状态，只与之前的差值j有关，差值变成j+w[i],或abs(j-w[i])，因此对于当前a[i]物品，假定放进去最优解是差值为j的时候，那么这个最优解一定是从上一个状态的其中一个差值j转化过来的，我们需要从这过程中取最优情况，因此用dp进行解决。

dp[i][j]：表示前i个物品差值为j的最大重量。

转移状态： 不取当前物品： dp[i][j]=max(dp[i][j],dp[i-1][j])
取当前物品放在较重一侧： dp[i][j]=max(dp[i][j],dp[i-1][j+a[i]]+a[i])
取当前物品放在较轻一侧： dp[i][j]=max(dp[i][j],dp[i-1][abs(j-a[i])]+a[i])

最后得到 dp[n][j] 差值为j的前n个物品的最大重量
枚举所有j中取最大值即为最终答案。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m,i,j;
int a[105];
int dp[105][10005];//第i个物品差值为j的最大容量
int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    memset(dp,-1,sizeof(dp));
    dp[0][0]=0;
    for(i=1;i<=n;i++){
        for(j=0;j<=10001;j++){
            if(dp[i-1][j]!=-1)              dp[i][j]=max(dp[i][j],dp[i-1][j]);//不取，保留上状态
            if(dp[i-1][j+a[i]]!=-1)         dp[i][j]=max(dp[i][j],dp[i-1][j+a[i]]+a[i]); //取了放重的一边
            if(dp[i-1][abs(j-a[i])]!=-1)    dp[i][j]=max(dp[i][j],dp[i-1][abs(j-a[i])]+a[i]);//取了放轻的一边
        }
    }
    int ans=0;
    for(i=0;i<=m;i++){
        ans=max(dp[n][i],ans);
    }
    printf("%d",ans);
}