|Just another Perl shrine|
finding values in an array that add up to a specific numberby Forsaken (Friar)
|on Jul 26, 2005 at 22:32 UTC||Need Help??|
Forsaken has asked for the
wisdom of the Perl Monks concerning the following question:
this is something I've been cracking my brain over but can't seem to find a decent solution for. I've done a number of searches but can't seem to come up with anything useful either. Here's the situation: I have an array of integer numbers. I need to add up a number of those integers to match a specific value. So, say for example that I have the following array: my @array = (6, 18, 12, 2, 49); I'd need some sort of method to add up x of the elements to make up number y. So for example if I were to need 2 of the integers to add up to 30, I'd need it to return that elements 1 and 2 match the description. Normally if I knew in advance that I'd only need 2 integers I'd use 2 nested foreach loops, but in this case both the x amount of integers that need to be added up as well as the final number y that needs to result from the search are variable, so I'm definitely lost here. Is there a module that could work this black magic for me? On a sidenote I also need to mention that I require all matches.
After checking each of the replies and browsing through the various pieces of information available on the whole knapsack problem, first allow me to express my earnest gratitude for all the great advice everyone has spent their time giving me. Keeping in mind the specifics of my particular situation I decided to take little bits and pieces from everywhere and came up with the following:
And it actually works, oh joy, oh joy. Perhaps this would be a good time to mention that the actual array I'm searching through contains a few thousand integers. Making a match of 2 integers can be done in less than 20 seconds. Making a match of 3....well, you're all smart people, do the math, so any advice you might wish to give me on optimizing would indeed be greatly appreciated ;-) I do intend to implement some sort of shortcircuit procedure, so that when for example searching for a combination of 6 numbers, and the first 4 already add up to more than the target value, the 4th counter would increment, cancelling out counter5 * counter6 combination checks, which might help speed things up a bit, especially if the numbers vary wildly.
minor update: fixed the while condition in _increment.
Yet another update: did a complete overhaul, steered away from OO, implemented "shortcircuit". Once again, any comments on optimization are more than welcome. Doing the same match of 2 numbers I mentioned earlier already went down from 20 seconds to 12...
Yet yet another update: made some optimizations to the calculate routine(thanks bart :-)) shaving off a lot more time.
Remember rule one...