javascript - 多属性子集求和算法

Question

我认为我有一个子集求和问题，我需要一些帮助。

我有 N 个集合，其中包含 X 个对象。每个对象有 5 个整数属性 a、b、c、d 和 e。现在我想找到 1 个或更多(可能不是全部，因为 X 可以变得相当大)对象组合，其中所有 a 的总和近似于变量 A(所以例如近似 100 我会说 110 > sum(a) > 90) ，所有b的总和近似于变量B等。

我可以使用一些关于从哪里开始或如何开始的指示!

(我想用 JavaScript 来做，但任何伪代码都会有帮助!)

Answer 1

这不是我通常解决此类问题的方式，但也许您可以尝试类似这样的方法来获得一种组合(伪代码)。

假设您可以将对象称为 object[i][j]，其中 i 是集合索引，j 是对象索引。总共有 X^N 种组合。

var result;
var sumPrevious;
for (var k = 0; k < Math.pow(x, N); k++) {
  result = [];    //array where we'll store one combination
  sumPrevious = 0;
  for (var i = 0; i < N; i++) {
    objectIndex = Math.floor((k - sumPrevious) / Math.pow(x, N-i-1));
    sumPrevious = sumPrevious + objectIndex * Math.pow(x, N-i-1);
    result[i] = object[i][objectIndex];
  }
  if (result meets your criterion) {
    return result;  //return the first result that meets the criterion, which limits the number of iterations
  }
}

我没有测试过，所以我不确定这段代码是否有效。但总的原则是正确的。每个组合都由从 0 到 x^N-1(伪代码中的 k)的数字表示。然后我将这个数字显示为“基 X”数字。 N 个位置中每个位置的“数字”是每个集合中对象的索引。我检查组合是否符合标准并返回符合标准的第一个组合。

更新。下面的函数，其中矩阵参数表示 N 组 X 对象，返回所有可能的对象组合。如果您只是返回符合条件的第一个结果而不是将其推送到 allCombinations 数组，您可能会获得所需的第一个组合。

var combinations = function(x, N, matrix) {
  var allCombinations = [];
  var result;
  var sumPrevious;
  for (var k = 0; k < Math.pow(x, N); k++) {
    result = [];    //array where we'll store one combination
    sumPrevious = 0;
    for (var i = 0; i < N; i++) {
      objectIndex = Math.floor((k - sumPrevious) / Math.pow(x, N-i-1));
      sumPrevious = sumPrevious + objectIndex * Math.pow(x, N-i-1);
      result[i] = matrix[i][objectIndex];
    }
    allCombinations.push(result);
  }
 return allCombinations;
}