La programación dinámica - La mochila con objetos no fraccionables

¿Qué es la programación dinámica?

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas.

Una subestructura óptima significa que se pueden usar soluciones óptimas de subproblemas para encontrar la solución óptima del problema en su conjunto. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos tres pasos:

1. Dividir el problema en subproblemas más pequeños.
2. Resolver estos problemas de manera óptima usando este proceso de tres pasos recursivamente.
3. Usar estas soluciones óptimas para construir una solución óptima al problema original.

Los subproblemas se resuelven a su vez dividiéndolos en subproblemas más pequeños hasta que se alcance el caso fácil, donde la solución al problema es trivial.

Puedes encontrar más información en Programación dinámica.

El ejemplo de la mochila con objetos no fraccionables

Enunciado

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.

Descripción del esquema algorítmico utilizado y como se aplica al problema

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,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. 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.

Ecuaciones recursivas del problema

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 \(b_i\) 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\) y \(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 "\(-\infty\)", que es superado por el beneficio de cualquier configuración válida. Por tanto, las ecuaciones de concurrencia del problema son:

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.

El algoritmo que resuelve el problema se puede escribir de la siguiente forma:

tipo Tabla = matriz[0..n,0..V] de entero

tipo Vector = matriz[0..n] de entero

fun MochilaEntera(vol:Vector, ben:Vector, n:entero, V:entero, M:Tabla)

   var

      i,j: entero

   fvar

   para i $\leftarrow$ 1 hasta n hacer

      M[i,0] $\leftarrow$ 0

   fpara

   para j $\leftarrow$ 1 hasta V hacer

      M[0,j] $\leftarrow$ 0

   fpara

   para i $\leftarrow$ 1 hasta n hacer

      para j $\leftarrow$ 1 hasta V hacer

         si vol[i] > j entonces

            M[i,j] $\leftarrow$ M[i-1,j]

         sino

            M[i,j] $\leftarrow$ max(M[i-1,j], M[i-1, j-vol[i]] + ben [i]})

         fsi

      fpara

   fpara

ffun

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.

fun ObjetosMochila(vol:Vector, M:Tabla, n:entero, V:entero, objetos:Vector)

   var

      i,W: entero

   fvar

   W $\leftarrow$ V

   para i $\leftarrow$ n hasta 1 incremento -1 hacer

      si M[i,W] = M[i-,W] entonces

         objetos[i] $\leftarrow$ 0

      sino

         objetos[i] $\leftarrow$ 1

         W $\leftarrow$ W - vol[i]

      fsi

   fpara

ffun

Para finalizar

Este ejemplo se ha desarrollado en Java para un trabajo de la asignatura de Programación y Estructuras De Datos Avanzadas del grado en Ingeniería Informática de la UNED.

Os dejo en el siguiente enlace el código fuente y la memoria que se ha presentado para el trabajo en cuestión.

¡Nos vemos Más allá del 0 y del 1!

Atentamente:

Carlos Caride Santeiro