大家们，哈忙吧奥利给，冲鸭！

Question

这个东西，谁帮帮我，我代码不太对，想要思路，（简易代码也行）可私O，ᕦ(･ㅂ･)ᕤ
c++
题目描述
2001年9月11日，一场突发的灾难将纽约世界贸易中心大厦夷为平地，Mr. F曾亲眼目睹了这次灾难。为了纪念“9·11”事件，Mr. F决定自己用水晶来搭建一座双塔。 Mr. F有N块水晶，每块水晶有一个高度，他想用这N块水晶搭建两座有同样高度的塔，使他们成为一座双塔，Mr. F可以从这N块水晶中任取M（1≤M≤N）块来搭建。但是他不知道能否使两座塔有同样的高度，也不知道如果能搭建成一座双塔，这座双塔的最大高度是多少。所以他来请你帮忙。 给定水晶的数量N（1≤N≤100）和每块水晶的高度Hi（N块水晶高度的总和不超过2000），你的任务是判断Mr. F能否用这些水晶搭建成一座双塔（两座塔有同样的高度），如果能，则输出所能搭建的双塔的最大高度，否则输出“Impossible”。

输入格式
输入的第一行为一个数N，表示水晶的数量。第二行为N个数，第i个数表示第i个水晶的高度。

输出格式
输出仅包含一行，如果能搭成一座双塔，则输出双塔的最大高度，否则输出一个字符串“Impossible”。

样例一
输入
5
1 3 4 5 2
输出
7
限制与约定
时间限制：
1
s
1s

空间限制：
256
MB
256MB

Answer 1

思路：将问题转化为从 N 个数中选出若干个数，使得这些数的和除以 2 等于所有数的和除以 2。这是一个经典的 0/1 背包问题，可以使用动态规划解决。具体来说，设 dp[i][j] 表示从前 i 个数中选若干个数，使得它们的和为 j 是否可行。状态转移方程为：

dp[i][j] = dp[i-1][j] || dp[i-1][j-a[i]]

其中 a[i] 表示第 i 个数的高度。状态转移方程的含义是不选第 i 个数或选第 i 个数。最终的答案即为最大的 j 使得 dp[N][j] 为 true，即选出的若干个数的和为所有数的和除以 2。

具体实现时需要注意，因为数组中可能存在负数，因此需要将所有数都加上一个正数，使得所有数都变成非负数。同时，根据 0/1 背包问题的特点，可以将 dp 数组压缩成一维，从后往前更新即可。