El Problema de la Mochila 0-1

El problema de la mochila 0-1 se enuncia asi: Se tiene una mochila de de capacidad $M$ 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.

Para resolverlos denotemos por $f_k(c)$ el beneficio óptimo obtenido usando los primeros $k$ objetos y una mochila de capacidad $c$ . Entonces $f_0(c) = p_0$ si $c \ge w_0$ y 0 en otro caso. Además

$$f_k(c) = \max \{ f_{k-1}(c), f_{k-1}(c-w_k)+p_k \}$$ (5.1)

si $c > w_k$ y $f_k(c) = f_{k-1}(c)$ en otro caso.

El esquema del algoritmo es:

 1	  for my $c (0..$M) {
 2	    $f[0][$c] = ($w[0] <= $c)? $p[0] : 0;
 3	  }
 4	
 5	  for my $k (1..$N-1) {
 6	    for my $c (0..$M) {
 7	      my $n = $f[$k-1][$c];
 8	      if ($c >= $w[$k]) {
 9	        my $y = $f[$k-1][$c-$w[$k]]+$p[$k];
10	        $f[$k][$c] = ($n < $y)? $y : $n;
11	      }
12	      else { $f[$k][$c] = $n; }
13	    }
14	  }

En las líneas 1-3 inicializamos la tabla @f. Después aparecen dos bucles anidados: el primero en los objetos y el segundo en las capacidades. Las líneas 8-11 no son mas que la transcripción de la ecuación de estado 5.1.