如何交換兩個數組的成員，使兩個數組的元素總和的差值最小？

Question

給定兩個無序數組array1和array2，長度均爲LEN。對於任何i(0<=i<LEN)，我可以交換array1[i]和array2[i]的值。現在，我必須以某種方式交換它們，以使array1和array2的元素之和的差值最小。

例如：

array1=[1, 3, 5] 
array2=[2, 4, 9] 

現在，如果我換兩個陣列的第三構件（5,9），該差成爲（1 + 3 + 9） - （2 + 4 + 5）= 2 。

我找到了一個使用遞歸的解決方案。在我的解決方案中，我檢查了所有有效組合以及差異最小的地方，那就是我的答案。但是這裏的運行時複雜度是O(2^LEN)。我怎樣才能更有效地做到這一點？

P.S.陣列索引從0開始。

Answer 1

考慮第三個陣列，其中ith條目是array1和array2中ith值的絕對差值。爲新數組中的這些差異分配符號等同於決定是否交換原始數組中的值。您現在正在嘗試解決將第三個數組中的（潛在符號交換）值的總和最小化的問題。這是Partition Problem的優化版本。