這個號稱「微軟的面試題」，該如何解答？

01-04

」有兩個數組a,b，大小都為n,；通過交換a,b中的元素，使|sum(a)-sum(b)|最小。「這個號稱微軟的面試題初看時還不覺得，無非排排序什麼的，後來發現太難了，而且網上的答案都不對，不知道哪位大神可以解答？
補充一下，題目的意思是，可以隨意交換（不要求交換對於項），可以交換多次，要求的是兩個數組的和的差值最小。其實也就是從2n個數裡面，取n個，要求取到的n個數的和與剩下的最接近。
我也是在CSDN上看的，大家可以搜下，但是原博主的解法明顯錯誤，誤導人，我自己又不會解。

什麼時候加上了絕對值……

帶絕對值就是 Partition Problem 了，有一個偽多項式的 DP 演算法，思路大概是這樣的：

var cache = ...; function P(a, j, l, s) { // a[0..j] 中有長度為 l 且總和為 s 的子集嗎？ if(cache.has(j, l, s)) return cache.find(j, l, s) // 緩存 if(l === 0 s === 0) return cache.save(j, l, s, true); if(l === 0 s !== 0 || j === 0 l &> 0 || j === 0 s !== 0) return cache.save(j, l, s, false); return cache.save(j, l, s, P(a, j - 1, l, s) || P(a, j - 1, l - 1, s - a[j - 1])) }

for(var s = Math.floor((sum(a) + sum(b)) / 2); s &>= 0; s--){ if(P(a.concat(b), n * 2, n, s)) { ... } }

不帶絕對值的話

先要說清楚定義，因為如果只能交換 ab 中的對應項，那麼很簡單的貪心法就能解決；如果可以多次任意交換，那麼就是排序完切割；如果是一次交換若干對的話，是 2n×2n 的二分圖最佳匹配，用 KM。

問題可以轉換成 從2N個數中選取N個，使得選取的數字和最接近總和的一半。

由於限定必須選取N個，個人感覺只能用搜索來做（錯誤請指正）。

@Belleve的答案是假設某種組合存在，然後反向搜索解是否存在，通過記憶化搜索（cache）降低時間複雜度。

另一種方式是正向搜索結果，每個數分為選和不選兩種情況，也可以加上一些剪枝策略。

用搜索方法來解，複雜度都不會太低，期待更好的解法。

------------------------------------------------------------------------------------------------

看到很多同學說這是一個背包問題，我有一些疑惑。

如果問題是 從2N個數中選取任意個，使得選取的數字和最接近總和的一半。

那麼將數的值即作為背包問題中物品的花費又做為物品的價值，那麼這是一個典型的01背包問題。

但如果限定必須選取N個，我就想不通了。求解惑~

不就是最簡單的背包么= =

同背包，求數據規模。

@郭彬

確實可以用背包做，不過動態規劃方程式要改成

f[j][k]為bool值表示選取j個後（區別於01背包的選取第i個）可以達到k空間（必須達到，區別01背包的滿足j空間）

然後

f[j][k]= $igcup_{i=1}^{n}$ {f[j-1][k-a[i]]}

用r[j][k]記錄前驅

m= $sum_{1}^{n}{a[i]}$

然後從m/2向前遍歷f[n][k]

找到為true則通過r回溯前驅

空間複雜度O(nm)

時間複雜度(n^2 m)

可以接受的數據n還是很小

DP可以求出那個值，至於怎麼找到所對應的a和b的數組，我感覺是搜索？

代碼段如下：

int sum=0; for (int i=1;i&<=n;i++){ cin&>&>a[i]; sum+=a[i]; } for(int i=1;i&<=n;i++){ for(int t=i-1;t&>=1;t--) for(int k=sum;k&>=0;k--) if(dp[t][k]) dp[t+1][k+a[i]]=1; dp[1][a[i]]=1; } int ans=0,t=n/2; for (int i=1;i&<=sum/2;i++) if(dp[t][i]) ans=i;

--以下錯誤做法--

先隨便分成兩個相等長度的數組，然後兩層for指向兩個數組中的元素，如果交換能使解更優就交換。如果兩層for下來曾經交換過，則繼續兩層for，否則演算法結束

題目應該可以等價於這個問題，在一個大小為2n的數組中選出n個數，使得這n個數儘可能接近2n個數總和的一半.

解決方法就是用排序，然後遞歸，一共C（n，2n）種情況，排序後剪下枝應該能搞定。。

我提供一個思路吧，大多數情況下基本能得到最優解，有時並不一定能得到最優解。

舉個特例例子，順便說下思路吧，1,2,4,8,16,32,64,128一共這8個數，先排序，然後兩兩取差，得到1,4,16,64。從大到小進行處理，取兩個數，64和16，然後64-16得48，代表原來最大的四個數分為兩組【16,128】【32,64】然後依次處理最後得到兩組【1,4,16,128】【2,8,32,64】。近似於最優解了，但不完全是。

其實就是如果數字差的不太大的話就可以答案，但是如果有差打的過分的話會出叉子。

PS，弄完之後可以進行微調，比如例子中第二組的和要小，然後依次嘗試交換第一組中比2大的數嘗試與2交換，然後的出更優解。然後依次處理。不過這樣做的時間複雜度不會好。

額.....看了回答我還是太嫩了嗎如果數組元素都是正數我想到的是就是一個容量為(a+b)/2 必須裝n個的背包問題

我的第一反應就是把a和b融合在一起，然後直接kmeans聚類

當然我知道考點肯定不在這裡，算是歪個題吧

另外，從直覺上，我覺得這是有數學解法的，依靠數學推理得到結論

然後直接按照結論做就好了

我覺得分類填數學比較容易有答案。。。

知乎的程序員什麼水平？

典型的npc問題，別惦記多項式解了。

近似演算法，隨機演算法。

算結果動規即可，要是找數組的話，相信我大力出奇蹟，爆搜不爆零

我覺得是個背包問題吧，容量為sum/2，遍曆數組求能放入的最大總和！

---明天上代碼

任意交換有個很水的方法就是按位做值域的dp……其實我第一反應是二分答案的費用流.........嗯，其實就是個背包.....我真是越來越水了

死做

排次序，接著遞歸｛中位二分後互換；不能互換 return｝

坐等大濕解法

想了個演算法請大家指正一下代碼什麼的請不要計較了只學過一丟丟編程

a1,a2,a3...an

b1,b2,b3...bn

for i = 1 to n //n的取值還沒考慮好

ci=sum(A)-sum(B) //不看絕對值，方便交換

if ci=0 or ci=ci-2 退出循環

k11=a1-b1,k12=a1-b2...knn=an-bn //循環自己腦補

取K中與ci同號項進行如下計算

x11=abs(k11-ci/2),x12=abs(k12-ci/2)...xnn=abs(knn-ci/2)

找到min(X)=xpq 將ap與bq互換

next i

輸出A，B。

已經完全看不懂了，所以，學了沒用也便忘了～

這是統計學問題，統計學問題，R語言叫自助法，研究的就是這種問題