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 order 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]] * ($#counters + 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 - $counter)) && ($counter > 0)) { $counter--; $countersref->[$counter]++; } if($counter < $#$countersref) { foreach my $counter2 (($counter + 1)..$#$countersref) { $countersref->[$counter2] = $countersref->[$counter] + $counter2 - $counter; } } } 1;