arrays - 需要多少次交换才能使数组 a 和 b 之和的差最小？

Question

给定 2 个整数数组 a[]和 b[]与 n (1 <= n <= 100) 大小相同编号自 1 to n .
(0 <= a[i], b[i] <= 6)
您可以交换任何 a[i]与 b[i] .
需要多少次交换才能使数组 a[] 的总和之差|和 b[]是最低的？
然后打印出来:

掉期次数

交换索引

两个数组和的差

示例

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