使数组 a 和 b 之和的差最小所需的最小交换次数是多少？

Question

给定 2 个整数数组 a[] 和 b[]，其大小与 n (1 <= n <= 100) 相同，编号来自 1 to n。

(0 <= a[i], b[i] <= 6)

您可以将任何 a[i] 替换为 b[i]。

需要多少 最小交换次数 才能使数组 a[] 和 [=] 之和的 之差14=] 是 最小值 ?

然后打印出来：

兑换次数
交换索引
两个数组之和的差

例子

n = 6

a[] = { 1, 1, 4, 4, 0, 6 }

b[] = { 6, 3, 1, 1, 6, 1 }

结果

 - 2 (The number of swaps)
 - 5, 6 (The swapped indexes)
 - 0 (The difference of sums of the arrays)

说明

如果将 a[5] 与 b[5] 和 a[6] 交换 与 b[6] 需要 2 交换，数组 a[] 和 b[] 将变为:

a[] = {1, 1, 4, 4, 6, 1}

b[] = {6, 3, 1, 1, 0, 6}

a[] 的总和是 1 + 1 + 4 + 4 + 6 + 1 = 17

b[] 的总和是 6 + 3 + 1 + 1 + 0 + 6 = 17

所以两个和的差是0.

Answer 1

这是一种迭代方法，可以保存目前为止的差异并更新实现差异所需交换的最小索引列表。

JavaScript代码：

function update(obj, d, arr){
  if (!obj[d] || obj[d].length > arr.length)
    obj[d] = arr;
}

function f(A, B){
  let diffs = {0: []};
  
  for (let i=0; i<A.length; i++){
    const newDiffs = {};
    
    for (d in diffs){
      // Swap
      let d1 = Number(d) + B[i] - A[i];
      if (diffs.hasOwnProperty(d1) && diffs[d1].length < diffs[d].length + 1)
        update(newDiffs, d1, diffs[d1]);
      else
        update(newDiffs, d1, diffs[d].concat(i+1));
        
      d1 = Number(d) + A[i] - B[i];
      if (diffs.hasOwnProperty(d1) && diffs[d1].length < diffs[d].length)
        update(newDiffs, d1, diffs[d1]);
      else
        update(newDiffs, d1, diffs[d]);
    }
    
    diffs = newDiffs;
  }

  console.log(JSON.stringify(diffs) + '\n\n');
  
  let best = Infinity;
  let idxs;

  for (let d in diffs){
    const _d = Math.abs(Number(d));
    if (_d < best){
      best = _d;
      idxs = diffs[d];
    }
  }

  return [best, idxs];
};

var A = [1, 1, 4, 4, 0, 6];
var B = [6, 3, 1, 1, 6, 1];

console.log(JSON.stringify(f(A, B)));

Answer 2

这是我的基于 Javascript גלעד ברקן 答案的 C++ 实现。

简短说明：

我们维护了迄今为止看到的所有差异及其最小交换的映射，并尝试根据新值扩展目前看到的所有差异以获得此类新映射。在考虑 A 和 B 中的 ith 项时，我们在每一步都有 2 个选择，要么按原样考虑这些项，要么交换 ith 个项。

代码：

#include <iostream>
#include <climits>
#include <unordered_map>
#include <vector>
using namespace std; // Pardon me for this sin


void update_keeping_existing_minimum(unordered_map<int, vector<int> >& mp, int key, vector<int>& value){
    if(mp.find(key) == mp.end() || mp[key].size() > value.size())mp[key] = value;
}

// Prints minimum swaps, indexes of swaps and minimum difference of sums
// Runtime is O(2^size_of_input) = 2^1 + 2^2 .. + 2^n = 2*2^n
// This is a bruteforce implementation.
// We try all possible cases, by expanding our array 1 index at time.
// For each previous difference,
// we use new index value and expand our possible difference outcomes.
// In worst case we may get 2 unique differences never seen before for every index.
void get_minimum_swaps(vector<int>& a, vector<int>& b){
    int n = a.size();

    unordered_map<int, vector<int> > prv_differences_mp;
    prv_differences_mp[0] = {}; // initial state

    for(int i = 0 ; i < n ; i++){
      unordered_map<int, vector<int> > new_differences_mp;
      
      for (auto& it: prv_differences_mp) {

          // possibility 1, we swap and expand previous difference
          int d = it.first;
          int d1 = d + b[i] - a[i];

          if(prv_differences_mp.find(d1) != prv_differences_mp.end() && prv_differences_mp[d1].size() < (prv_differences_mp[d].size() + 1)){
            update_keeping_existing_minimum(new_differences_mp, d1, prv_differences_mp[d1]);
          } else {
            // only place we are modifying the prv map, lets make a copy so that changes don't affect other calculations
            vector<int> temp = prv_differences_mp[d];
            temp.push_back(i+1);
            update_keeping_existing_minimum(new_differences_mp, d1, temp);
          }

          // possibility 2, we don't swap and expand previous difference
          int d2 = d + a[i] - b[i];
          if(prv_differences_mp.find(d2) != prv_differences_mp.end() && prv_differences_mp[d2].size() < prv_differences_mp[d].size()){
            update_keeping_existing_minimum(new_differences_mp, d2, prv_differences_mp[d2]);
          } else {
            update_keeping_existing_minimum(new_differences_mp, d2, prv_differences_mp[d]);
          }
      }
      
      cout<<i<<":index\n";
      for(auto& it: prv_differences_mp){
        cout<<it.first<<": [ ";
        for(auto& item: it.second)cout<<item<<" ";
        cout<<"] ; ";
      }
      cout<<"\n";
      prv_differences_mp = new_differences_mp;
    }

    int best = INT_MAX;
    vector<int> min_swap_ans;

    for(auto& it: prv_differences_mp){
      int _d = it.first >= 0 ? it.first: -it.first;
      if(_d < best){
        best = _d;
        min_swap_ans = it.second;
      }
    }
   
    cout<<"Number of swaps: "<<min_swap_ans.size()<<"\n";
    cout<<"Swapped indexes:\n";
    for(auto idx: min_swap_ans)cout<<idx<<" ";
    cout<<"\nDifference: "<<best<<"\n";

}

int main(){

  vector<int> A{ 1, 1, 4, 4, 0, 6 };
  vector<int> B{ 6, 3, 1, 1, 6, 1 };
  
  get_minimum_swaps(A, B);

  return 0;
}

使数组 a 和 b 之和的差最小所需的最小交换次数是多少？

What is the minimum number of swaps needed so that the difference of sums of arrays a and b is minimum?

arrays

algorithm

np-hard

这是我的基于 Javascript גלעד ברקן 答案的 C++ 实现。