2倍、最小差分を見つける

Question

二つの配列a[], b[];sum_aがありますsum_bは今、私たちは2回b[j]とa[i]を交換する機会を持っているb[]とdiff = |sum_a - sum_b|;

の和である、a[]の和です。

最小の差分を取得したいですか？

例：
= 7 7 5
B = 3 3 6 6

我々は6と3と7、および交換5を交換することができる：

= 3 7 6 5
b = 7 3 5 6

私たちは最小の差分を得ることができるので、(3+7+6+5)-(7+3+5+6) = 0;

質問：どのように指定された配列から最小の差分を見つけるためにプログラムすることができますa[] and b[]？

Answer 1

この問題は、ブルートフォースアルゴリズムを使用して解決できます。以下では、2つのループを使用して1つの交換をシミュレートし、2つの交換をシミュレートするように拡張できます。 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; 
}