Problema de la mochila con programación dinámica

De Wikipedia, la enciclopedia libre

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

Tabla de contenidos 1 Descripción del problema 2 Pasos de Programación Dinámica 3 Datos 4 Principio de optimalidad de Bellman 5 Ecuaciones recurrentes para el problema 6 Implementacion

[editar] Descripción del problema

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

[editar] 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.

[editar] 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)

[editar] 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 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.

[editar] Ecuaciones recurrentes para el problema

a) Ecuación hacia delante

• Supongamos que gi(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

[editar] Implementacion

• 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]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;