Problema de la mochila
El problema de la mochila es un problema de optimización combinatoria : dado un conjunto de artículos, cada uno con un peso y un valor, determine el número de cada artículo para incluir en una colección de modo que el peso total sea menor o igual a un límite dado y el valor total es lo más grande posible. Deriva su nombre del problema al que se enfrenta alguien que está limitado por una mochila de tamaño fijo y debe llenarla con los artículos más valiosos. El problema a menudo surge en la asignación de recursos, donde los tomadores de decisiones tienen que elegir entre un conjunto de proyectos o tareas no divisibles con un presupuesto fijo o una restricción de tiempo, respectivamente.
El problema de la mochila se ha estudiado durante más de un siglo, y los primeros trabajos datan de 1897. [1] El nombre "problema de la mochila" se remonta a los primeros trabajos del matemático Tobias Dantzig (1884-1956), [2 ] y se refiere al problema común de empacar los artículos más valiosos o útiles sin sobrecargar el equipaje.
Los problemas de la mochila aparecen en los procesos de toma de decisiones del mundo real en una amplia variedad de campos, como encontrar la forma menos derrochadora de cortar materias primas, [3] selección de inversiones y carteras , [4] selección de activos para titulización respaldada por activos. , [5] y generación de claves para Merkle-Hellman [6] y otros criptosistemas de mochila .
Una de las primeras aplicaciones de los algoritmos de mochila fue en la construcción y puntuación de pruebas en las que los examinados pueden elegir a qué preguntas responder. Para pequeños ejemplos, es un proceso bastante simple proporcionar a los examinados esa opción. Por ejemplo, si un examen contiene 12 preguntas cada una con un valor de 10 puntos, la persona que rinde el examen solo necesita responder 10 preguntas para lograr una puntuación máxima posible de 100 puntos. Sin embargo, en las pruebas con una distribución heterogénea de valores de puntos, es más difícil proporcionar opciones. Feuerman y Weiss propusieron un sistema en el que a los estudiantes se les da una prueba heterogénea con un total de 125 puntos posibles. Se pide a los estudiantes que respondan todas las preguntas lo mejor que puedan. De los posibles subconjuntos de problemas cuyos valores de puntos totales suman 100,un algoritmo de mochila determinaría qué subconjunto da a cada estudiante la puntuación más alta posible.[7]
Un estudio de 1999 del Repositorio de Algoritmos de la Universidad de Stony Brook mostró que, de 75 problemas algorítmicos, el problema de la mochila era el decimonoveno más popular y el tercero más necesario después de los árboles de sufijos y el problema de empaquetado en contenedores . [8]
El problema más común que se resuelve es el problema de la mochila 0-1 , que restringe el número de copias de cada tipo de artículo a cero o uno. Dado un conjunto de elementos numerados del 1 al , cada uno con un peso y un valor , junto con una capacidad máxima de peso ,
(Solución: si cualquier número de cada casilla está disponible, entonces tres casillas amarillas y tres casillas grises; si solo están disponibles las casillas que se muestran, entonces todas, pero no la casilla verde).
