对于一个算法题的思考．

精华帖的一个思考.原文地址如下


有两个数组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)为b中任取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分钟写出答案的人都是值得我去学习的．

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