Se tiene una mochila de de capacidad y objetos de pesos y beneficios . Se trata de encontrar la combinación óptima de objetos que caben en la mochila y producen el máximo beneficio.
Denotemos por el valor óptimo de la solución para el subproblema considerando los objetos y capacidad . El problema consiste en encontrar el valor de . Se cumple la siguiente fórmula:
Esta fórmula nos dice que la solución para el problema con objetos puede obtenerse a partir de las soluciones de los dos subproblemas de mochila con objetos que resultan de tomar las decisiones de incluir o no el objeto .
En esta sección presentamos un programa que usa threads dispuestas en pipeline para resolver el problema.
lhp@nereida:~/Lperl/src/threads$ cat knap.dat 8 102 2 15 20 100 20 90 30 60 40 40 30 15 60 10 10 1 N=8, M = 102 weight 0 profit 0 ... N=8, M = 102 weight 0 profit 0 ... Example 2.1 pag 20 Martello and Toth sol 280
Al ejecutar el programa se muestra la solución:
lhp@nereida:~/Lperl/src/threads$ pipeknap2.pl knap.dat sol = 280 lhp@nereida:~/Lperl/src/threads$
El programa principal se limita a cargar las librerías y crear el pipeline de threads:
lhp@nereida:~/Lperl/src/threads$ cat -n pipeknap2.pl 1 #!/usr/bin/perl -w 2 use strict; 3 use threads; 4 use Thread::Queue; 5 use threads::shared; 6 use Carp; 7 use IO::File; 8 9 ### main 10 my ($M, $w, $p) = ReadKnap($ARGV[0]); 11 my $N = @$w; 12 13 &pipe($N, \&knap, $M, $w, $p);El primer argumento
$N
de pipe
es el número de threads,
el segundo la subrutina a ejecutar por la thread. En este caso una referencia
a la subrutina knap
. Los restantes argumentos son argumentos
pasados a la subrutina que ejecuta la thread. En este caso:
$M
es la capacidad de la mochila
$w
es una referencia a la lista de pesos
$p
es una referencia a la lista de beneficios (profits)
La subrutina auxiliar ReadKnap
lee un fichero conteniendo una descripción
del problema de la mochila:
79 sub ReadKnap { 80 my $filename = shift; 81 82 my $file = IO::File->new("< $filename"); 83 croak "Can't open $filename" unless defined($file); 84 my (@w, @p); 85 86 my $N = <$file>; 87 my $M = <$file>; 88 for (0..$N-1) { 89 $w[$_] = <$file>; 90 $p[$_] = <$file>; 91 } 92 return ($M, \@w, \@p); 93 }
$k
. Coincide con el índice del objeto del
que se encarga la tarea. Por tanto esta tarea $k
se encarga de computar los valores óptimos
para todo
los
cuales son almacenados en la lista privada @f
$from_left
que le comunica con el hilo encargado del
cómputo de
para todo
$to_right
que le comunica con el hilo encargado del
cómputo de
para todo
$M
, la lista de pesos @w
y la lista de beneficios @p
40 sub knap { 41 my $k = shift(); 42 my $from_left = shift(); 43 my $to_right = shift(); 44 ############## 45 my $M = shift(); 46 my @w = @{shift()}; 47 my @p = @{shift()}; 48 49 my $N = @w; 50 my @f; 51 my @left; 52 53 croak "Profits and Weights don't have the same size" 54 unless scalar(@w) == scalar(@p); 55 56 for my $c (0..$M) { 57 $f[$c] = ($w[$k] <= $c)? $p[$k] : 0; 58 }Antes de empezar el cómputo se inicia la lista
@f
(i.e.
para todo
, líneas 56-58). Si el objeto
$k
cabe en una mochila de capacidad $c
se pondrá. En otro caso el valor inicial es cero.
En general, en todo pipeline hay que distinguir tres casos:
$f[$c]
-
que depende del mismo
y se envía al vecino derecho (línea 70) para que este haga lo mismo.
Este envío puede eliminarse si se trata de la última thread
$f[$M]
)
60 if ($k) { 61 for my $c (0..$M) { 62 $left[$c] = $from_left->dequeue(); 63 if ($c >= $w[$k]) { 64 my $y = $left[$c-$w[$k]]+$p[$k]; 65 $f[$c] = ($left[$c] < $y)? $y : $left[$c]; 66 } 67 else { 68 $f[$c] = $left[$c]; 69 } 70 $to_right->enqueue($f[$c]); 71 } 72 } 73 else { # thread virtual 0 74 $to_right->enqueue(@f); 75 } 76 print "sol = $f[-1]\n" if $k == ($N-1); 77 }
$N+1
canales. El canal $channel[$id+1]
comunica la thread $id
con la thread $id+1
.
$N
hilos con nombres entre 0 y $N-1
.
Además de los argumentos específicos de la tarea se le envían
17 sub pipe { # crea el pipe de tamaño N 18 my $N = shift(); # número de procesadores virtuales 19 my $task = shift(); # subrutina a ejecutar 20 my @channel : shared; # array de colas 21 my @t; # array de tareas 22 # El resto de argumentos son argumentos de $task 23 24 my $id; # identificador de procesador físico 25 26 # creamos canales ... 27 for($id=0; $id <= $N; $id++) { 28 $channel[$id] = new Thread::Queue; # canal comunicando hilos $id-1 e $id 29 } 30 # creamos threads ... 31 for($id=0; $id < $N; $id++) { 32 $t[$id] = threads->new($task, $id, $channel[$id], $channel[$id+1], @_); 33 } 34 # La thread 0 no trabaja, sólo espera ... 35 for($id=0; $id < $N; $id++) { 36 $t[$id]->join(); # join debe ser ejecutado por el padre 37 } 38 }
Puede obtener ficheros de entrada para el ejemplo en esta sección descargando el fichero knap_dat.tgz. en la página de estos apuntes.