Problema De La Mochila

Problema de la mochila THE KNAPSACK PROBLEM
 Es un problema de optimización combinatoria.

 Es decir:
Dado un conjunto de elementos, cada uno con un peso y un valor, se determinar el número decada elemento a incluir en una colección de manera que el peso total es menor que o igual a un límite dado y el valor total es tan grande como sea posible.

 Su nombre se deriva del problemaenfrentado por una persona que se ve limitado por el tamaño fijo de una mochila y debe llenarla con los artículos más valiosos que posee.
Pág. 01 Alicia Granda – Mario Silva Mora

 El problema surge amenudo en la asignación de recursos donde hay limitaciones financieras y se estudia en campos tales como la combinatoria , ciencias de la computación , teoría de la complejidad , la criptografía y lasmatemáticas aplicadas.  El problema de la mochila se ha estudiado durante más de un siglo, las primeras obras datan de 1897.  No se sabe cómo se originó el nombre de "problema de la mochila", peroel problema fue mencionado como tal en las primeras obras del matemático Tobias Dantzig (1884-1956).

Pág. 02

Alicia Granda – Mario Silva Mora

EJEMPLO de una dimensión (restricción) problemade la mochila:

 ¿Que cajas se debe elegir para maximizar la cantidad de dinero mientras se mantiene el peso total inferior o igual a 15 kg?

NOTA: En un problema múltiple restringido se podríaconsiderar tanto el peso y el volumen de las cajas. SOLUCIÓN:  Si la cantidad de cada cajas no está restringida, se seleccionaría 3 cajas amarillas y 3 cajas grises.  Pero en la imagen que semuestra, están restringida la cantidad, se seleccionara todas menos la caja verde.
Pág. 03 Alicia Granda – Mario Silva Mora

Aplicaciones:
 Un estudio de 1998 del Repositorio de la Universidad de StonyBrook Algoritmo puso de manifiesto que, de los 75 problemas algorítmicos, el problema de la mochila era la 18vo más popular y el cuarto más necesaria después de kd-árboles , árboles de sufijos , y...