Wikilibros

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

Ingresar texto

Plantilla:A wikilibros

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 editar

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 editar

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 editar

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 editar

  • 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 editar

  • 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 editar

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 editar

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

Otros Ejemplos De Programación Dinámica editar

Obtenido de «https://es.wikibooks.org/w/index.php?title=Programación_dinámica/Problema_de_la_mochila_con_programación_dinámica&oldid=303104»