Programación dinámica: la familia knapsack

Maximiza el valor en una mochila limitada. Una sola regla —¿se permiten fracciones?— decide entre greedy y DP.

Fraccionario vs 0/1

• Fraccionario (puedes rebanar): greedy es ÓPTIMO — el más denso primero, y rellenas la mochila
• 0/1 (todo o nada): greedy SE ROMPE — el objeto más denso puede desperdiciar capacidad
• Clásico: (10,60),(20,100),(30,120), mochila 50 → greedy 160, óptimo 220
• Ninguna regla greedy sirve para 0/1 → programación dinámica

El DP 0/1: tomar o saltar

• dp[i][w] = mejor valor con los primeros i objetos dentro de la capacidad w
• Cada objeto: max(saltar = dp[i-1][w], tomar = value + dp[i-1][w-weight])
• Llena desde "ningún objeto" hacia arriba; respuesta = dp[n][capacity]
• O(n · capacidad)

Mira cómo se llena la tabla

Verde = aquí se tomó el objeto · gris = se saltó. dp[4][7] = 9 (objetos 3+4). El greedy por densidad agarra primero el objeto de peso 5 → solo 8.

Greedy no tiene garantía

Greedy promedia ~95%, pero en el PEOR caso → 0 (objetos A=(1,2), B=(W,W), mochila W: greedy 2, óptimo W). Fraccionario 136% = una cota superior floja (brecha de relajación).

Pseudo-polinomial

• O(n · capacidad) es polinomial en el VALOR de la capacidad, exponencial en sus BITS
• Rápido con capacidades modestas; inviable con enormes → branch-and-bound / FPTAS
• El knapsack 0/1 es NP-hard — el DP no lo mete en P
• "Rápido para mis entradas" ≠ "tiempo polinomial"

Para llevar

Se permiten fracciones → greedy. Todo o nada → DP. Esa es toda la diferencia. DP hace explícito el espacio de estados — pero un espacio de estados enorme sigue doliendo. Siguiente: distancia de edición y LCS — DP sobre secuencias (diff, corrector ortográfico, ADN).