Overview
El problema de la mochila 0/1: dados artículos con pesos y valores, maximiza el valor total sin exceder la capacidad de peso.
Analogy
Empacar para un viaje: cada artículo tiene peso y valor, solo puedes cargar hasta W kilos — ¿qué llevas para maximizar el valor?
Step-by-step
- Crea tabla DP: dp[i][w] = máximo valor con los primeros i artículos y capacidad w
- Para cada artículo: no incluir (dp[i-1][w]) o incluir (dp[i-1][w-peso_i] + valor_i)
- Toma el máximo de las dos opciones
- dp[n][W] es la respuesta
Visual
artículos: [(peso=2,val=3),(peso=3,val=4),(peso=4,val=5)]
W=5
dp[3][5] = 7 (artículo 1 + artículo 2)
Common mistakes
- Confundir 0/1 (cada artículo una vez) con mochila fraccional o ilimitada
- Iteración incorrecta al optimizar a O(W) espacio
Practice questions
- Optimiza a O(W) espacio con un array 1D
- Reconstruye qué artículos se incluyen rastreando hacia atrás la tabla DP
Time
O(n×W) — n artículos × W capacidad
Space
O(n×W) → optimizable a O(W)