view release on metacpan or  search on metacpan

lib/Algorithm/Knap01DP.pm  view on Meta::CPAN

package Algorithm::Knap01DP;
use 5.008004;
use strict;
use warnings;
use Carp;
use IO::File;

our $VERSION = '0.25'; 
# Still a very early "alpha" version

sub new {
    my $class = shift;
    my $self = {
        capacity    => 0,       # total capacity of this knapsack
        numobjects  => 0,       # number of objects
        weights     => [],      # weights to be packed into the knapsack
        profits     => [],      # profits to be packed into the knapsack
        tableval    => [],      # f[k][c] DP table of values
        tablesol    => [],      # x[k][c] DP table of sols 
                                # (0 = out, 1 = in, 2 = in and out)
        solutions   => [],      # list of lists of object indexes 
        filename    => "",      # name of the file the problem was read from
        @_,
    };
    
    croak "Profits and Weights don't have the same size" 
           unless scalar(@{$self->{weights}}) == scalar(@{$self->{profits}});

    bless $self, $class;
}

sub Knap01DP {
  my $self = shift();
  my $M = $self->{capacity};
  my @w = @{$self->{weights}};
  my @p = @{$self->{profits}};

  croak "Weight list is empty" unless (@w > 0);

  my $N = @w;
  my (@f, @x);

  for my $c (0..$M) {
    if ($w[0] <= $c) {
      $f[0][$c] = $p[0];
      $x[0][$c] = 1;
    }
    else {
      $f[0][$c] = 0;
      $x[0][$c] = 0;
    }
  }

  for my $k (1..$N-1) {
    for my $c (0..$M) {
      my $n = $f[$k-1][$c];
      if ($c >= $w[$k]) {
        my $y = $f[$k-1][$c-$w[$k]]+$p[$k];
        if ($n < $y) {
          $f[$k][$c] = $y;
          $x[$k][$c] = 1;
        }
        elsif ($n > $y) { 
          $f[$k][$c] = $n;
          $x[$k][$c] = 0;
        }
        else { # $n == $y
          $f[$k][$c] = $n;
          $x[$k][$c] = 2; # both ways
        }
      }
      else { 
        $f[$k][$c] = $n; 
        $x[$k][$c] = 0; 
      }
    }
  }
  ($self->{tableval}, $self->{tablesol}) = (\@f, \@x);
}

sub solutions {
  my $self = shift();
  my $N = $self->{numobjects};
  my $M = $self->{capacity};
  my @w = @{$self->{weights}};
  my (@f, @x);

  $self->Knap01DP() if (!@{$self->{tableval}});
  @f = @{$self->{tableval}};