Programación dinámica/Problema de la mochila con programación dinámica

El presente artículo se encuadra en la Programación dinámica (computación). Para otros enfoques de la Programación dinámica ver Programación dinámica (investigacición operativa)

ALGORITMO DE LA MOCHILA - PROGRAMACIÓN DINÁMICA

Programación Dinámica

Según el contexto, Programación dinámica puede referirse a:

• Un procedimiento que intenta resolver problemas disminuyendo su coste computacional aumentando el coste espacial. Programación dinámica(computación)= [1]
• Un procedimiento que intenta optimizar una función objetivo, en problemas no lineales, discretizables, y secuenciales. Programación dinámica(investigación operativa) = [2]

Descripción del problema

Sea n objetos no fraccionables de pesos pi y beneficios bi. El peso máximo que puede llevar la mochila es C. Queremos llenar la mochila con objetos, tal que se maximice el beneficio.

Pasos de Programación Dinámica

Los pasos que vamos a seguir son los siguientes:

• Ver que se cumple el principio de optimalidad de Bellman.
• Buscar ecuaciones recurrentes para el problema.
• Construir una tabla de valores a partir de las ecuaciones.

Datos

• n objetos con pesos pi y beneficios bi asociados a cada objeto.
• No se pueden fraccionar los objetos (se cogen o no se cogen).
• Se define un problema más general en función del número de objetos y la capacidad C de la mochila: mochila(k,l,C)
• Resolver el problema consiste en obtener: mochila(1,n,C)

Principio de optimalidad de Bellman

• Cualquier subsecuencia de decisiones de una secuencia óptima de decisiones que resuelve un problema también debe ser óptima respecto al subproblema que se resuelve.
• Sea y1,…,yn una secuencia óptima de valores 0-1 para x1,…,xn.
  • Si y1=0, entonces y2,…,yn forman una secuencia óptima para el problema mochila(2, n, C).
  • Si y1=1, entonces y2,…,yn forman una secuencia óptima para el problema mochila(2, n, C - p1).

• Demostración: Si existe una solución mejor para el problema correspondiente, entonces es mejor que para el problema mochila(1, n, C), en contra de la hipótesis. Lo mismo se cumple en cualquier etapa de decisión.

Ecuaciones recurrentes para el problema

a) Ecuación hacia delante

• Supongamos que gj(C) es el beneficio acumulado para la solución óptima del problema mochila(j,n,C), entonces:

    gj(C)= max {gj+1(C), gj+1(C-pj)+bj} 

cuyo significado:

    gj+1(C) -> no se coge el objeto j 
    gj+1(C-pj)+bj -> se coge el objeto j 

• El caso trivial se da cuando j vale n+1, y en este caso:

    gn+1(C) = 0

• Luego el cálculo de mochila(1,n,C) se reduce a la aplicación de las ecuaciones:

    gj(C) = max  {gj+1(C), gj+1(C-pj)+bj} si j<>n+1
    gj(C) = 0 si j = n+1 

b) Ecuación hacia atrás

• Supongamos que gj(C) es el beneficio acumulado para la solución óptima del problema mochila(1,j,C), entonces:

    gj(C)= max {gj-1(C), gj-1(C-pj)+bj}

cuyo significado:

    gj-1(C) -> no se coge el objeto j
    gj-1(C-pj)+bj -> se coge el objeto j

• El caso trivial se da cuando j vale 0, y en este caso:

     g0(C) = 0

• Luego el cálculo de mochila(1,n,C) se reduce a la aplicación de las ecuaciones:

    gj(C) = max  {gj-1(C), gj-1(C-pj)+bj} si j<>0 
    gj(C) = 0 si j = 0

Implementación

• Si consideramos la ecuación hacia atrás, la implementación nos quedará:

 proc mochila(p,b:vector[1..n] de nat,cap: nat,g: vector[0..n, 0..cap] de nat)
        var c,j: nat;
               para c=0 hasta cap hacer g[0,c]=0 fpara;
               para j=1 hasta n hacer g[j,0]=0 fpara;
               para j=1 hasta n hacer
                       para c=1 hasta cap hacer
                               si c<p[j] entonces 
                                   g[j,c]=g[j-1,c];
                               en caso contrario
                                   si g[j-1,c]$\geq \;$g[j-1,c-p[j]]+b[j] entonces 
                                       g[j,c]=g[j-1,c];                             
                                   en caso contrario
                                       g[j,c]=g[j-1,c-p[j]]+b[j];
                                   fsi;
                               fsi;
                       fpara;
                fpara;
 fproc;

Otros Ejemplos De Programación Dinámica

• Ejecución de n tareas en tiempo mínimo en un sistema de dos procesadores A y B
• Programas en disco
• Problema de los sellos con programación dinámica
• Programación dinámica/Problema de la mochila con programación dinámica
• Problema del producto de una secuencia de matrices con programación dinámica
• Problema de las monedas con programación dinámica
• Camino de coste mínimo entre dos nodos de un grafo dirigido
• Problema de la división de peso
• Problema de las vacas con programación dinámica
• Problema del Cambio de Palabra programación dinámica en JAVA