Pr Dinamica2

Programación dinámica:
Introducción


Recordemos el problema de la
mochila:
– Se tienen n objetos fraccionables y una
mochila.
– El objeto i tiene peso pi y una fracción xi
(0≤xi≤1) del objeto i produce un beneficio
bixi.
maximizar
b
i ximochila, de capacidad
– El objetivo
es llenar
la
1i n
C, de manera que se maximice el beneficio.

sujeto a  pi xi C
1i n

con 0xi 1, bi  0, pi  0,1i n



Una variante: la “mochila 0-1”
– xi sólo toma valores 0 ó 1, indicando que el
objeto se deja fuera o se mete en la mochila.
– Los pesos, pi, y la capacidad son números
naturales.
Los beneficios, bi, son reales no negativos.

Programación dinámica:
Introducción


Ejemplo:
n=3
C=15
(b1,b2,b3)=(38,40,24)
(p1,p2,p3)=(9,6,5)



Recordar la estrategia voraz:
– Tomar siempre el objeto queproporcione
mayor beneficio por unidad de peso.
– Se obtiene la solución:
(x1,x2,x3)=(0,1,1), con beneficio 64
– Sin embargo, la solución óptima es:
(x1,x2,x3)=(1,1,0), con beneficio 78



Por tanto, la estrategia voraz no
calcula la solución óptima del
problema de la mochila 0-1.

Programación dinámica:
Introducción
R. Bellman: Dynamic Programming,
Princeton University Press, 1957.
Técnica de programación dinámica
– Se emplea típicamente para resolver
problemas de optimización.
– Permite resolver problemas mediante una
secuencia de decisiones.
Como el esquema voraz
– A diferencia del esquema voraz, se producen
varias secuencias de decisiones y sólamente
al
final se sabe cuál es la mejor de ellas.
– Está basada en el principio de optimalidad
de Bellman:
“Cualquier subsecuencia dedecisiones
de una secuencia óptima de decisiones
que resuelve un problema
también debe ser óptima respecto al
subproblema que resuelve.”

Programación dinámica:
Introducción
– Supongamos que un problema se resuelve
tras tomar un secuencia d1, d2, …, dn de
decisiones.
– Si hay d opciones posibles para cada una
de las decisiones, una técnica de fuerza
bruta exploraría un total de dn secuenciasposibles de decisiones (explosión
combinatoria).
– La técnica de programación dinámica evita
explorar todas las secuencias posibles por
medio de la resolución de subproblemas de
tamaño creciente y almacenamiento en
una tabla de las soluciones óptimas de
esos subproblemas para facilitar la
solución de los problemas más
grandes.

El problema de la
mochila 0-1


Sea mochila(k,l,P) el problema:
lmaximizar  bi xi
i k

l

sujeto a  pi xi P
i k

con xi {0,1}, k i l

– El problema de la mochila 0-1 es
mochila(1,n,C).

El problema de la
mochila 0-1


Ecuación de recurrencia hacia
adelante:


g
j (c)
– Si            es el beneficio (o ganancia total)



de una
gj (c) max gj1(c), gj1(c  pj )  bj

solución
óptima de mochila(j,n,c), entonces





dependiendo de que elobjeto j-ésimo
entre o no en la solución (nótese que sólo
puede entrar si

c-pj≥0).
g
c
n1(c) 0, para cualquier capacidad
– Además,
v
g1(C)
Ambas ecuaciones permiten calcular            ,
que es el valor de una solución óptima de
mochila(1,n,C).

(Nótese que la ecuación de recurrencia es
hacia adelante pero el cálculo se realiza hacia atr

El problema de la
mochila 0-1


Ecuación derecurrencia hacia
atrás:

g
j (c)
– Si             es el beneficio (o ganancia total)



de g
una
j (c) max gj 1(c), gj 1(c  pj ) bj

solución
óptima de mochila(1,j,c), entonces





dependiendo de que el objeto j-ésimo
entre o no en la solución (nótese que sólo
puede entrar si
c-pj≥0).
g0(c)  0, para cualquier capacidad
c

– Además,
w
gn(C)
Ambas ecuaciones permitencalcular            ,
que es el valor de una solución óptima de
mochila(1,n,C).

(Ahora la recurrencia es hacia atrás pero el cálcul
se realiza hacia adelante.)

El problema de la
mochila 0-1


Tanto la recurrencia hacia adelante como
hacia atrás permiten escribir un algoritmo
recursivo de forma
inmediata.
función mochila1(p,b:vector[1..n] de nat;
función mochila1(p,b:vector[1..n] de nat;...