[Python]华为面试题，交换两个数组的元素使之总和的差值最小。

这是个NPC问题，所以就用穷举发了，在这里给出了一个用python的itertools的解法，个人认为比较简洁。

import itertools

def funcProduct(a, b):
    for c in itertools.permutations(b):
        for d in itertools.product(*[list(itertools.permutations(x)) for x in zip(a, c)]):
            yield zip(*d)

a = [1,2,3,4]
b = [5,6,700,800]
print min(funcProduct(a,b), key=lambda x:abs(sum(x[0])-sum(x[1])))

评论

8 楼 flysunmicro 2011-03-24  

合并，排序

7 楼 liuningbo 2011-03-24  

看看写了个 ，实现不需数组长度一致，复杂度O(n^2),求好的算法
   

   /**  arr1={1,2,3};  
     * arr2={22,33,44,55};  
     * 交换两个矩阵数据  
     */  
    public  void exchange(){   
        int index=0;           
        int len=arr1.length;   
        int currMinus=getMinus();          
        while(true){               
            for (int i = 0; i < arr2.length; i++) {   
                echangeMatrix(index,i);//交换值   
                if(currMinus>getMinus()){   
                    currMinus=getMinus();//一次循环中找到最小minus的                 
                }else {   
                    echangeMatrix(index,i);//若不是则不交换，即再换同一位置一次   
                }                  
            }   
            index++;   
            if(index>=len){   
                break;   
            }   
        }   
           
    }   
    private void echangeMatrix(int index,int des){   
        int temp=0;   
        temp=arr1[index];   
        arr1[index]=arr2[des];   
        arr2[des]=temp;   
    }   
    /**计算和  
     * ryuuninbou  
     * @return     int  
     */  
    private  int getMinus(){   
        int sum1=0;   
        int sum2=0;   
        for (int i = 0; i < arr1.length; i++) {   
            sum1+=arr1[i];   
        }   
        for (int i = 0; i < arr2.length; i++) {   
            sum2+=arr2[i];   
        }   
        return Math.abs(sum1-sum2);   
    } 

6 楼 jackra 2011-03-24  

jackra 写道

我个人意见:
先重排所有数组元素到管道
然后分别对2个数组中最小的一组追加当前最小数值.
另外,使用数组效率不好
最好用链表来做

本人不太懂数学,不清楚有什么具体的解法,最少我是没举证出这样不合理的例子,希望大家集思广益.

有个问题,均等树组下,这样的情况貌似问题不大,非均等的情况貌似要用大的树组里第2大元素和小树组里的最小元素交换.

5 楼 jackra 2011-03-24  

我个人意见:
先重排所有数组元素到管道
然后分别对2个数组中最小的一组追加当前最小数值.
另外,使用数组效率不好
最好用链表来做

本人不太懂数学,不清楚有什么具体的解法,最少我是没举证出这样不合理的例子,希望大家集思广益.

4 楼 ggzwtj 2011-03-21  

chenhao112358 写道

如果不要求最有解，可以直接遍历一遍数组，然后比较sum大小和a[i],b[i]大小，看是否交换，就OK 了。
如果需要求最优解，那么就可以先弄个二维数组，记录两个数组的差值表，然后比较sum差值，再去匹配差值表，看需要交换哪几个。

二维数组怎么记录信息？记录对应的位置的两个数是否交换过吗？

3 楼 ggzwtj 2011-03-21  

楼主有用过背包算法，就是传说中的小偷想偷东西，但是包包的容量是有限的，拿那些东西才能取得最多的东西。

其实可以换个角度想问题，就可以把楼主的问题转换成背包问题了：
如果想让两个数组的和之差最小，这不就是让两个数组的和都非常接近总和的一半！当然很多情况下是不能是得两个数组的和相等，都等于总和的一半。

如果不想等的话，必然有一个数组的和是小于总和一半的。我们要做的就是怎么让这个小的部分最接近总和的一半。

所以，这个问题应该可以转化成0-1背包问题，而这个包的大小就是所有数总和的一半，最后我们要求的是用一定量的数字怎么把这个包装得最满。

所以，这不是一个NP问题。

ps：如果我对楼主的描述没有理解错的话。:)

2 楼 chenhao112358 2011-03-21  

如果不要求最有解，可以直接遍历一遍数组，然后比较sum大小和a[i],b[i]大小，看是否交换，就OK 了。
如果需要求最优解，那么就可以先弄个二维数组，记录两个数组的差值表，然后比较sum差值，再去匹配差值表，看需要交换哪几个。

1 楼 dabaosod011 2011-03-19  

楼主你是新来的吧，这种贴还是算入门水准，给你投了新手贴了。

>>> a = [1,2,3,4]
>>> b = [5,6,700,800] 
>>> import itertools
>>> min(itertools.combinations(a+b, len(a+b)/2), key=lambda x:abs(sum(x)-sum(a+b)/2))
(4, 5, 6, 700)