陣列平衡

Question

我們有兩個數組a []和b []，我們需要找到兩個數組a和a之間的最小絕對差值a & b和最小值no。的舉動使最小的絕對差異。

示例：
一個[] = {} 70,30,33,23,4,4,34,95總和= 293
B [] = {} 50,10,10,7總和= 77

將95,23從數組a移動到b。
移動10從陣列a到b

移動兩個陣列的總和之後變爲185

輸出爲0，3（的移動兩個陣列之間的差異，沒有。）

Answer 1

第一部分你的問題，「找到兩個數組之和的最小絕對差值a & b」，是Knapsack problem的變體。維基百科定義爲「給定一組項目，每個項目都有一個權重和一個值，確定每個項目包含在一個集合中的數量，以便總權重小於或等於給定限制，總值爲儘可能大。「

要查看此結果，請將a和b中的所有值合併到一個新數組ab中，並查找其值的一半。你想找到ab中的元素，它們的總和等於或者儘可能接近它。然後，您可以將這些值和a和其餘的b，這是獲得最小絕對差異的方法之一。

要找到你「的舉動最低數量」，我們可以找到解決揹包問題，然後爲每個解決方案找到需要多少移動拿回去給所有方式原始a和b（或原始b和a如果這需要更少的移動）。

只有你的問題的第一部分computational complexity是着名的NP-完整的，所以期待一個長期運行的程序適用於任何規模較大的數組。維基百科的文章有多種算法來解決你的問題的第一部分，所以你可以從那裏開始並選擇算法。

難怪這是一個競爭性編程問題！