si y en otro caso.
El esquema del algoritmo secuencial es:
for my $c (0..$M) { $f[0][$c] = ($w[0] <= $c)? $p[0] : 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]; $f[$k][$c] = ($n < $y)? $y : $n; } else { $f[$k][$c] = $n; } } }
En la dirección:
http://nereida.deioc.ull.es/˜lhp/perlexamples/Algorithm-Knap01DP-0.01.tar.gz.
puede encontrar una distribución de un módulo Perl que proporciona una solución secuencial.
He aqui una solución paralela:
$ cat -n pipeknap.pl 1 #!/usr/bin/perl -w -I../lib 2 # File: pipeknap.pl 3 4 use strict; 5 use threads; 6 use Thread::Queue; 7 use Carp; 8 use IO::File; 9 use Threads::Pipe qw(pipe); 10 11 ### main 12 #my ($M, $w, $p) = ReadKnap($ARGV[0]); 13 srand(27); 14 my ($M, $w, $p) = GenKnap($ARGV[0]); 15 my $N = @$w; 16 my $numthreads = ($ARGV[1] || 2); 17 18 my @f = &pipe($numthreads, $N, \&knap, $M, $w, $p); 19 20 my @Table = GetSol(@f); 21 print "Sol = $Table[-1][-1]\n"; 22 23 sub knap { 24 my $k = shift(); 25 my $from_left = shift(); 26 my $to_right = shift(); 27 ############## 28 my $M = shift(); 29 my @w = @{shift()}; 30 my @p = @{shift()}; 31 32 my $N = @w; 33 my @f; 34 my @left; 35 36 croak "Profits and Weights don't have the same size" unless scalar(@w) == scalar(@p); 37 38 if ($k) { 39 for my $c (0..$M) { 40 $left[$c] = $from_left->dequeue(); 41 if ($c >= $w[$k]) { 42 my $y = $left[$c-$w[$k]]+$p[$k]; 43 $f[$c] = ($left[$c] < $y)? $y : $left[$c]; 44 } 45 else { 46 $f[$c] = $left[$c]; 47 } 48 $to_right->enqueue($f[$c]); 49 } 50 } 51 else { # thread virtual 0 52 for my $c (0..$M) { 53 $f[$c] = ($w[0] <= $c)? $p[0] : 0; 54 } 55 $to_right->enqueue(@f); 56 } 57 return (\@f); 58 } 59 60 sub ReadKnap { 61 my $filename = shift; 62 63 my $file = IO::File->new("< $filename"); 64 croak "Can't open $filename" unless defined($file); 65 my (@w, @p); 66 67 my ($N, $M); 68 69 chomp($N = <$file>); 70 chomp($M = <$file>); 71 for (0..$N-1) { 72 $w[$_] = <$file>; 73 $p[$_] = <$file>; 74 } 75 chomp @w; 76 chomp @p; 77 $file->close(); 78 return ($M, \@w, \@p); 79 } 80 81 sub GenKnap { 82 my $N = (shift() || 10000); 83 my $R = (shift() || $N); 84 85 my ($x, $M, @w); 86 @w = map { $x = 1 + int(rand($R)); $M += $x; $x } 1..$N; 87 $M = int ($M / 2); 88 return ($M, \@w, \@w); 89 } 90 91 sub GetSol { 92 my @f = @_; 93 94 my $k = 0; 95 for my $t (@f) { 96 my $c = 0; 97 for my $fkc (@$t) { 98 $Table[$k][$c] = $fkc; 99 $c++; 100 } 101 $k++; 102 } 103 return @Table; 104 }
Casiano Rodríguez León