Denotemos por el valor óptimo de la solución para el subproblema considerando los objetos , capacidad y beneficio inicial . 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 .
El siguiente programa recibe el número de objetos y genera un problema aleatorio de mochila 0-1 con ese número de objetos:
lhp@nereida:~/Lperl/src$ time ./memoizeknap.pl 20 C = 115; w = 17 18 4 14 13 13 8 16 17 15 10 9 3 14 9 3 8 15 7 18 115 real 0m3.043s user 0m3.050s sys 0m0.010sEl programa usa la ecuación 4.1 para resolver el problema. El diseño recursivo de la subrutina da lugar a un esquema divide-y-vencerás:
lhp@nereida:~/Lperl/src$ cat -n memoizeknap.pl 1 #!/usr/bin/perl -w 2 use strict; 3 use List::Util qw(max sum); 4 5 my $N = shift || 10; 6 my @w = map { 3 + int(rand($N-3)) } 1..$N; 7 my @p = @w; 8 my $C = int(sum(@w)/2); 9 10 sub knap { 11 my ($k, $c, $b) = @_; 12 my @s; 13 14 return $b if $k < 0; 15 $s[0] = knap($k-1, $c, $b); 16 if ($w[$k] <= $c) { 17 $s[1] = knap($k-1, $c-$w[$k], $b+$p[$k]); 18 } 19 return max(@s); 20 } 21 22 my $s = knap($N-1, $C, 0); 23 24 print "C = $C; w = @w\n"; 25 print "$s\n";
Responda a las siguientes preguntas:
knap
para un problema de la mochila con
objetos?.
La pregunta se refiere al peor caso posible.
(k, c, b)
de la subrutina knap
?
¿Que valor es mayor. Este o el calculado en el apartado
anterior?
Memoize
la función knap
. Use el módulo Benchmark
para comparar rendimientos. ¿Puede explicar las diferencias?
¿Como cambia el árbol de búsqueda explorado al
memoizar la función?
knap
.
Use el módulo Benchmark para comparar los
rendimientos de las tres versiones.
Casiano Rodríguez León