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;
[download]