兩次交流，找出最小差異

Question

有兩個數組a[], b[];sum_a是a[]總和，sum_b是b[]和總和diff = |sum_a - sum_b|;

現在我們有機會與b[j]交換a[i]兩次;

我們想要獲得最小差異？

例如：
一個= 7 7 5 5
B = 3 3 6 6

我們能與6交換7 3和交換機5：

一個= 3 7 6 5
b = 7 3 5 6

所以我們可以得到的最小差異是(3+7+6+5)-(7+3+5+6) = 0;

問題：程序如何從給定的數組中找到最小差異a[] and b[]？

Answer 1

您可以使用蠻力算法解決此問題。下面我用兩個循環來模擬一個交換，你可以擴展來模擬兩個交換。在cpp中演示。

int main() 
{ 
    int a[100]; 
    int b[100]; 
    int sumA=0; 
    int sumB=0; 
    int diff=0; 

    int n; 
    cin>>n; 
    for(int i=0; i<n; i++){ 
    cin>>a[i]; 
    sumA+=a[i]; 
    } 
    for(int i=0; i<n; i++){ 
    cin>>b[i]; 
    sumB+=b[i]; 
    } 
    diff= abs(sumA-sumB); 
    cout<<" Orig diff: " <<diff<<endl; 
    for(int i=0; i<n; i++){ 
     for(int j=0; j<n;j++){ 
      int tmp = abs(a[i]-b[j]); 
      int newSumA = sumA+tmp; 
      int newSumB = sumB-tmp; 
      int newDiff = abs(newSumA-newSumB); 
      if(newDiff<diff){ 
      diff = newDiff; 
      } 
     } 
    } 
    cout<<"Answer: "<<diff<<endl; 
    return 0; 
}