Alex Rivera | Logout

Algorithm: Extract subset based on property sum

Asked 2012-10-09T20:23:20.830
14

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 fina

javascript algorithm
Edit
Report

1 Answer

3

This is what I call a "sort and bracket" problem. The way you solve it is by sorting the data and then bracketing around the target value or target range.

For example, in this case the sorted order is:

98
112
126
182
191
196
210
213
223
237

Now you average the list: 178.8. Therefore the starting bracket is (126,182). Start moving out from this average: sum(126,182,112,191,98) = 709, too small. Delete the 98 and replace with value from the other side: 196, ie sum(126,182,112,191,196) = 807, still too small. Go to next value on high side, sum(126,182,112,191,210)=821. Ok, found one match. By continuing this process you can find every match. Basically what bracketing does is help you search only a subset of all the possible combinations so you do not have to check every combination. You are generating combinations outward from an average, instead of from one end or the other.

Whenever your sum exceeds/falls below the range you terminate the combination generation on the high/low side and switch to the other. This is the optimal solution to the problem.

Implementation Method: to implement this algorithm you need to get a combination generator that works in "lexicographical" order. You then start with n, say 5, items and determine the median combination as I have shown above. You then get the next lower combination, if you are low, you switch to the next higher combination and so on.

-------------- ADDENDUM -------------------

After thinking about this it might be better to use a plain changes-type algorithm for this rather than a lexicographical combinator. This type of algorithm will generate all combinations, but only switch any 2 elements at a given time. Basically you modify this algorithm to switch direction whenever it goes out of bounds (goes above the range or below it).

answered 2012-10-09T21:11:05.180

Your Answer