多属性子集求和算法

Question

我认为我有一个子集和问题，我可以使用一些帮助。

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

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

（我想在 JavaScript 中完成，但任何伪代码都会有所帮助！）

Answer 1

如果我的理解是正确的，那么您正在寻找幂集算法。如果是这样，您将找到一个 JavaScript 实现，您可以在此处修改：http://rosettacode.org/wiki/Power_set

Answer 2

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

假设您可以将对象称为对象[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）的数字表示。然后我将这个数字显示为 'base X' 数字。 N 个位置中每个位置的 'digit' 是每个集合中对象的索引。我检查组合是否符合标准，return 第一个符合标准的组合。

更新。下面的函数，其中矩阵参数表示N组X对象，returns所有可能的对象组合。如果您只是 return 第一个符合条件的结果而不是将其推送到 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;
}

多属性子集求和算法

Subset sum algorithm with multiple attributes

javascript

math