交换使两个序列差最小| Two Equal-sized Subsets Partition Problem

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

这是微软的一道面试题，也在July整理的面试100题之中。本来我想了一下，没有什么特别好的方案，于是百度之。结果百度第一页出来的答案，都一样就算了，还是错的。吐槽无力， 然后就有了这篇中文文章。

首先很容易想到，这问题的本质，就是将一个长度为2n的数组，分成长度为n的两个子数组，使它们和的差值最小。这是数组分隔问题的一个特例。见Partition Problem。在原问题中，原数组允许被分为两个任意长度的子数组（只要它们合起来为2n）。然而有了子数组长度必须为n这个条件后，这个问题难度并没有降低--它还是一个NP问题。证明见这里。

网上搜出来的很多解法，其实不能说全错。但它们不能保证始终得到最优解。大多数方法用的都是贪婪算法的思想，然而贪婪算法是以局部最优解去揣测全局最优解--可能成功，也可能失败。贪婪算法获取全局最优解的典型例子比如Dijkstra最短路径算法以及求最小生成树的kruskal算法。 但其有效性需要严格的证明，当然，证明其失败的话，一个反例即可。网上的大多数算法，不能保证总是最优解，但有一些确实是优秀的渐近算法，能保证结果于最优解的差距在一定范围以内。关于这些算法可以参考这里。

那么，如何得到最优解？
1. 穷举法。
天下武功，唯快不破。算法么，只要够暴力，总是能解的。- -！
问题本质是从2n个元素中取出n个元素，使其和最接近于Sum/2，其中Sum为2n个元素的总和。
所以只要枚举出2n个元素中n个元素的所有组合，迭代更新最接近的值，总和得到最好的解。当然，这个算法的时间复杂度就是阶乘级别的了，不过对于一个NP问题，这也不丢脸呵。

2. DP 算法。
详见编程之美209页。

public class PartitionArray {
 
 /**
  * @param array:
  *        assuming that the input array is the combination of two n-sized array.
  * @return int :
  *        minimal difference of the two n-sized subsets.
  */
 public static int minimalSum (int[] array){
  int total = sum(array);
  int sum = total/2;
  int n=array.length/2;
  
  //dp[i][v] = true means that there's i elements added up to value v.
  boolean[][] dp = new boolean[n+1][sum+1];
  dp[0][0]=true;
  
  for(int k=1;k<=2*n;k++){
   int val = array[k-1];
   for(int i=1;i<=k&&i<=n;i++){
    for(int v=1;v<=sum;v++){
     //try to take k as i th element
     if(v>=val && dp[i-1][v-val])
      dp[i][v]=true;
    }
   }
  }
  //find the answer. we need n-sized subset, so just check dp[n][*].
  for(int i=sum;i>0;i--){
   if(dp[n][i])
    /**
     * we find a subset with size=n and sum=i,another subset will have sum=total-i
     * so the difference will be (total-i)-i=total-2*i
     */
    return total-2*i;
  }
  return -1; 
 }
 
 private static int sum(int[] array){
  int sum=0;
  for(int i:array)
   sum+=i;
  return sum;
 }
}

当数组之和非常大的时候，DP算法的数组就会非常大，就不那么高效了。
对于一些极端例子，比如A=[ 12345,12332,14098], B=[ 32213,12321,23132]. DP还不如暴力破解。C(6,3) = 120。 总共才120种可能。