Práctica: Memoización de un Divide y Vencerás

El problema de la mochila 0-1 se enuncia asi: Se tiene una mochila de de capacidad $C$ y $N$ objetos de pesos $w_k$ y beneficios $p_k$ . Se trata de encontrar la combinación óptima de objetos que caben en la mochila y producen el máximo beneficio.

Denotemos por $knap_{k,c,b}$ el valor óptimo de la solución para el subproblema considerando los objetos $\{1, \ldots k\}$ , capacidad $c$ y beneficio inicial $b$ . El problema consiste en encontrar el valor de $knap_{N,C,0}$ . Se cumple la siguiente fórmula:

$$knap_{k,c,b} = \max \{ knap_{k-1,c,b}, knap_{k-1,c-w_k,b+p_k} \}$$ (4.1)

si $c > w_k$ y $knap_{\emptyset, c,b} = b$ en otro caso.

Esta fórmula nos dice que la solución para el problema $knap_{k,c,b}$ con objetos $\{1, \ldots k\}$ puede obtenerse a partir de las soluciones de los dos subproblemas de mochila con objetos $\{1, \ldots k-1\}$ que resultan de tomar las decisiones de incluir o no el objeto $k$ .

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.010s

El 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:

1. ¿Cual es el tamaño del árbol de búsqueda explorado por knap para un problema de la mochila con $N$ objetos?. La pregunta se refiere al peor caso posible.
2. Para una mochila de capacidad $C$ y $N$ objetos de pesos $w_k$ y beneficios $p_k$ ¿Cuál es el máximo cardinal del conjunto de ternas de entrada (k, c, b) de la subrutina knap? ¿Que valor es mayor. Este o el calculado en el apartado anterior?
3. Memoize usando el módulo 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?
4. Memoize manualmente la función knap. Use el módulo Benchmark para comparar los rendimientos de las tres versiones.