arrays - 如何从两个数组中选取元素以使总和之间的差异最小

Question

有 2 个数组，其中两个数组的长度相同。

数组 A = 一组非负整数

数组 B = 一组非正整数

我必须为每个索引 i 选择 A[i] 或 B[i]，并且想知道 abs(sum) 的最小值。

e.g

example 1

A = {1,2,3,4} , B = {-1,-2,-3,-4}

then the minimum of abs(sum) would be 0 by selecting 1, -2, -3 and 4. (-1, 2, 3, -4) also works.

例子2

A = {1,1,1,3} , B = {0,0,0,-3}

then the minimum of abs(sum) would be 0 by selecting 1,1,1 and -3.

我只能想到计算需要指数时间的每种可能组合的天真方法。有没有更好的方法来解决这个问题？

Answer 1

这可以在 O(n * num_diffs) 中完成时间复杂度通过想象一桶否定只是我们试图尽可能接近另一个的另一桶积极。

JavaScript 代码(diff 是将物品放入桶中时产生的差异):

function f(A, B){
  let diffs = new Set();
  diffs.add(A[0]);
  diffs.add(-B[0]);
  
  for (let i=1; i<A.length; i++){
    let newDiffs = new Set();
    for (d of [...diffs]){
      newDiffs.add(d + A[i]);
      newDiffs.add(Math.abs(d + B[i]));
    }
    diffs = newDiffs;
  }
  console.log(`Diffs: ${ [...diffs] }`); 
  return Math.min(...diffs);
}

var ABs = [
  [[1, 2, 3, 4], [-1, -2, -3, -4]], // 0
  [[1, 1, 1, 3], [0, 0, 0, -3]] // 0
]

for (let [A, B] of ABs){
  console.log(`A: ${ A }`);
  console.log(`B: ${ B }`);
  console.log(`Result: ${ f(A, B) }`);
  console.log('');
}