Question

一道编程题 求算法思路.

给出n(2<=n<=20)个数 每个数很大 在(100W-400W)之间吧
现在要求从中选出一些数（可以不选）分别放到2个集合里面 使这2个集合里面数的总和相等,并要求这2个集合中数的总和尽量大.
问满足条件的集合中的数的总和为多少?
比如有5个数分别是 1,2,3,4,5
那么应从中选出3,4为一个集合 2,5为一个集合 这样他们的总和相等（都为7）.
结果就是7

怎么做啊？
说说思路就行啦
谢谢
。。。
必然超时吧

Answer 1

因为n比较小，此题最优的解法是双向搜索
做法如下（n=20)：
枚举前十个数的放入集合的放法，共3^10种，以两个集合的元素差为key，两个集合的元素和为value，存入哈希表
枚举后十个数的放入集合的放法，以两个集合的元素差为key，查哈希表，这样能查到对应的前十个数的分配方法，就知道总和了
这是最优解法，复杂度为3^(n/2)
这题还有一种经典的动态规划的解法，叫“双塔问题”，复杂度为w*n，w为所有数的总和

Answer 2

排序是必然的也是从大到小好了
然后最大的数去加第3大的数(和第2大的加必然无解),得出A,第2大的去和第4大的加,得出B,如果A>B则设置A=最大的加第4大的(同时要判断下第2大加第3大是否比他大,依次类推),如果A<B则B=第2大加第5大(如果第2的找完了从第3开始),A=B的换那就是答案了(保留)
楼上的算法也可行,就是工程量大了,使用穷举法,计算量大,而且他还有一个漏洞第一或第2循环中的两个数相加并没有考虑

Answer 3

设置数组存N个100W-400W之间的数，设置循环使数组中的数从大到小排序；
设置第一个循环，按排列好的顺序从N个数组中选出从X（1<=X=<N）个数相加；
设置第二个循环，从N-X个数中选出Y（1<=Y<=N-X）个数相加；
判断二者和是否相等，相等则输出总和数。