El problema de la mochila (knapsack problem) es el siguiente problema de optimización combinatoria:
Dado un conjunto de elementos, cada uno con un peso y un valor, determinar qué elementos incluir en la colección para que el peso total sea menor o igual a un límite dado y el valor total sea el mayor posible.
El problema más sencillo (0-1 knapsack problem) es aquel en el que se restringe el número de copias de cada item a cero o uno.
Si n es el número de items numerados de 1 a n, cada uno con un peso wi y un valor vi, con una capacidad máxima de peso W, se trata de maximizar:
$$\sum_{i=1}^n v_ix_i$$
con la restricción:
$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in \{ 0,1 \}$$
El problema de la mochila acotada (BKP) elimina la restricción de que solo exista un ejemplar de cada artículo, pero restringe el número xi de copias de cada tipo de artículo a un valor entero máximo no negativo c. Por tanto la restricción es:
$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in \{ 0,1 \dots c\}$$
El problema de la mochila ilimitada (UKP) no impone un límite superior al número de copias de cada tipo de artículo y la única restricción de xi es que sea un número entero no negativo:
$$\sum_{i=1}^n w_ix_i \leq W \hspace{0.2 cm} si \hspace{0.2 cm} x_i\in N$$
Vamos a resolver un ejemplo mediante programación dinámica:
Sean 5 objetos con los valores vi y pesos wi que se muestran en la Figura. Los pesos posibles en la mochila van desde 0 al máximo permitido de W=8 .
Se establece una matriz M[i,j] donde cada elemento indica el beneficio máximo de llevar una mochila de peso j con objetos desde x1 hasta xi.
La primera fila de ceros corresponde a no meter ningún objeto en la mochila y la primera columna de ceros indica mochila de tamaño cero que no admite ningún objeto.
Analicemos el funcionamiento observando las celdas coloreadas. La matriz se va completando de izquierda a derecha y de arriba a abajo. Si estamos en la celda M[3,5]=7, retrocedemos 4 posiciones hasta la celda M[2,0]=0 ya que w3=4; ahora hacemos el cálculo siguiente:
$$M[3,1]+v_3=0+10=10>M[3,5]=7 \rightarrow M[4,5]=10$$
La celda M[5,5] también vale 10 porque una mochila de peso máximo 4 no admite un objeto de peso 5.
La celda M[6,8] repite el valor 16 pues el valor que se obtiene (15) es menor que el de su celda superior.
El valor más alto de la última columna (19) indica el valor máximo.
Vamos a obtener los objetos con los que se consigue el valor máximo:
Al ser M[6,9]=M[5,9] el objeto W5=7 no se pone en la mochila. Como M[5,9]>M[4,9] el objeto w4=5 se pone en la mochila.
Retrocedemos 5 posiciones a M[4,4] y siguiendo el mismo razonamiento no ponemos el objeto w3=4 y si ponemos el objeto w2=3. Continuando el proceso se llega a M[2,1]=0 y finaliza rl proceso.
Se han colocado en la mochila el objeto w2=3, v2=5 y el objeto w4=5, v4=14.
