玄关求条

#include<bits/stdc++.h>

using namespace std;

/**
 * 非负数组nums中，子序列累加和不超过t，但是最接近t的累加和是多少
 * 01背包问题(子集累加和尽量接近t) + 空间压缩
 */
int solve(vector<int> &nums, int target) {
	vector<int> dp(target + 1, 0);
	for (int num: nums) {//for(int num=0;num<nums.size();num++)
		for (int j = target; j >= num; j--) {
			// dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
			dp[j] = max(dp[j], dp[j - num] + num);
		}
	}
	return dp[target];
}

int lastStoneWeightII(vector<int> &nums) {
	int sum = 0;
	for (int num: nums) {
		sum += num;
	}
	/**
	 * nums中随意选择数字
	 * 累加和一定要 <= sum / 2
	 * 又尽量接近
	 */
	int nearSum = solve(nums, sum / 2);
	return (sum - nearSum) - nearSum;
}

int main() {
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
//		cin >> nums[i];
		scanf("%d",&nums[i]);
	}

	int result = lastStoneWeightII(nums);
	cout << result << endl;

	return 0;
}