对于一个算法题的思考．

wysilly

精华帖的一个思考.原文地址如下
http://bbs.chinaunix.net/viewthr ... p%3Bfilter%3Ddigest

有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小


遍读全部内容，没有一个比较好的算法能够即正确又是在最坏情况下通用，并且有论证严谨的．
思考了两天后，终于理清了思路．理论上，这个的题目的最优的复杂度应是O(2^(n-1))

首先设A为a中所有原素的和,B为b中所有原素的和.

t=|A-B|为当前两数组之差．A',B'分别为交换后的和

a(i)为a中任取i个元素的和,b(i)为了中任取i个元素和.

由于|a(i)-b(i)|与|a(j)-b(j)| (i<>j)  相互之间没有必然因果关系，就是说取i个元素进行交换和取j个元素进行交换,对于|A'-B'|的值的影响是彼此不相干的．

所以可能通过抽取排列组合从a(1)(对应b(1))到a(n/2)(对应有b(n/2))的组合抽取，然后对得到的|a(i)-b(i)|与t/2比较，最接近的就是最优解了．由于最优解个数的最大值可能为2^n-1(即所有元素都相等).

数学表达为
C(1,n)C(1,n)+C(2,n)C(2,n).......+C(n/2,n)C(n/2,n)次比较|a(i)-b(i)|与t/2的值.

至于对于大于n/2的组合不用再抽取的原因我想不用过多解释了．


最后复杂度应该是比把两个数组合并从2n个元素中抽取n元素的方式要低多了，有没有比此复杂更低的算法呢,我想是没有的了，因为由于|a(i)-b(i)|与|a(j)-b(j)| (i<>j)  相互之间没有必然因果关系．

不管如何,能在8分钟写出答案的人都是值得我去学习的．

不对的地方希望达人指正．

[ 本帖最后由 wysilly 于 2007-9-29 20:21 编辑 ]

局内人

把 a_1, ... , a_n, b_1, ... , b_n 记为 x_1, ..., x_2n. 题目的意思是从这 2n 个数中选 n 个求和得到 S1, 剩下的求和得到 S2，要求 S1-S2 最小。

这也相当于考虑 (x_1, ..., x_2n) 与一个向量 (y_1, ... ,y_2n ) 的内积，其中 y_1, ..., y_2n 中有 n 个取 1， n 个取 -1， 要求内积最小。

由排序不等式知道，反序和最小，所以现把 x_1, ..., x_n 从小到大排序得到 (z_1, ..., z_2n) 然后 (z_1,..., z_2n)(1,..., 1, -1, ..., -1) 为所求最小值。

z_1, ..., z_n 就是所求第一组数， z_{n+1}, ..., z_2n 就是所求第二组数。

o(n log n)

ddvv

所以现把 x_1, ..., x_n 从小到大排序得到 (z_1, ..., z_2n) 然后 (z_1,..., z_2n)(1,..., 1, -1, ..., -1) 为所求最小值。

可以解释一下，为什么这样是最小的？在样做的方法不就是把a,b两组数和起来，然后排序，最后去前n个为第一组，后面n个为第二组么？这样做怎么好像取出的结果是差最大而不是差最小。。。。。。
我算法不是很强，所以一时半会没看懂，请教一下~

halve

这个好像是经典题目吧，记得以前上课的时候都有讲到。。。

dxcnjupt

楼主这个.....就是穷举的算法
这一题只能用穷举做，楼主的证明很漂亮
|a(i)-b(i)|与|a(j)-b(j)| (i<>j)  相互之间没有必然因果关系，就是说取i个元素进行交换和取j个元素进行交换,对于|A'-B'|的值的影响是彼此不相干的．


那边的帖子只看了8页，实在是看不下去了......
CU学过数论基础的人好像很少啊

所有看到的算法（除穷举外）都是“先放置一些数，然后再考虑余下的数如何放置”
我晕
难道都不需要考虑回退的吗
如果正好要把最大的几个数放在一起怎么办？？（比如144456）
如果要把 第N1大的数－第N2大的数 放一起怎么办？？（14445688）
如果这些“连续放置”组合起来又要怎么办？？

根据后面小数的数值分布，前面大数的放置情况也是需要回退的。证明如楼主所述。

如果是“只要接近最小值”，那么这一题有很多解法；但题目要求“严格最小值”，所以实际上只能穷举。最多不过是根据“差相等”的情况做有限的优化。

cjaizss

经典的不能再经典的问题了

ypxing

这个问题的复杂度和背包问题应该是相当的