Tema
Problema de la mochila
- Algoritmos
- Nivel intermedio
- Con simulador interactivo
El problema de la mochila busca el subconjunto de objetos de mayor valor cuyo peso total no supera una capacidad dada.
Nombre en inglés
Knapsack problem
Intuición
La tabla se lee como una pregunta repetida: Con los primeros i objetos y una capacidad w, ¿conviene meter el objeto i o dejarlo fuera? Meterlo libera la capacidad w menos su peso y suma su valor, mientras que dejarlo fuera conserva el valor de la fila anterior. El coste es el número de casillas, y de ahí que la solución se llame pseudopolinómica: Depende del valor numérico de la capacidad y no solo del número de objetos.
Fórmula
T[i][w] = max(T[i-1][w], v_i + T[i-1][w - p_i]) si p_i <= w ; T[i][w] = T[i-1][w] en otro caso ; coste O(n W)
Ejemplo resuelto
Con capacidad 5 y tres objetos de pesos 2, 3 y 4 y valores 3, 4 y 5, la tabla de 4 filas por 6 columnas deja en la última casilla el valor 7, que corresponde a tomar los objetos de peso 2 y 3. La alternativa de tomar el objeto de peso 4 deja una capacidad de 1 sin usar y solo suma 5.
Errores frecuentes
- Aplicar la estrategia voraz por mayor valor entre peso: Funciona en la versión fraccionaria, mientras que en la versión con objetos enteros puede fallar.
- Llamar polinómico al algoritmo: El coste O(n W) depende del valor de W y no del número de dígitos con que se escribe, de ahí el nombre de pseudopolinómico, y la versión de decisión es NP completa.
- Reutilizar una fila sin cuidado al comprimir la tabla: Con un único vector hay que recorrer las capacidades de mayor a menor, porque de lo contrario cada objeto se puede tomar varias veces.
Ejercicio
Con capacidad 4 y dos objetos, uno de peso 3 y valor 5 y otro de peso 2 y valor 3, ¿cuál es el valor máximo alcanzable?
Ver la solución
Los dos objetos juntos pesan 5 y no caben en la mochila, así que se elige el mejor de los dos por separado, que es el de valor 5.
Respuesta: 5
Temas relacionados
Cursos a los que prepara
Simulador
Este tema tiene un simulador interactivo en la guía.