欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1036. -- 分配宝藏

1036: 分配宝藏

时间限制: 1 Sec  内存限制: 128 MB
提交: 381  解决: 118
[提交][状态][讨论版]

题目描述

两个寻宝者找到一个宝藏,里面包含着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

提示

来源

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