El problema de la mochila
Una excursionista con un límite de peso, un ladrón con un saco, una empresa con un presupuesto y una lista de proyectos: todos se enfrentan a la misma pregunta. ¿Qué cosas deben entrar para obtener el mayor valor sin pasarse del límite? Es el problema de la mochila, y la programación dinámica lo resuelve de forma exacta cuando los pesos son números enteros de tamaño moderado.
El problema
Hay n objetos, cada uno con un peso y un valor, y una mochila que aguanta como mucho un peso W. Elige un conjunto de objetos cuyo peso total sea como mucho W y cuyo valor total sea lo mayor posible. Cada objeto entra entero o se queda fuera, y por eso se llama problema de la mochila 0/1. Con n objetos hay 2ⁿ conjuntos posibles, así que probarlos todos pronto se vuelve imposible.
La tabla
Sea best[i][w] el mayor valor que cabe en el peso w usando solo los i primeros objetos. Entonces best[0][w] = 0, y para cada fila siguiente hay dos opciones: dejar fuera el objeto i, lo que da best[i − 1][w], o, si su peso wᵢ cabe, meterlo, lo que da su valor más best[i − 1][w − wᵢ]. El mayor de los dos es best[i][w]. Si la tabla se llena fila por fila, las dos celdas que se necesitan siempre están listas.
Un ejemplo
Toma una capacidad de 7 y cuatro objetos con pesos 1, 3, 4 y 5 y valores 1, 4, 5 y 7. Con solo el primer objeto, cada capacidad desde 1 vale 1. Al añadir el segundo, la capacidad 4 puede llevar los dos por 5. Al añadir el tercero, la capacidad 7 puede llevar los objetos 2 y 3 por 9. El cuarto objeto, de peso 5 y valor 7, podría ir con el objeto 1 por 8 con capacidad 6 o 7, pero 9 es mejor, así que la celda de abajo a la derecha es 9: mete los objetos de peso 3 y 4.
¿Qué dificultad tiene?
La tabla necesita unos n·W pasos. Parece rápido, pero W es un número, y un número de d cifras puede llegar a 10 elevado a d, así que el trabajo crece de forma exponencial con la longitud de la entrada. El problema de la mochila es NP-difícil; fue uno de los 21 problemas NP-completos de Richard Karp de 1972. En la práctica, la tabla, la ramificación y poda y buenos esquemas de aproximación resuelven bien casos reales grandes.
Historia y usos
El nombre se remonta al matemático Tobias Dantzig a principios del siglo XX, y su hijo George Dantzig dio un método voraz clásico para resolverlo en 1957. Los problemas de la mochila aparecen al hacer presupuestos y seleccionar carteras de inversión, al cortar materia prima con el menor desperdicio posible, al cargar mercancías e incluso en los inicios de la criptografía de clave pública: el criptosistema de Merkle–Hellman de 1978 se basaba en un problema de la mochila y fue roto pocos años después.
Explóralo
Abre la app, cambia a la vista Tabla y pulsa Paso. La celda naranja es la que se está llenando, y las celdas azules son las dos que compara: la celda justo encima y, en la fila de arriba, la celda que está tantas columnas a la izquierda como pesa el objeto. Después de la última celda, la reconstrucción sube en naranja desde la esquina de abajo a la derecha, y los objetos metidos aparecen debajo de la tabla.
Preguntas frecuentes
¿Qué diferencia hay entre la mochila 0/1, acotada y no acotada?
En la versión 0/1 cada objeto se toma como mucho una vez. En la versión acotada cada objeto tiene un número limitado de copias, y en la no acotada, cualquier número. La tabla cambia muy poco de una a otra.
¿Acierta alguna vez el método voraz en la mochila?
En el problema de la mochila fraccionaria, donde los objetos se pueden partir, tomar primero el mejor valor por peso es óptimo. Con objetos enteros puede quedarse muy lejos, aunque la mejor opción entre el método voraz y el objeto más valioso por sí solo siempre vale al menos la mitad del mejor valor.
¿Cuánta memoria necesita la tabla?
(n + 1)·(W + 1) celdas para la tabla completa, que es lo que se necesita para reconstruir los objetos. Si solo se quiere el mejor valor, basta con una fila de W + 1 celdas, llenada de derecha a izquierda.
¿La mochila es lo mismo que la suma de subconjuntos?
La suma de subconjuntos es el caso particular en que el valor de cada objeto es igual a su peso y la pregunta es si la mochila se puede llenar exactamente. También es NP-completo y se resuelve con el mismo tipo de tabla.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba el problema de la mochila