链接：https://ac.nowcoder.com/acm/problem/19158
来源：牛客网

题目描述

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

输入描述: 

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

输出描述: 

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

题型：

动态规划--01背包

思路：

1.明确总问题：求最多能拿走的武器总重量-->求n个物品中选取若干个物品，使得天平两端总重量差值小于m的最大总重量。
2.明确子问题：求前i个物品中选取若干个物品，使得天平两端总重量差值为j的最大总重量-->考虑01背包
3.明确dp含义：设dp[i][j]为前i个物品中选取若干个物品，使得天平两端总重量差值为j的最大总重量。所以，如果选到了i个物品，其状态只有两种可能，即前一个物品选/不选，如果前一个物品不选，那么dp[i][j]=dp[i-1][j]
如果前一个物品选，那么dp[i][j]=max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])])+a[i]（01背包）;
4.明确状态转移方程：dp[i][j]=max(dp[i-1][j],max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])])+a[i]);（对于j-a[i]使用abs()是因为可能会出现负数，如果差值出现负数，那么相当于第i-1个物品的位置换到另一边）
5.明确初始化：dp[0][0]=0，其他格子全为-INF
6.明确i,j范围：i:1~n    j:0~sum（注意不是1~sum,0也要算的）
7.明确答案：为max(dp[n][i])（0<=i<=m）（注意i从0开始，到m结束）

代码： 

#include<bits/stdc++.h>
using namespace std;
int a[120],dp[120][22000];
int main() {
	int n,m,sum=0;
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) {
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	memset(dp,-0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=1; i<=n; i++) {
		for(int j=0; j<=sum; j++) {
			dp[i][j]=max(dp[i-1][j],max(dp[i-1][abs(j-a[i])],dp[i-1][j+a[i]])+a[i]);
		}
	}
	int ans=0;
	for(int i=0; i<=m; i++) {
		ans=max(ans,dp[n][i]);
	}
	printf("%d\n",ans);
	return 0;
}