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

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

交换使两个序列差最小| Two Equal-sized Subsets Partition Problem | Thousand Sunny
有两个序列a,b，大小都为n,序列元素的值任意整数，无序；
要求：通过交换a,b中的元素，使[序列a元素的和]与[序列b元素的和]之间的差最小
http://yyeclipse.blogspot.com/2013/02/two-equal-sized-subsets-partition.html
还有一种思路就是：转化为：2n个数组，把它划分为两个数组并且使之和之差最小，编程之美有详细解答
当数组之和非常大的时候，DP算法的数组就会非常大，就不那么高效了。
对于一些极端例子，比如A=[ 12345,12332,14098], B=[ 32213,12321,23132]. DP还不如暴力破解。C(6,3) = 120。总共才120种可能。

/**

  * @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; 

}

用回溯法(backtracking)解决平衡集合问题
http://blog.csdn.net/ljsspace/article/details/6434621#

X. Don't think this method will work.
http://www.cnblogs.com/tractorman/p/4063866.html

核心代码分析：为什么会使用if((A[i]!=B[j]) && (abs(diff-2*(A[i]-B[j]))<=abs(diff)))...1,而不是if(abs(diff-2*(A[i]-B[j]))<abs(diff))...2 ？,因为如果使用代码2，就会有特例出现：

　　 A ＝ { 5,5,9,10 }; B ＝{ 4,7,7,13 }; A的和为29，B为31。当把A中的5，5与B中的4，7交换后，A与B的和都为30，差为0.但使用代码2将检测不到这种交换！因此输出结果是原数组。

　　而使用代码1就可以输出差为0的两个数组。因为A和B和之差的绝对值为2，如果A的5与B的7交换后差的绝对值也是2，可以交换。则5和7交换之后，再把A的5和B的4交换，差的绝对值就为0了。

　　为什么有(A[i]!=B[j])？，因为如果A和B中有相同元素的时候，就会进入死循环。

　　所以综合起来，就应该使用if((A[i]!=B[j]) && (abs(diff-2*(A[i]-B[j]))<=abs(diff)))

void Swap()
{
    int sumA=0,sumB=0;
    int times = 0;
    int flag = 1;
    for (int i=0;i<N;i++)
    {
        sumA+=A[i];
        sumB+=B[i];
    }

    int diff=sumA-sumB;
    if(diff==0)
        return;
    while (flag)
    {
        flag = 0;
        for(int i=0;i<N;i++)
            for (int j=0;j<N;j++)
            {    
                if((A[i]!=B[j]) && (abs(diff-2*(A[i]-B[j]))<=abs(diff)))
                {
                    diff = diff-2*(A[i]-B[j]);
                    swap(A[i],B[j]);
                    flag = 1;
                }
                times++;
            }
    } 
    cout << "times = " << times << endl;
}

http://www.cnblogs.com/tianshuai11/archive/2012/04/20/2477169.html
http://blog.csdn.net/cwqbuptcwqbupt/article/details/7521733
这种方法却有缺陷，因为一次只允许交换一对元素，这对于一次需要交换两个元素的数组而言将出错，考虑如下情况：
A ＝ { 5,5,9,10 };
B ＝ { 4,7,7,13 };
A的和为29，B为31。当把A中的5，5与B中的4，7交换后，A与B的和都为30，差为0.但上述算法一将检测不到这种交换！因此输出结果是原数组。当前数组a和数组b的和之差为
A = sum(a) - sum(b)

a的第i个元素和b的第j个元素交换后，a和b的和之差为
A' = sum(a) - a[i] + b[j] - （sum(b)- b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])

设x= a[i] - b[j]
|A| - |A'| = |A| - |A-2x|

假设A> 0,
当x在(0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，
x越接近A/2效果越好,
如果找不到在(0,A)之间的x，则当前的a和b就是答案。

所以算法大概如下：
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，
重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。
http://bylijinnan.iteye.com/blog/1356447

* 求解思路：
* 当前数组a和数组b的和之差为 A = sum(a) - sum(b) a的第i个元素和b的第j个元素交换后，
* a和b的和之差为 A'
* =sum(a) - a[i] + b[j] - （sum(b) - b[j] + a[i])
* = sum(a) - sum(b) - 2 (a[i] -b[j])
* = A - 2 (a[i] - b[j])
* 设x = a[i] - b[j], 则交换后差值变为 A’ = A - 2x
*
* 假设A > 0, 当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好,
* 如果找不到在(0,A)之间的x，则当前的a和b就是答案。所以算法大概如下：
* 在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，
* 重复前面的步骤直至找不到(0,A)之间的x为止。
*/
public static void main(String[] args) {
MinSumASumB minSumASumB=new MinSumASumB();
int[] a={3,5,-10};
int[] b={20,25,50};
minSumASumB.swapToMinusDiff(a, b);
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(b));
}
public void swapToMinusDiff(int[] a,int[] b){
int sumA=sum(a);
int sumB=sum(b);
if(sumA==sumB)return;
if(sumA<sumB){
int[] temp=a;
a=b;
b=temp;
}
int curDiff=1;
int oldDiff=Integer.MAX_VALUE;
int pA=-1;
int pB=-1;
boolean shift=true;
int len=a.length;//the length of a and b should be the same
while(shift&&curDiff>0){
shift=false;
curDiff=sum(a)-sum(b);
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
int temp=a[i]-b[j];
int newDiff=Math.abs(curDiff-2*temp);
if(newDiff<curDiff&&newDiff<oldDiff){
shift=true;
oldDiff=newDiff;
pA=i;
pB=j;
}
}
}
if(shift){
int temp=a[pA];
a[pA]=b[pB];
b[pB]=temp;
}
}
System.out.println("the min diff is "+oldDiff);
}

http://blog.csdn.net/liulanghk/article/details/46628201
通过交换的方式，最终的状态是在保证两个序列中元素个数相同的条件下，任何一个元素都可以位于两个序列中的任何一个。这样问题可以转化为：在一个长度为2*n的整数序列中，如何将元素个数分成两个子集，记每个子集的元素之和分别为S1和S2，使得|S1-S2|最小。

//分别表示 a[]的和 b[]的和以及2者之差 int sum1,sum2,a; int temp; //和之差是否大于0 bool dayu0; //等待交换的a[i]和b[j]的下标 i j int pos1,pos2; //最接近a/2的a[i]-b[j]值 float minn; //是否能有解 bool have1 ; while (1) { sum1 = 0; sum2 = 0; //求两个数组的和 for (int i = 0 ; i < n;++i) { sum1 += ar1[i]; sum2 += ar2[i]; } a = sum1 - sum2; //和之差 dayu0 = a>0?true:false; //和之差是大于0还是小于0 have1 = false; //是否能找到解 for (int i = 0 ; i < n;++i) //找最接近a/2的 a[i]-b[j] { for (int j = 0;j < n;++j) { temp = ar1[i] - ar2[j]; //如果a[i]-b[j] 在(0,a)之间 (超出的就没有意义了) if ((dayu0 && temp > 0 && temp < a)||(!dayu0 && temp < 0 && temp > a)) { //若比之前的a[i]-b[j]更接近a/2 则更新 if (have1 && abs(temp - a/2.0) < minn) { minn = abs(temp - a/2.0); pos1 = i; pos2 = j; } else { have1 = true; minn = abs(temp - a/2.0); pos1 = i; pos2 = j; } } } } if (!have1) //若找不到符合条件的a[i]-b[j]了则结束 { break; } swap(ar1[pos1],ar2[pos2]); //交换a b中的元素 }
这个题目的原型是之前做过的ACM动态规划
多米诺骨牌（DOMINO）
问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：
顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。
现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。

Read full article from 交换使两个序列差最小| Two Equal-sized Subsets Partition Problem | Thousand Sunny

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

Labels

Popular Posts