El problema de la mochila tiene solución como problema de programación dinámica manejado en base a un tabla en la cual cada elemento es considerado consecutivamente.
El problema también puede ser atacado generando una tabla en la que la mochila óptima para cada capacidad posible en la mochila sea generada, esta solución está modelada en base a la solución encontrada en el libro de Sedgewick sobre Algoritmos en Java y la solución propuesta en los tutoriales de TopCoder.
Solución Bottom-up con Tabla
Se puede construir una tabla de (nItems+1) filas y (capacidad+1) columnas. La fila 0 se deja como una fila sentinela (para representar consistentemente el caso en que se tiene 0 elementos y la capacidad es también de 0 en peso).
La variable j indica el número de elementos que se tiene para llenar la mochila. Wi y Vi indican el peso y valor de cada elemento.
Cada celda [nItems][capacidad] indica la solución óptima para las restricciones de peso y valor colocadas. La celda [4][5] indica el valor de la solución óptima (el máximo valor obtenido) para la mochila de 4 ítems y capacidad de peso 5.
En los libros Fundamentals of Algorithmcs de Brassard y Bratley e Introduction to the Design & Analysis of Algorithms de Levitin aparecen las reglas para llenar la tabla y obtener el contenido de la mochila óptima.
Modelos para una Solución Top-down
Sedgewick presenta una solución recursiva de programación dinámica usando memoización. El vector global maxKnown[] contiene el valor para la mochila con el peso representado por su subíndice. La generación de la mochila se hace con el vector global itemKnown[]. La solución recursiva inicia invocando la función para la capacidad de la mochila.
En la recursión, si la celda actual del vector global aparece como no calculada, se llena con llamadas recursivas para los subíndices inferiores, esto es el comportamiento estándar para una función memoizada. En este caso, se busca el mejor ítem para optimizar el valor para esta capacidad de la mochila. Recuérdese que "valor" significa aquí la preciación total de los elementos en la mochila. Hay un falla menor en la función presentada aquí y es que no encuentra solución si los ítems disponibles no llenan completamente la mochila. Para superar esta limitación se puede suplementar a la mochila con un ítem de peso uno y valor cero para asegurar una solución.
El cuerpo de esta función de memoización recursiva también podría servir de base para una implementación bottom-up: esto se haría llenando los vectores empezando en el peso 1 y subiendo hasta completar la capacidad de la mochila. Esto llena todas las celdas, mientras que la implementación basada en función memoizada sólo llena las celdas requeridas para la solución final.
El siguiente código es una solución dinámica en Java para el problema entero de la mochila:
static int knap (int c, int [] solution)
{ int i, space, m, t,
maxKnown[], itemKnown[];
itemKnown = new int [c+1];
maxKnown = new int [c+1];
// se asume que el arreglo maxKnown está lleno con ceros
for (m=1; m<=c; m++)
for (i=1; i<=n; i++)
if ( (space = m-weight[i]) >= 0 )
{ t = maxKnown[space] + profit[i];
// Dummy: wt 1, value 0
if ( t >= maxKnown[m] )
{ maxKnown[m] = t;
itemKnown[m] = i;
}
}
// el estado de solution[] es desconocido, así que se hace:
java.util.Arrays.fill (solution, 0);
for (m=c; m>0 ; m-=weight[itemKnown[m]] )
solution[itemKnown[m]]++;
return maxKnown[c];
}
