两次交流，找出最小差异

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; 
}