EL PROBLEMA DE LA MOCHILA

Supóngase que tenemos una mochila con capacidad C (un entero positivo) y n objetos de tamaño s1, ..., sn, así como "utilidades" ó "pesos" p1 ..., pn (todos positivos).

El problema consiste en hallar la utilidad total más grande de cualquier subconjunto de los objetos que quepa en la mochila (y hallar un subconjunto que produzca la utilidad máxima).

Así que dado la utilidad k, ¿existe un subconjunto de los objetos que quepa en la mochila y tenga una utilidad total de por lo menos k?

El problema de la mochila tiene diversas aplicaciones en planificación económica y en problemas de carga o empaque. Por ejemplo, podría describir un problema de toma de decisiones de inversión en el que el "tamaño" de una inversión es la cantidad de dinero requerida, C es el capital total que se puede invertir y la "utilidad" de una inversión es el rendimiento esperado. Otro ejemplo sería una aplicación de una versión más complicada del problema, donde los objetos son tareas o experimentos que diversas organizaciones quieren que se efectúen durante un vuelo espacial. Además de su tamaño (el volumen del equipo necesario), cada tarea podría tener necesidades de energía y necesidades de tiempo de la tripulación. Tanto el espacio como la energía y el tiempo disponibles durante el vuelo son limitados. Cada tarea tiene cierto valor, o utilidad. ¿Qué subconjunto factible de las tareas tiene el valor total más grande?

Cabe señalar que el problema de la mochila es de maximización.