Unbalance balance (dynamic programming, DP)

Title Description

finally Alice Out of the trap of the demon king , But now she forgot to bring her weapon , What should I do ??? This is the time , A mysterious old man came up to her and promised to give her weapons for free , But the old man has one condition , You need to put the selected weapons on both ends of the scale , If the balance is balanced, all weapons on the balance can be taken away , Fortunately, the scale is rusty , As long as the weight difference between the two ends is less than or equal to m Will maintain balance ,Alice Foolishly think that the heavier the weapon, the better , seek Alice The maximum total weight of weapons that can be taken .（ Unlimited number of operations ）

Input description :

 first line 2 It's an integer  n, m;
 The second line n It's an integer x, respectively n The weight of a weapon .
1 <= n <= 100; 0 <= m <= 100; 1 <= x <= 100;

Output description :

 An integer , Express Alice The maximum total weight of weapons that can be taken .

Example 1

Input

5 4
1 5 61 65 100

Output

132

Example 2

Input

5 0
10 20 30 40 100

Output

200

analysis ：

dp[i][j] , In the i The difference between the two sides of the balance is j Maximum weight of

When not selected dp[i][j] = max(dp[i][j], dp[i - 1][j]);

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

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

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
int n, m;
int a[110];
int dp[110][10010];
int sum = 0;
const int inf = 0x3f3f3f3f;
int main()
{
	cin >> n >> m;
	memset(dp, -inf, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= sum; j++) {
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);
			dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i - 1][j] + a[i]);
			dp[i][abs(j - a[i])] = max(dp[i][abs(j - a[i])], dp[i - 1][j] + a[i]);
		}
	}
	int ans = 0;
	for (int i = 0; i <= m; i++) ans = max(ans, dp[n][i]);
	cout << ans;
	return 0;
}