华为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));
}
}
