Problema de la Mochila 0/1 (Knapsack)

Programación dinámica y el problema de la mochila

El problema

Dado un conjunto de n objetos con pesos w_i y valores v_i, y una mochila con capacidad W, selecciona el subconjunto que maximice el valor total sin exceder W. La versión 0/1 significa que cada objeto se toma entero o no se toma (no fracciones).

Por qué no funciona la heurística greedy

Una solución "obvia" sería ordenar por ratio valor/peso y meter los mejores primero. Funciona para la mochila fraccionaria pero NO siempre para la 0/1. Ejemplo: W=10, objetos (peso=6, valor=10), (peso=5, valor=8), (peso=5, valor=8). Greedy toma el primero (ratio 1.67) y ya no caben los otros = valor 10. La solución óptima es tomar los dos últimos = valor 16.

Programación dinámica al rescate

La idea: construir la solución de problemas más chicos a más grandes. Define DP[i][w] = valor máximo usando los primeros i objetos con capacidad w. La recursión:

• Si w_i > w (el objeto no cabe): DP[i][w] = DP[i-1][w] (no tomarlo)
• Si w_i ≤ w: DP[i][w] = max(DP[i-1][w], DP[i-1][w-w_i] + v_i)

La respuesta final está en DP[n][W].

Reconstrucción de la solución

Una vez tienes la tabla DP, "reverse engineering" cuáles objetos se tomaron:

1. Empieza en DP[n][W].
2. Si DP[i][w] ≠ DP[i-1][w], el objeto i fue tomado. Resta su peso de w.
3. Si DP[i][w] = DP[i-1][w], el objeto i no fue tomado.
4. Repite con i-1 hasta i = 0.

Complejidad

O(n·W) tiempo y espacio. Es pseudopolinomial: polinomial en el valor de W, no en su número de bits. Para W grande (millones), DP no escala - se usan aproximaciones (FPTAS) o programación entera (branch and bound).

Por qué importa la mochila

La mochila aparece disfrazada en miles de problemas reales:

• Presupuesto de inversión: proyectos con costo y beneficio, presupuesto limitado.
• Asignación de recursos: cuáles proyectos hacer dado un equipo limitado.
• Carga de aviones/camiones: qué cargas llevar maximizando ingreso.
• Selección de cartera: qué activos comprar con presupuesto limitado.
• Compresión de archivos: variantes en algoritmos de codificación.
• Subset sum / criptografía: base de algunos esquemas criptográficos antiguos (Merkle-Hellman).

Variantes del problema

• Mochila fraccionaria: puedes tomar fracciones. Greedy óptimo. O(n log n).
• Mochila ilimitada: cada objeto se puede tomar varias veces. DP de una dimensión.
• Mochila acotada: cada objeto tiene un límite máximo de copias.
• Mochila multidimensional: múltiples restricciones (peso + volumen + valor).
• Mochila con dependencias: tomar X obliga a tomar Y, o impide tomar Z.

Programación dinámica como técnica

La mochila es un ejemplo clásico de DP. Otros problemas resueltos con la misma técnica:

• Floyd-Warshall (distancias mínimas).
• Subsecuencia común más larga (LCS) - útil en diff y bioinformática.
• Multiplicación óptima de matrices.
• Problema del cambio (monedas).
• Edit distance / Levenshtein - usado en spell-checkers.
• Problemas de scheduling con plazos y penalizaciones.

Cuándo no usar DP

• Cuando el espacio de estados (filas × columnas) no cabe en memoria.
• Cuando no hay subestructura óptima (el óptimo global no se compone de óptimos locales).
• Cuando hay solución analítica directa más simple.

Conexión: el problema de la mochila es NP-hard en su formulación de decisión. DP lo resuelve en pseudopolinomial gracias a la estructura específica. Pero si W es exponencial en n, DP también es exponencial - no contradice la NP-completitud.