均分算法

来源：百度知道 编辑：UC知道 时间：2024/09/18 06:34:42
给定2N个数，将其均分为两组（每组N个数)，使两组数之和的差的绝对值最小，求这个算法
对于钟云浩大侠回答的一个反例：
1 3 6 8 10 14
均值为7
作差后为
-6 -4 -1 1 3 7
将-1 和 1 所对应的6 8取出，剩下-6 -4 3 7，分组为（-6，7）（-4，3）求和为1，-1；没有为零的数，再次分组（-1，1）求和为0，全部取出，这怎么可能
实际上此算法如果能实现，则数的个数必须满足：N=A*2+B*2的平方+C*2的立方+......

再回钟大侠
就你的例子，用你的方法得到的分组是(6 8 10 ) | ( 1 3 14 )差为6
而更小的分法是（3 8 10）|（1 6 14）差为0

(1) 求2N个数的均值,分别求2N个数与均值的差,这些差组成了新的2N个数,
问题就化为了:在2N个数中找N个数,它们的和为零或最接近零
(2)在2N个数中找等于零的数,取出. 如果取出的数已经有N个了,则问题已解决.如果不到N个,则继续下一步
(3)将剩余的数,由小到大排列,然后分组:(最小,最大),(第二小,第二大),(第三小,第三大),...
将每组求和,这些和又构成了一个新数组
在这数组中找等于零的数,取出. 如果到目前为止,原始数组相应被取出数的已经达到或超过了N个,,则问题已解决.
(比如,某个"和"被取出,则对应的分组中的两个数就被取出了)
如果不到N个,则继续下一步
(4)将剩余的"和",看作(3)中开始的"剩余的数",重复步骤(3)
...

回答楼主:
原数组:1,3,6,8,10,14
(A)算均值--记为P:7, 求差:-6,-4,-1,1,3,7
(B)找"差"=0,没有,
取出:没有,
剩余"差"数组:-6,-4,-1,1,3,7
剩余原数组:1,3,6,8,10,14
(C)将剩余"差"数组,由小到大排列,然后分组:(-6,7),(-4,3),(-1,1)
每组求和,新的"和"数组:1,-1,0
找"和"=0,有一个
取出,"和"数组中:一个0; "差"数组中:(-1,1); 原数组中:6,8
剩余"和"数组:1,-1
剩余"差"数组:(-6,7),(-4,3)
剩余原数组:1,3,10,14
(D)按我前面的陈述,接下来,是用剩余"和"数组,求新的"差"数组,那么,就得到:
新的"差"数组:0, 由小到大排列,然后分组:0 (已经无组要分)
每组求和(只有一组),