数集划分问题

Question

之前发过一个类似帖子，但是还是没找到最优的算法具体需求如下：
将N个整数的集合分成2堆，使这2堆的差值最小，求这2堆集合（S1，S2），2堆集合长度不要求一样。或则问题可以转换成这样，最小差值已经确定为MIN，即求sum（S1）- sum（S2）= MIN 的2堆集合。

Answer 1

看过一篇类似的帖子，但是也只是求出2堆集合的最小值，并没有对2堆集合具体做划分1 将N个数排序，称集合A2 取出A中最大两个数a,b，相减得c3 a,b出集合，c进集合4 若A只有一个元素跳出，否则跳到25 A中最后一个元素就是2堆集合的最小差值

Answer 2

我觉得三楼算法还是可以找两个集合记为A，B
同时记录两个减法运算的操作数，被减数归为A，减数归为B，差（非负数）仍属于A。而再与其“差”进行减法运算的数就归为B，其差亦归为B，依此类推~

Answer 3

我有一个想法不知道是否可行
集合为A
1.堆a 和b
2.找A最大的一个数放如a,次大的放入b。
3.假设|sum(a)-sum(b)| = c,找到与c接近的的数放入 a,b较小的堆里面
4.循环3知道 A里面都被拿出来。

Answer 4

打字说好麻烦
还是模拟下步骤，好懂些
如1   2   3   4
a   b   c   d
1   1    2
a   d-c  b
1   1
a   b-d+c
0
b-d+c-a
根据符号可知
bc一组， ad一组
只用在处理的过程中记录下来每次操作就行了

Answer 5

perfect有图有真相，很好～