数集划分问题
之前发过一个类似帖子,但是还是没找到最优的算法
具体需求如下:
将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一组
只用在处理的过程中记录下来每次操作就行了