Description:


将一堆正整数分为2组,要求2组的和相差最小。
例如:1 2 3 4 5,将1 2 4分为1组,3 5分为1组,两组和相差1,是所有方案中相差最少的。

Input:


\(1\) 行:一个数 \(N\)\(N\) 为正整数的数量。
\(2 \sim N+1\) 行, \(N\) 个正整数。
( \(N \le 100\) , 所有正整数的和 \(\le 10000\) )

Output:


输出这个最小差

Sample Input:


Sample Output:


题解:


一开始这道题不知道做……

注意到两堆必定有一堆大于 \(\frac{sum}{2}\) ,也必定有一堆小于 \(\frac{sum}{2}\) ,我们不妨考虑小于 \(\frac{sum}{2}\) 的那一堆,让他尽量大就可以了。

然后就是01背包了。背包容量为 \(\frac{sum}{2}\)