分配宝藏-j9国际集团直营

1036: 分配宝藏

时间限制: 1000 ms  内存限制: 128 MB
提交: 692  解决: 200
[提交][状态][讨论版]

题目描述

两个寻宝者找到一个宝藏，里面包含着n件物品，每件物品的价值是w[i]。suma代表寻宝者A所获物品的总价值，sumb代表寻宝者B所获物品的总价值，请问怎么分配，能使得|suma - sumb|（即suma与sumb之差的绝对值）最小。

输入

有多组输入数据，第一行为一个数字T，代表有T组输入数据 (0<T<=50)。
接下来为T组数据，每组数据分为两行：
第一行有一个整数n, 表示物品个数，其中0<n<=200.
第二行有n个整数，第i个正数w[i]代表第i件物品的价值，其中0<w[i]<=200.
注意：所有数据均为正整数。

输出

一共T行。
对于每组数据，输出一个整数，表示|suma-sumb|。

样例输入

2
2
2 3
4
1 2 3 4

样例输出

1
0

提示

来源

2014西电ACM校赛现场赛

[提交][状态][讨论版]