多属性子集求和算法 [英] Subset sum algorithm with multiple attributes

问题描述

我有一个我认为可以解决的子集总和问题.

I have what I believe is a subset sum problem that I could use some help with.

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

I have N sets with an X amount of objects in them. Each object has 5 integer attributes a,b,c,d and e. Now I would like to find 1 or more (probably not all because X can become rather large) combinations of objects where the sum of all a's approximates a variable A (so e.g. approximates 100 I would say 110 > sum(a) > 90), the sum of all b's approximates variable B, etc.

我可以使用一些指针来指示从哪里开始或如何做！

I could use some pointers on where to start or how to do this!

(我想用JavaScript做到这一点，但是任何伪代码都会有所帮助！)

(I would like to do it in JavaScript, but any pseudocode would be helpful!)

推荐答案

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

This is not how I would usually solve a problem of this type, but maybe you can try out something like this to get just one combination (in pseudocode).

让我们假设您可以将对象称为object [i] [j]，其中i是集合索引，而j是对象索引.总共有X ^ N个组合.

Let's assume that you can refer to objects as object[i][j], where i is the set index and j is the object index. In total, there are X^N combinations.

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个位置中每个位置的数字"是每个集合中对象的索引.我检查组合是否符合条件，并返回符合条件的第一个组合.

I have not tested it, so I am not sure whether this code works. But the general principle is correct. Every combination is represented by a number from 0 to x^N-1 (k in pseudocode). Then I present this number as a 'base X' number. The 'digit' at each of the N places is the index of an object from each set. I check whether the combination meets the criterion and return the first combination that does.

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

An update. The function below, where the matrix parameter represents N sets of X objects, returns all possible combinations of objects. If you just return the first result that meets your criterion rather than push it to allCombinations array, you'll probably get the first combination you need.

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

这篇关于多属性子集求和算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！