数集划分有关问题 两集合求最小差值

数集划分问题 两集合求最小差值

提问：

将N个整数的集合分成2堆，使这2堆的差值最小，求这2堆集合（S1，S2），2堆集合长度不要求一样。
或则问题可以转换成这样，最小差值已经确定为MIN，即求sum（S1）- sum（S2）= MIN 的2堆集合。

 

回答：

看过一篇类似的帖子，但是也只是求出2堆集合的最小值，并没有对2堆集合具体做划分

1 将N个数排序，称集合A

2 取出A中最大两个数a,b，相减得c

3 a,b出集合，c进集合

4 若A只有一个元素跳出，否则跳到2

5 A中最后一个元素就是2堆集合的最小差值

 

如何确定两个集合？
两个集合记为A，B
同时记录两个减法运算的操作数，被减数归为A，减数归为B，差（非负数）仍属于A。而再与其“差”进行减法运算的数就归为B，其差亦归为B，依此类推~