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.
UPDATE
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:
package Algorithm::Knapsack::Fixed; use strict; use warnings; use Exporter; our @ISA = qw(Exporter); our @EXPORT_OK = qw(calculate); sub calculate { my($target, $number, $arrayref) = @_; my @counters = (0..($number - 1)); my @array = @{$arrayref}; my @results; my $endpoint = $#array - $#counters; #sort the array in descending order but remember what the original o +rder was so we can reverse the sort # before we give back the results. If for example we find that items + 123 and 456 of the sorted array # match, we'd return $order[123] and $order[456] my @order = sort { $array[$b] <=> $array[$a] } @0 .. $#array; @array = @array[@order]; while(1) { my $sum = 0; $sum += $array[$counters[0]]; for(1..$#counters) { $sum += $array[$counters[$_]]; if(($sum > $target) && ($_ < $#counters)) { &_increment($_, \@counters, \@array); last; } } if($sum == $target) { #we've got a matching combination! push(@results, [@order[@counters]]); } if(($counters[0] == $endpoint) || (($array[$counters[0]] * ($#coun +ters + 1)) < $target)) { return @results; } if($sum < $target) { &_increment(($#counters - 1), \@counters, \@array); next; } &_increment($#counters, \@counters, \@array); } } sub _increment { my($counter, $countersref, $arrayref) = @_; $countersref->[$counter]++; while(($countersref->[$counter] > $#$arrayref - ($#$countersref - $c +ounter)) && ($counter > 0)) { $counter--; $countersref->[$counter]++; } if($counter < $#$countersref) { foreach my $counter2 (($counter + 1)..$#$countersref) { $countersref->[$counter2] = $countersref->[$counter] + $counte +r2 - $counter; } } } 1;
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...
|
---|
Replies are listed 'Best First'. | |
---|---|
Re: finding values in an array that add up to a specific number
by dave_the_m (Monsignor) on Jul 26, 2005 at 23:25 UTC | |
Re: finding values in an array that add up to a specific number
by halley (Prior) on Jul 26, 2005 at 23:15 UTC | |
Re: finding values in an array that add up to a specific number
by dynamo (Chaplain) on Jul 26, 2005 at 22:54 UTC | |
Re: finding values in an array that add up to a specific number
by tomazos (Deacon) on Jul 27, 2005 at 00:42 UTC | |
Re: finding values in an array that add up to a specific number
by Solo (Deacon) on Jul 26, 2005 at 23:10 UTC | |
Re: finding values in an array that add up to a specific number
by GrandFather (Saint) on Jul 27, 2005 at 00:22 UTC | |
Re: finding values in an array that add up to a specific number
by Anonymous Monk on Jul 27, 2005 at 09:17 UTC | |
Re: finding values in an array that add up to a specific number
by TedPride (Priest) on Jul 27, 2005 at 07:46 UTC |