Siguiente:Planteo AlternativoArriba:Tutorial Anterior:Características Comunes

El Problema de la Mochila.

El problema de la mochila es un tipo particular de programción entera con sólo una restricción. Cada item que puede ir en la mochila tiene un tamaño y un beneficio asociado. La mochila tiene una capacidad máxima. Qué se debe llevar en la mochila para maximizar el beneficio total?. A modo de ejemplo supongamos que hay tres items como se muestra en la Tabla  4, y suponga que la capacidad de la mochila es 5.

table458
Tabla 4: Items para la Mochila

Los niveles representan los items: luego se tienen tres niveles j=1,2,3. El estado tex2html_wrap_inline1004 en el nivel  j representa el peso total de los items j
más todos los items que se agregarán posteriormente a la mochila. La decisión en el nivel j es cuántos items j poner en la mochila. Sea ese valor tex2html_wrap_inline892 .

Luego se tienen las siguientes fórmulas recursivas: Sea tex2html_wrap_inline1016 el valor de usar tex2html_wrap_inline1004 unidades de la capacidad para items j más los que se agregarán.  Si tex2html_wrap_inline1022 representa el mayor entero menor o igual a a.



Siguiente:Planteo AlternativoArriba:Tutorial Anterior:Características Comunes