~/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__
Casiano Rodríguez León