Siguiente:Reemplazo de EquipamientoArriba:Tutorial Anterior:Problema de la Mochila

Planteo Alternativo

Existe otra forma de formular el problema de la mochila. Esto ilustrará cuán arbitraria puede ser la definición de niveles, estado y decisiones. Además, da una visión de la flexibilidad de las reglas en programación dinámica.
Se va a trabajar con una recursividad forward (hacia adelante). Para el problema de la mochila se indexarán los niveles por w, el peso que se lleva. La decisión es determinar el último item agregado para llegar al peso w. Luego, hay sólo un estado por nivel. Sea g(w) el máximo beneficio que se puede ganar de una mochila con un peso w. Continuamos usando  y  como el peso y beneficio, respectivamente, para el item j. Lo siguiente relaciona g(w) con valores de g calculados previamente:

Intuitivamente, para tener una mochila con un peso de w, se debe terminar agregando algún item. Si se agrega el item j, terminaremos con una mochila de tamaño  disponible para ser llenada. Para ilustrar usando el ejemplo anterior:

• g(0) = 0
•  g(1) = 30 agrega item 3.
•   agrega item 1.
•   agrega item 1 o 3.
•   agrega item 1.
•   agrega 1 o 3.

Esto da un máximo de 160, lo que se gana al agregar 2 unidades del item 1 y 1 del item 3.
 

Siguiente:Reemplazo de EquipamientoArriba:Tutorial Anterior:Problema de la Mochila