El Módulo

A continuación comentamos los contenidos del módulo:

~/Lperl/src/threads/knapsack/Algorithm-Knap01DP/lib/Algorithm$ cat -n Knap01DP.pm
     1  package Algorithm::Knap01DP;
     2  use 5.008004;
     3  use strict;
     4  use warnings;
     5  use Carp;
     6  use IO::File;
     7
     8  use Exporter; # Warning!! h2xs generated a require Exporter;
     9  our @ISA = qw(Exporter);
    10  our @EXPORT_OK = qw/Knap01DP ReadKnap/;

Exportamos las funciones Knap01DP y ReadKnap sólo bajo demanda.

    11  our $VERSION = '0.01';
    12  # Still a very early "alpha" version
    13
    14  sub Knap01DP {
    15    my $M = shift;
    16    my @w = @{shift()};
    17    my @p = @{shift()};
    18
    19    my $N = @w;
    20    my @f;
    21
    22    croak "Profits and Weights don't have the same size" 
                                  unless scalar(@w) == scalar(@p);
    23
    24    for my $c (0..$M) {
    25      $f[0][$c] = ($w[0] <= $c)? $p[0] : 0;
    26    }
    27
    28    for my $k (1..$N-1) {
    29      for my $c (0..$M) {
    30        my $n = $f[$k-1][$c];
    31        if ($c >= $w[$k]) {
    32          my $y = $f[$k-1][$c-$w[$k]]+$p[$k];
    33          $f[$k][$c] = ($n < $y)? $y : $n;
    34        }
    35        else { $f[$k][$c] = $n; }
    36      }
    37    }
    38    return @f;
    39  }
    40
    41  sub ReadKnap {
    42    my $filename = shift;
    43
    44    my $file = IO::File->new("< $filename");
    45    croak "Can't open $filename" unless defined($file);
    46    my (@w, @p);
    47
    48    my $N = <$file>; chomp($N);
    49    my $M = <$file>; chomp($M);
    50    for (0..$N-1) {
    51      $w[$_] = <$file>;
    52      $p[$_] = <$file>;
    53    }
    54    chomp @w; chomp @p;
    55    return ($M, \@w, \@p);
    56  }
    57
    58  1;
    59  __END__