查找元素索引，使它们的值相加后等于 x

Question

我有一个数组，看起来像这样：

var x = 17;
var arr = [{ value:2, quantity: 4 }, { value:8, quantity: 1 }, { value:3, quantity: 3 }];

我的问题是如何查找那些元素的索引，这些元素的值加起来等于x。在这种情况下，返回结果应为：

[1, 3, 3, 3]

当然，也可以使用[0, 0, 0, 1, 2]或[0, 0, 0, 0, 2, 2, 2]来完成，但是返回数组长度越短越好。

- Kasper Seweryn

---

数组中可能有多少个不同的项？ - Ry-

实际上没有特定的限制。arr 数组是不可预测的。 - Kasper Seweryn

https://en.wikipedia.org/wiki/Knapsack_problem - Ry-

Answer 1

有更高效的方法来做这件事，但这是一个非常明显/干净的解决方案。我们将把它视为一个线性方程，其中combo包含arr中每个值的系数：

// your initial x and arr
var x = 17;
var arr = [{ value:2, quantity: 4 }, { value:8, quantity: 1 }, { value:3, quantity: 3 }];

// maximums[i] is the maximum amount of arr[i]'s you can ever
// have in any combination
var maximums = arr.map(function(item){ return Math.floor(x / item.value) });

// an array of the current coefficients we're trying. combo[i]
// corresponds to the coefficient for arr[i]
// we will start off with all coefficients set to 0 and
// increase each one by 1 as we go along
var combo = arr.map(function(){ return 0 });

// the sum we get with the current coefficients
var sum = 0;

// take the current coefficients in combo and try the next
// coefficient from left-to-right, we know when to stop
// trying to increase a given coefficient when it exceeds
// its corresponding value in the maximums array
function next() {
  for(var i = 0; i < combo.length; i++) {
    combo[i]++;
    // we increased the coeff. so increase the sum
    sum += arr[i].value;
    if(combo[i] <= maximums[i]) {
      // the coefficient is smaller/equal to its max size, so we're done
      break;
    }else{
      // we've maxed out the right most coeff. so bail
      if(i == combo.length-1) return false;
      // reset this coefficient, remove it from sum & cont. loop
      sum -= arr[i].value * combo[i];
      combo[i] = 0;
    }
  }
  return true;
}

// now we just enumerate all combinations until the sum equals x
while(next()) {
  if(sum == x) break;
}

// if no combination is found, abort
if(sum != x) {
  console.log('not possible');

// otherwise print the combination that works
}else{
  for(var i = 0; i < combo.length; i++) {
    if(combo[i] == 0) continue;
    console.log(combo[i] + ' of (' + JSON.stringify(arr[i]) + ')');
  }
}

如果您总是想要最小可能的组合，可以这样做：

function coeffsUsed() {
  var count = 0;
  for(var i = 0; i < combo.length; i++) {
    if(combo[i] > 0) count++;
  }
  return count;
}

// now we just enumerate all combinations until the sum equals x
var smallestCombo = {};
var smallest = -1;
while(next()) {
  if(sum == x) {
    var count = coeffsUsed();
    if(smallest == -1 || count < smallest) {
      smallest = count;
      smallestCombo = combo.slice(0); // clones the array
    }
  } 
}

// if no combination is found, abort
if(smallest == -1) {
  console.log('not possible');

// otherwise print the combination that works
}else{
  for(var i = 0; i < smallestCombo.length; i++) {
    if(smallestCombo[i] == 0) continue;
    console.log(smallestCombo[i] + ' of (' + JSON.stringify(arr[i]) + ')');
  }
}

- David Zorychta