日期:2014-05-20  浏览次数:20645 次

数集划分问题
之前发过一个类似帖子,但是还是没找到最优的算法

具体需求如下:
将N个整数的集合分成2堆,使这2堆的差值最小,求这2堆集合(S1,S2),2堆集合长度不要求一样。

或则问题可以转换成这样,最小差值已经确定为MIN,即求sum(S1)- sum(S2)= MIN 的2堆集合。

------解决方案--------------------
我觉得三楼算法还是可以找

两个集合记为A,B
同时记录两个减法运算的操作数,被减数归为A,减数归为B,差(非负数)仍属于A。而再与其“差”进行减法运算的数就归为B,其差亦归为B,依此类推~
------解决方案--------------------
打字说好麻烦
还是模拟下步骤,好懂些


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一组
只用在处理的过程中记录下来每次操作就行了