華為06年面試題（要求8分鐘完成）
題目：
有兩個(gè)數(shù)組a,b岛宦，大小都為n,數(shù)組元素的值任意，無(wú)序耍缴；
要求：
通過(guò)交換a,b中的元素砾肺，使數(shù)組a元素的和與數(shù)組b元素的和之間的差最小挽霉。
前幾天華為機(jī)試,掛了...題目就是這道題,當(dāng)時(shí)只有百分之三十的通過(guò)率,機(jī)試掛了面試機(jī)會(huì)都沒(méi)有,郁郁寡歡,一直思索這題到底正確的方式是什么,特此記錄.
網(wǎng)上很多代碼都是直接遍歷任意兩個(gè)之間交換,這樣只能做到局部最優(yōu)無(wú)法處理a{7,8,97,9800} b{1,15,898,9000}這樣的情況(必須同時(shí)交換兩個(gè));
這題比較正確的思路可能是在2n個(gè)數(shù)里取n個(gè)數(shù),這n個(gè)數(shù)最接近sum/2的情況;
網(wǎng)上有討論 n個(gè)數(shù)里取若干個(gè)數(shù),使其和最接近值M---https://blog.csdn.net/lsjseu/article/details/11660731
也就是這個(gè)問(wèn)題可以看作一個(gè)背包問(wèn)題,容量為sum/2,但是有個(gè)限制條件2n個(gè)數(shù)里必須要取n個(gè);
暫時(shí)代碼如下,有更好解法的大佬還望留個(gè)言指導(dǎo)下,對(duì)這題是真的懵逼...
public class BagProblem {
// 存a,b數(shù)組拼接后的數(shù)組；
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;
}
// 遞歸：(復(fù)雜度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);
}
}
/**
* 動(dòng)態(tài)規(guī)劃:
* 復(fù)雜度：len*len/2*sum
* 注意順序必須前面算完了才開(kāi)始算后面
* 計(jì)算前可以先比較下len*len/2*sum和2^len哪個(gè)大再?zèng)Q定用哪種
* i表示前i個(gè)數(shù)組
* j表示前i個(gè)里選j個(gè)
* v表示放不超過(guò)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個(gè)里選j個(gè)
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{
// 當(dāng)前i==j時(shí)变汪，向上遞歸的時(shí)候result[i-1][j][v]會(huì)失去意義
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) {
// 數(shù)組合并下
// 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數(shù)組的長(zhǎng)度："+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("花費(fèi)時(shí)間："+(end-start));
System.out.println("最接近sum/2的組合的和："+k);
System.out.println("最小差值結(jié)果:"+ (bp.sum(input)-2*k));
}
}
