Se tiene una mochila con una capacidad máxima V y n objetos con volúmenes \(v=(v_1,v_2,\dots,v_n)\) y beneficios \(b=(b_1,b_2,\dots,b_n)\) . Los valores de los volúmenes son enteros. El objetivo de este problema es encontrar una selección de objetos cuya suma de volúmenes no supere la capacidad máxima de la mochila, y de forma que la suma de beneficios sea máxima. Por lo tanto, es un problema de optimización con restricciones.
En esta versión del problema los objetos son indivisibles, con lo que sólo tenemos la opción de incluirlos o excluirlos. Este hecho hace que no se pueda aplicar un algoritmo voraz. Se pide que se desarrolle el programa que resuelva este problema mediante el esquema de programación dinámica.
Se tiene una mochila con una capacidad máxima de V y n objetos con volúmenes $v=(v_1,v_2,\dots,v_n)$ y beneficios b=(b_1,b_2,\dots,bn) . Los valores de los volúmenes son enteros. El objetivo de este problema es encontrar una selección de objetos cuya suma de volúmenes no supere la capacidad máxima de la mochila, y de forma que la suma de beneficios sea máxima. Este es un problema de optimización con restricciones que se puede plantear de la siguiente forma:
\[maximizar \sum_{i=0}^{n} x_ib_i \mbox{ cumpliendo } \sum_{i=0}^{n} x_iv_i \leq V\]donde \(x_i\) toma el valor \(0\) ó \(1\), \(0\) para indicar que el objeto \(i\) no se incluye en la mochila y \(1\) para indicar lo contrario.
Para la resolución de este problema se utiliza el esquema de programación dinámica.
Se formula el problema de forma incremental, planteando las ecuaciones recursivas para una función \(mochila(i,W)\) que da el máximo beneficio para un volumen \(W\) que queda libre en la mochila considerando los objetos entre \(1\) e \(i\), siendo \(i\leq n\). Cuando se pasa a considerar el objeto \(i\) se tienen dos posibilidades: que el objeto exceda de la capacidad de la mochila o quepa en ella. El primer caso se prueba con el resto de objetos. En el segundo caso se tienen también dos opciones: o bien se incluye, con lo que el beneficio bi se añade al valor de la función, y el volumen \(v_i\) se resta del espacio libre, o bien no se incluye, con lo que se tiene que resolver el problema considerando la serie de objetos entre \(1\) e \(i−1\) . Se queda con el que maximice el beneficio total. Los casos base del problema se presentan cuando la capacidad de la mochila llega a \(0\) , o cuando no queda ningún objeto. En estos casos, el beneficio es \(0\). También se pueden considerar casos para configuraciones no válidas a las que se puede llegar si se excede la capacidad de la mochila. Este caso se designa con el valor especial "\(−\inf\)", que es superado por el beneficio de cualquier configuración válida. Por tanto, las ecuaciones de concurrencia del problema son:
\[mochila(i,W) = \begin{cases}0 & \mbox{si } i = 0 \mbox{ y } W \geq 0 \\-\infty & \mbox{si } W ‹ 0 \\mochila(i-1,W) & \mbox{si } i › 0 \mbox{ y } v_i > W \\max\{mochila(i-1,W), b_i + mochila(i-1,W-v_i) \} & \mbox{si } i › 0 \mbox{ y } v_i \leq W\end{cases}\]Para resolver el problema se construye una tabla \(M[n,V]\) con tantas filas como objetos y tantas columnas como indique el volumen \(V\). Para calcular la posición \(M[i,j]\) se necesita haber calculado dos de las posiciones de la linea anterior. Por tanto se construye la tabla por filar y el valor \(M[n,V]\) de la última fila da la solución al problema.
Para que el algoritmo indique qué objetos hay que seleccionar para obtener el beneficio máximo, se puede llamar a una función que tenga como datos de entrada la tabla construida y los volúmenes de los objetos, y de cómo salida un vector objetos de ceros y unos, en el que un uno significa que hay que incluir el objeto para obtener el beneficio máximo. Esta función, empezando por la ultima casilla de la tabla, va comprobando a cada paso si el valor de la casilla coincide con el de la casilla de la fila superior, lo que indica que no se ha incluido el objeto i. Si no coinciden se sabe que el objeto se ha incluido y se pasa a comprobar la casilla correspondiente a la reducción de volumen que ha supuesto incluir el objeto.
El coste computacional de este algoritmo está en \(O(nV)\), por los dos bucles anidados para la construcción de la tabla. Asimismo, el método de obtención de los objetos contenidos en la mochila tiene un coste de \(O(n)\) por el bucle de recorrer todos los los objetos.
La utilización de un algoritmo voraz consiste en introducir en la mochila según orden decreciente de utilidad (beneficio) los diversos objetos. En una primera etapa, se adicionarán unidades enteras hasta que, por motivo de capacidad, no sea posible seguir introduciendo enteros y haya que añadir la porción que quepa del siguiente objeto. Al ser objetos que no se pueden dividir en porciones, el uso de un algoritmo voraz no es aplicable a este problema.
En la zona de visualización podrás ver cómo funciona y cómo se construye la tabla. Introduce los datos de entrada (volumen y beneficio) y pulsa ACTUALIZAR. Podrás ver la evolución del algoritmo y de las estructuras de datos utilizadas utilizando los botones de control superiores