Monday, February 18, 2013

交换使两个序列差最小| 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种可能。

2 comments: