2

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

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!

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

2
  • I have a couple of clarifying questions. Do I understand correctly that you have X objects in each of N sets? Do you want to find 1 or more combination of objects for each of N sets or for all the sets combined? Can the objects in the combination belong to different sets? Commented Jan 22, 2015 at 20:40
  • Good question. Yes every set has X objects. I want to make 1 or more combinations with ONLY 1 object of each set combined (so if I had 5 sets, use 5 objects, one from each set). I understand that wasn't clear. Commented Jan 22, 2015 at 20:43

2 Answers 2

1

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).

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

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.

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;
}
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for the answer. From the looks of it I think it should work yes. I will try it soon!
I altered a few things to optimize it for the API I'm retrieving the data from, but the basic principle works, thanks!
0

If I understand you correct, you are looking for a power set algorithm. If so, you'll find a JavaScript implementation you can modify here: http://rosettacode.org/wiki/Power_set

1 Comment

I could indeed use that, and then check for every set if my goal is reached. The thing is if I have 5 sets of only 10 items, the power set will already get pretty huge

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.