Question

超难算法题：任给出2n个整数(不妨假设an满足:a1<a2<a3<...a2n)组成的int型数组

求一个函数 int * minHalfArray(int array[],int m)，其中m=2n,array是2n个int型整数组成的数组的首地址，要求函数从array[2n]中找出其中n个数数组成的一个新数组 returnValue[n]，使得returnValue[n] 数组的和尽量接近array[2n]数组和的一半，并返回returnValue的值(若有多种解只需返回其中任意一个)。
找到了，在维基百科上，这类题被称为最简单的NP完全问题了。
http://en.wikipedia.org/wiki/Partition_problem
不知道从哪里看到的这个题，也算长了见识，谢谢大家的回答！

Answer 1

嗯，其实应该不难吧。
首先您先给数组排序(从小到大，结合下面所说)，数组有序后您再求和，第三步就是从小到大尝试着去相加，知道达到一个临界的下标，在这下标下只有两个分支，
第一，直接等于和的一半，出来就是结果。
第二，此下标满足此0下标到此下标刚好比一半小，此下标下一个之和比一半大，结果为两者与和的一半相差较小的(及差的绝对值更小)
有了这个下标，只需返回数组0下标到所求下标的值。
算法实现可以再问，但大体思想你明白就行。

Answer 2

我来说说，假定这个数组是排好序，不妨设为升序，计算出和sum,然后除以2n,必然得到一个整数位于a1与a2n之间，找到这个整数（或者是最接近他的），然后定义两个指针同时指向这个数字，一个左移，一个右移，注意如果一个指针到达边界就只移动另一个指针，并求和两个指针间的数字和为sum2，使其最接近sum,这样就OK了，时间复杂度为0（n),应该满足要求

Answer 3

这和另一道题的解法一样：给一个string，输出string中所有的字符组合，不考虑字符顺序。比如“set”有se,st,et，set。你这个问题就转成把这些组合列出来，然后看哪个组合离和的一半最近就行了

追问

这是枚举，C(n,2n),时间复杂度n!,有更好的吗？

追答

想不出来啊，因为有很多不确定性，比如要求的是找与和的一半最接近的，那不列举出来谁知道多近是最接近呢。不过这个算法可以改良，比如这是一个整型数组，有正数有负数，那么就把这个数组统一加上最小负数的绝对值，使得这个数组变成正数数组。然后把这个数组中大于和的一半的数组舍去。再者在不求和的情况下一定有一个数最接近和的一半，那么求和小于这个数的枚举数组可排除。

Answer 4

我的想法：
使用随机算法。
1. 先把这个数组（大小2n）随便分成两个大小为n的数组，记为arr1和arr2。
2. 然后每次从arr1中选一个数i,从arr2中选一个j，如果交换i和j的值能够使得两个数组的和更接近，则交换。否则，不交换。
3. 循环第二步一定次数。使得2个数组的和不断接近。
第三步的次数非常重要。
随机算法肯定可以的，请参考poj2531和poj2454，都是典型的使用随机算法的题目，和本题类似。

Answer 5

这个真的很难，貌似是个面试题

追问

希望可以有高人指点迷津。不过枚举就不用说了，效率太低，复杂度接近n!了。