通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差

华为06年面试题（要求8分钟完成）

题目：

有两个数组a,b，大小都为n,数组元素的值任意，无序；
要求：

通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小。

前几天华为机试,挂了...题目就是这道题,当时只有百分之三十的通过率,机试挂了面试机会都没有,郁郁寡欢,一直思索这题到底正确的方式是什么,特此记录.

网上很多代码都是直接遍历任意两个之间交换,这样只能做到局部最优无法处理a{7,8,97,9800} b{1,15,898,9000}这样的情况(必须同时交换两个);

这题比较正确的思路可能是在2n个数里取n个数,这n个数最接近sum/2的情况;
网上有讨论 n个数里取若干个数,使其和最接近值M---https://blog.csdn.net/lsjseu/article/details/11660731

也就是这个问题可以看作一个背包问题,容量为sum/2,但是有个限制条件2n个数里必须要取n个;

暂时代码如下,有更好解法的大佬还望留个言指导下,对这题是真的懵逼...

public class BagProblem {
    // 存a,b数组拼接后的数组；
    private  int[] arr;

    public BagProblem(int[] arr){
        this.arr=arr;
    }

    public  int sum(int[] arr){
        int sum=0;
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
        }
        return sum;
    }
    public  int sumz(int[] arr,int index){
        int sum=0;
        for(int i=0;i<index;i++){
            sum+=arr[i];
        }
        return sum;
    }



    // 递归：(复杂度2^len次方,舍弃)
    public  int recursion(int i,int j,int v){
        if(i<=0||j<0||v<0||i<j){
            return Integer.MIN_VALUE;
        }
        if(j==0){
            return 0;
        }
        if(arr[i-1]<=v){
            return Math.max(recursion(i-1,j,v),recursion(i-1,j-1,v-arr[i-1])+arr[i-1]);
        }else{
            return recursion(i-1,j,v);
        }
    }


    /**
     * 动态规划:
     * 复杂度：len*len/2*sum
     * 注意顺序必须前面算完了才开始算后面
     * 计算前可以先比较下len*len/2*sum和2^len哪个大再决定用哪种
     * i表示前i个数组
     * j表示前i个里选j个
     * v表示放不超过v重量
     * */

    public  int dynamic(int[] input){
        int len =input.length;
        int sum=sum(input)/2;
        // 存总重量
        int[][][] result=new int[len+1][len/2+1][sum+1];

        for(int i=1;i<=len;i++){
            for(int v=0;v<=sum;v++){
                for(int j=1;j<=len/2&&j<=i;j++){
                    // 比较i与j,i个里选j个
                    if(i>j){
                        if(input[i-1]>v){
                            result[i][j][v]=result[i-1][j][v];
                        }else{
                            result[i][j][v]=Math.max(result[i-1][j][v],result[i-1][j-1][v-input[i-1]]+input[i-1]);
                        }
                    }else{
                        // 当前i==j时，向上递归的时候result[i-1][j][v]会失去意义
                        if(sumz(input,i)>v||result[i-1][j-1][v-input[i-1]]<0){
                            result[i][j][v]=Integer.MIN_VALUE;
                        }else{
                            result[i][j][v]=result[i-1][j-1][v-input[i-1]]+input[i-1];
                        }
                    }

                }
            }
        }
        return result[len][len/2][sum];
    }







    public static void main(String[] args) {
        // 数组合并下
//        int[] input={1, 3, 5 ,49,0, 2, 4 ,18,1, 3, 5 ,49,0, 2, 4 ,18,1, 3, 5 ,49,0, 2, 4 ,18,1, 3, 5 ,49,0, 2, 4 ,18,1, 3, 5 ,49,0, 2, 4 ,18,1, 3, 5 ,49,0, 2, 4 ,18,1, 3, 5 ,49,0, 2, 4 ,18,1, 3, 5 ,49};
        int[] input={9,990,99000,99999};
//        int[] input={1,7,8,14,98,9800,9000,897};


        BagProblem bp=new BagProblem(input);

        System.out.println("2n数组的长度："+input.length);

//        int k=bp.recursion(input.length,input.length/2,bp.sum(input)/2);
        final long start = System.currentTimeMillis();
        int k=bp.dynamic(input);
        final long end = System.currentTimeMillis();
        System.out.println("花费时间："+(end-start));
        System.out.println("最接近sum/2的组合的和："+k);
        System.out.println("最小差值结果:"+ (bp.sum(input)-2*k));
    }
}