javascript - Algorithm: Extract subset based on property sum

Question

I want an algorithm (no specific language) to find a subset from a set of integers such that their sum is within a certain range.

For example, if I have a group of people, whose weights are as follows.

var people:{
   jane:126,
   julia:112,
   charles:98,
   john:182,
   bob:213,
   edgar: 237,
   jay: 223,
   dan: 191,
   alex: 210,
   david: 196
}

Now, from these people, I'd like to find a subset whose combined weight is between 818-822 pounds (If you're trying to do the math... don't bother, these numbers are out of my head, and I don't even know if there's a solution with this dataset). The number of people in the group doesn't matter, just a group from the larger set. And really, any group will do (although random is better in my case).

Note that this is just a quick example... there would actually be hundreds of people, and it would be possible that there would be no combination that would fit into this criteria. Because the actual numbers would be much larger than this, I'm concerned about a n^n problem and running through thousands of iterations, even though I need this to run very quickly.

Maybe I fell asleep during that day in computer science class, but I haven't been able to come up with anything other than brute force methods.

I've tagged this as javascript, simply because that is closest to my actual implementation (and it reads easier). Open to other solutions, as long as they aren't predicated on some Cthulhu function somewhere.

I know this is a weird question to ask on SO, but any help here would be appreciated.

---

Ok, I'm stumped. 23 hours to post a bounty for something that I can grok code-wise -- my background is certainly not in this realm, and I have a hard time even discerning the notations used to describe the problem, let alone the solutions.

Anybody want to help me out and throw me some sample javascript code that I can modify to the final project? I'll be adding a 250pt bounty when I can... but if a decent solution comes through I'll hand it out when the time comes.

Answer 1

This is similar to 0-1 Knapsack problem or Subset sum problem.

If weights are not very large integer numbers, a dynamic programming solution should be efficient.

---

Here is javascript implementation of dynamic programming algorithm. If you want random groups, just random shuffle the list of people before applying this algorithm.

var p = {
   jane:126,
   julia:112,
...
};

function subset(people, min, max)
{
  var subsets = [];
  subsets[0] = '';

  for (var person in people)
  {
    for (var s = min-1; s >= 0; --s)
    {
      if (s in subsets)
      {
        var sum = s + people[person];

        if (!(sum in subsets))
        {
          subsets[sum] = subsets[s] + ' ' + person;

          if (sum >= min && sum <= max)
          {
            return subsets[sum];
          }
        }
      }
    }
  }

  return 'Not found';
}

print(subset(p, 818, 822));