Programación dinámica: la familia knapsack

De qué trata este capítulo

Dos problemas que se ven casi idénticos tienen dificultades completamente distintas, y la familia knapsack es donde esa lección pega más fuerte. Tienes una mochila de capacidad limitada y objetos con pesos y valores; maximiza el valor que cargas. Si puedes llevarte fracciones de objetos —3 kilos de un lingote de oro de 5 kilos— el problema se resuelve de forma greedy y óptima: toma primero los objetos más densos (valor por peso) y rebana el último para llenar la mochila. Pero si los objetos son todo o nada —el knapsack 0/1— esa misma regla greedy se rompe, y ninguna regla greedy funciona; necesitas programación dinámica, una tabla sobre (objetos considerados, capacidad usada). Este capítulo construye los dos, para que veas con precisión dónde deja de funcionar greedy y dónde entra DP. También introduce una idea sutil e importante: el DP del knapsack 0/1 es pseudo-polinomial —rápido en la práctica pero no realmente polinomial en el tamaño de la entrada—, que es un primer vistazo al límite de lo que la programación dinámica puede resolver eficientemente.

Un poco de historia

El problema de la mochila es uno de los más antiguos estudiados en optimización combinatoria, formalizado a principios del siglo XX y bautizado por la imagen cotidiana de empacar una mochila. Su importancia creció por dos vías. Primero, se volvió un problema NP-hard canónico: la versión 0/1 está en la lista de problemas difíciles que el artículo histórico de Richard Karp de 1972 conectó entre sí, lo que significa que no se conoce un algoritmo que lo resuelva en tiempo polinomial respecto a la longitud en bits de la entrada. Segundo, y en tensión con lo anterior, tiene una solución por programación dinámica que es eficiente siempre que la capacidad sea un número modesto —el algoritmo "pseudo-polinomial" O(n · capacidad)—, lo que lo convirtió en el ejemplo didáctico favorito precisamente para esa sutileza de que "eficiente en los números" y "eficiente en los bits" no son lo mismo. Knapsack también tiene historia criptográfica real: el criptosistema Merkle-Hellman (1978) basó su seguridad en la dificultad de una variante del knapsack, y su ruptura posterior (a manos de Shamir, aprovechando la estructura especial de esa variante) es una advertencia sobre asumir que un problema difícil sigue siendo difícil en casos especiales. La división entre fraccionario y 0/1 ha sido desde entonces la ilustración estándar de "¿cuándo funciona greedy?".

La intuición

Empecemos con el knapsack fraccionario, porque muestra a greedy en su mejor versión. Ordena los objetos por densidad de valor —valor entre peso— y tómalos del más denso al menos denso. Llena la mochila con objetos completos hasta que uno ya no quepa, y luego toma exactamente la fracción que rellena el espacio restante. Esto es óptimo, y se puede demostrar con un argumento de intercambio: cualquier unidad de capacidad se aprovecha mejor con el material más denso disponible, y las fracciones te permiten hacer justo eso siempre. La propiedad de elección greedy se cumple limpiamente.

Ahora vuelve los objetos todo o nada, y ese argumento se derrumba. Ya no puedes "rellenar" con una fracción, así que tomar primero el objeto más denso puede desperdiciar capacidad que habrías llenado mejor con una combinación de objetos menos densos. El fallo clásico: objetos (peso 10, valor 60), (20, 100), (30, 120) con una mochila de 50. Greedy por densidad toma el objeto de peso 10 (densidad 6) y luego el de peso 20 (densidad 5), llegando a valor 160 y usando 30 de los 50 de capacidad —el último objeto ya no cabe—. El óptimo ignora por completo el objeto más denso y toma los de peso 20 y 30 para un valor de 220, llenando la mochila exacto. Greedy se comprometió con una elección localmente densa que globalmente desperdició espacio. Como ningún criterio greedy es seguro, tienes que considerar, para cada objeto, ambas posibilidades —tomarlo o dejarlo—, y eso es el programa dinámico. Define dp[i][w] como el mejor valor alcanzable usando los primeros i objetos dentro de la capacidad w. Cada objeto i o se salta (valor dp[i-1][w]) o se toma si cabe (valor value[i] + dp[i-1][w - weight[i]]), y te quedas con el mejor. Llena la tabla desde "ningún objeto" hacia arriba y la respuesta es dp[n][capacity]. Todos los subconjuntos se consideran implícitamente, pero cada subproblema (objeto, capacidad) se calcula una sola vez.

Complejidad: cómo escala

El knapsack fraccionario es O(n log n) —un sort más un recorrido—. El DP 0/1 es O(n · capacidad) en tiempo y espacio: una tabla de n objetos por capacidad+1 columnas, con cada celda en O(1). Eso parece polinomial, pero hay un detalle que hizo famoso al knapsack. El duelo no compite en velocidad —ambos son rápidos—, compite en el valor que logra cada método conforme los objetos crecen respecto a la mochila:

El DP es exactamente óptimo (la línea plana en 100%, verificada contra fuerza bruta en cada instancia pequeña). Greedy se le acerca bastante cuando los objetos son chicos respecto a la mochila —con objetos del 10% del tamaño es prácticamente óptimo—, pero se degrada conforme los objetos se vuelven más gruesos, y cae a alrededor del 95% cuando un objeto puede llenar la mochila entera, porque la granularidad de todo o nada es donde se nota su espacio desperdiciado. Y algo clave: ese 95% es solo el promedio; greedy sobre 0/1 no tiene ninguna garantía en el peor caso. La línea del fraccionario queda arriba del 100% —con granularidad gruesa reporta 136% del óptimo 0/1— porque permitir fracciones siempre puede hacerlo al menos igual de bien, y la brecha entre la relajación fraccionaria y la respuesta real del 0/1 mide cuánto cuesta la restricción de integralidad. Ese valor fraccionario es una cota superior legítima del óptimo 0/1, que es exactamente por lo que los solvers de branch-and-bound la usan para podar.

En qué es bueno y en qué no

El DP del knapsack es la herramienta correcta para seleccionar un subconjunto de máximo valor bajo una sola restricción de capacidad, cuando esa capacidad (o el peso total) es un número modesto: asignación de presupuesto, carga de contenedores y mercancía, subproblemas de cutting-stock y bin-packing, planeación de recursos, selección de portafolio bajo un tope de costo, y el problema subset-sum (un caso especial donde el valor es igual al peso). Su estructura de DP además generaliza: el knapsack acotado (copias limitadas de cada objeto), el knapsack no acotado (copias ilimitadas, que es exactamente la recurrencia de coin-change del capítulo pasado) y el knapsack multidimensional (varias restricciones) siguen todos el mismo patrón de tomar o saltar. Cuando la restricción es un entero pequeño, esta es una solución limpia, exacta y rápida.

Donde sufre es con capacidades grandes, donde el O(n · capacidad) pseudo-polinomial se vuelve prohibitivo: una capacidad en el orden de miles de millones hace que la tabla sea imposiblemente grande incluso con pocos objetos, y tienes que cambiar a branch-and-bound, esquemas de aproximación o solvers de programación entera. También maneja únicamente la estructura específica de objetos independientes con valor y peso aditivos; los problemas con interacciones entre objetos (tomar A cambia el valor de B), con varias restricciones complejas o con objetivos no aditivos necesitan otras formulaciones. Y, como muestra el fallo de greedy, hay que resistir la tentación de resolverlo con una heurística rápida cuando necesitas un óptimo garantizado. Knapsack se resuelve exactamente con DP dentro de su presupuesto pseudo-polinomial, y es difícil fuera de él; saber en cuál régimen estás es todo el juego.

Los datos, o las entradas

El duelo barre el tamaño de los objetos respecto a la mochila —desde objetos diminutos (10% de la capacidad) hasta objetos que pueden llenarla por completo— y mide el valor de cada método como porcentaje del óptimo del DP, mostrando cómo greedy se degrada conforme la granularidad se hace más gruesa y cómo la relajación fraccionaria se queda arriba del 100% como cota superior floja. La correctitud se verifica contra fuerza bruta (probar todos los subconjuntos) en cientos de instancias pequeñas: el DP debe coincidir exactamente con el óptimo real, el conjunto de objetos reconstruido debe ser un empaque válido de ese valor, greedy nunca debe superar al óptimo, y el valor fraccionario nunca debe quedar por debajo. La animación llena la tabla 2D del DP para cuatro objetos y capacidad 7 —la instancia donde greedy saca 8 y el DP saca 9— una fila de objeto a la vez.

Constrúyelo, una función a la vez

Knapsack fraccionario: greedy, y demostrablemente óptimo para esa variante.

def fractional_knapsack(items, capacity):
    """FRACTIONAL knapsack — greedy is optimal here. `items` is a list of (weight, value). Sort by
    value density (value/weight) descending; take whole items until one won't fit, then take the
    fraction that fills the bag. O(n log n). Returns the maximum value (possibly fractional)."""
    order = sorted(items, key=lambda it: it[1] / it[0], reverse=True)   # densest first
    value, room = 0.0, capacity
    for w, v in order:
        if room >= w:
            value += v                            # whole item fits
            room -= w
        else:
            value += v * (room / w)               # take the fraction that fills the bag
            break
    return value

Knapsack 0/1: el programa dinámico que greedy no puede reemplazar, con reconstrucción.

def knapsack_01(items, capacity):
    """0/1 knapsack — each item taken whole or not at all. Greedy fails; this is dynamic
    programming. dp[i][w] = best value using the first i items within capacity w. Each item is
    either SKIPPED (dp[i-1][w]) or TAKEN if it fits (value + dp[i-1][w-weight]). O(n · capacity)
    time and space — 'pseudo-polynomial': polynomial in the capacity's VALUE, exponential in its
    number of bits. Returns (best_value, chosen_item_indices)."""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w_i, v_i = items[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]               # option A: skip item i
            if w_i <= w:                          # option B: take item i, if it fits
                dp[i][w] = max(dp[i][w], v_i + dp[i - 1][w - w_i])
    # reconstruct which items were taken by walking the table back
    chosen, w = [], capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:              # value changed ⇒ item i was taken
            chosen.append(i - 1)
            w -= items[i - 1][0]
    return dp[n][capacity], sorted(chosen)

Míralo funcionar

Aquí está la tabla del DP 0/1 para cuatro objetos (pesos 1, 3, 4, 5; valores 1, 4, 5, 7) y una mochila de capacidad 7, llenada una fila de objeto a la vez. La fila 0 es "ningún objeto", todo ceros. Cada fila nueva agrega un objeto y recalcula cada columna de capacidad como la mejor de dos opciones: saltar el objeto (copiar el valor tal cual de la fila de arriba) o tomarlo (su valor más el mejor valor para la capacidad sobrante, dp[i-1][w-weight]). Las celdas verdes son donde ganó tomar el objeto; las grises, donde ganó saltarlo. Observa cómo el mejor valor va subiendo conforme se agregan objetos, hasta aterrizar en dp[4][7] = 9 en la esquina inferior derecha. El trazo naranja al final recorre las decisiones hacia atrás para recuperar qué objetos se tomaron: los de peso 3 y peso 4, valor 4+5 = 9. El greedy por densidad habría agarrado primero el objeto de peso 5 (densidad 1.4) y solo habría llegado a 8; la tabla, al considerar saltar y tomar en cada paso, encontró el mejor par que el compromiso de greedy dejó ir:

El código completo

La pestaña "desde cero" trae los dos knapsacks: el greedy fraccionario y el DP 0/1 con reconstrucción; la pestaña de librería trae el greedy por densidad aplicado al 0/1 (el enfoque equivocado, para contrastar) y el óptimo por fuerza bruta que se usa para verificar el DP. Cambia entre ellas: el greedy fraccionario y el greedy 0/1 equivocado son casi el mismo código, y la diferencia entre "óptimo" y "sin garantía" está enteramente en si se permiten fracciones.

"""The knapsack family — pack a bag of limited capacity with items of given weights and values
to maximize the value carried. It's the archetypal constrained-optimization problem, and it hides
a beautiful lesson: two nearly identical versions have completely different difficulty.

FRACTIONAL knapsack lets you take fractions of items (3.5 kg of a 5 kg gold bar). It's solved
GREEDILY and optimally: sort by value-per-weight and take the densest items first, slicing the
last one to fill the bag exactly. The greedy-choice property holds.

0/1 knapsack forces an all-or-nothing choice per item (you take the whole gold bar or none). That
one change destroys the greedy-choice property — taking the densest item first can be arbitrarily
bad — and the problem becomes one that only DYNAMIC PROGRAMMING solves exactly, via a table over
(items considered, capacity used). This chapter builds both, so the fractional/0-1 split shows
exactly where greedy stops working and DP takes over.
"""


# region: fractional
def fractional_knapsack(items, capacity):
    """FRACTIONAL knapsack — greedy is optimal here. `items` is a list of (weight, value). Sort by
    value density (value/weight) descending; take whole items until one won't fit, then take the
    fraction that fills the bag. O(n log n). Returns the maximum value (possibly fractional)."""
    order = sorted(items, key=lambda it: it[1] / it[0], reverse=True)   # densest first
    value, room = 0.0, capacity
    for w, v in order:
        if room >= w:
            value += v                            # whole item fits
            room -= w
        else:
            value += v * (room / w)               # take the fraction that fills the bag
            break
    return value
# endregion


# region: knapsack_01
def knapsack_01(items, capacity):
    """0/1 knapsack — each item taken whole or not at all. Greedy fails; this is dynamic
    programming. dp[i][w] = best value using the first i items within capacity w. Each item is
    either SKIPPED (dp[i-1][w]) or TAKEN if it fits (value + dp[i-1][w-weight]). O(n · capacity)
    time and space — 'pseudo-polynomial': polynomial in the capacity's VALUE, exponential in its
    number of bits. Returns (best_value, chosen_item_indices)."""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w_i, v_i = items[i - 1]
        for w in range(capacity + 1):
            dp[i][w] = dp[i - 1][w]               # option A: skip item i
            if w_i <= w:                          # option B: take item i, if it fits
                dp[i][w] = max(dp[i][w], v_i + dp[i - 1][w - w_i])
    # reconstruct which items were taken by walking the table back
    chosen, w = [], capacity
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:              # value changed ⇒ item i was taken
            chosen.append(i - 1)
            w -= items[i - 1][0]
    return dp[n][capacity], sorted(chosen)
# endregion


# region: table
def knapsack_table(items, capacity):
    """Return the full dp table plus, for each cell, whether the current item was TAKEN there —
    used to animate the fill and see the take/skip decision pattern."""
    n = len(items)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    taken = [[False] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w_i, v_i = items[i - 1]
        for w in range(capacity + 1):
            skip = dp[i - 1][w]
            take = v_i + dp[i - 1][w - w_i] if w_i <= w else -1
            if take > skip:
                dp[i][w], taken[i][w] = take, True
            else:
                dp[i][w] = skip
    return dp, taken
# endregion

"""The contrasts and the reference. Two things to compare 0/1 knapsack's DP against:

- `greedy_01` applies the FRACTIONAL greedy (densest first) to the 0/1 problem — the natural wrong
  idea. It's fast but can leave a lot of value on the table, and it's the cautionary contrast that
  shows why 0/1 needs DP.
- `brute_force_01` tries every subset (O(2^n)) for the true optimum — the reference that proves the
  DP is correct on small instances.

In production you'd use the DP (or an ILP/branch-and-bound solver for large instances); these exist
to verify and to contrast.
"""
from itertools import combinations


# region: greedy
def greedy_01(items, capacity):
    """The fractional greedy (densest item first) applied to 0/1 — WRONG in general. It takes whole
    dense items until none fits, never reconsidering, so it can miss a better combination of less
    dense items that pack the bag more fully. Returns (value, chosen indices)."""
    order = sorted(range(len(items)), key=lambda i: items[i][1] / items[i][0], reverse=True)
    value, room, chosen = 0, capacity, []
    for i in order:
        w, v = items[i]
        if w <= room:
            value += v
            room -= w
            chosen.append(i)
    return value, sorted(chosen)
# endregion


# region: brute
def brute_force_01(items, capacity):
    """The true 0/1 optimum by trying every subset — O(2^n), only for verification on small inputs.
    Returns the best value."""
    n = len(items)
    best = 0
    for r in range(n + 1):
        for subset in combinations(range(n), r):
            w = sum(items[i][0] for i in subset)
            if w <= capacity:
                best = max(best, sum(items[i][1] for i in subset))
    return best
# endregion

Desde cero contra la librería

El par de knapsacks es la ilustración más clara de todo este libro sobre cuándo funciona greedy. El fraccionario y el 0/1 se diferencian por una sola regla —¿puedes tomar una fracción?— y esa regla es la diferencia entre un greedy de una línea demostrablemente óptimo y un problema NP-hard que necesita una tabla de DP. Vuelve concreto el punto abstracto del capítulo de greedy: greedy es óptimo exactamente cuando el problema tiene la propiedad de elección greedy, y "tomar fracciones" es precisamente lo que le da esa propiedad al knapsack fraccionario y lo que le falta al 0/1. El capítulo también dibuja el límite de la propia programación dinámica. El DP resolvió el knapsack 0/1 de forma pseudo-polinomial —eficiente para capacidades modestas pero no realmente polinomial—, que es la primera señal de que DP, por poderoso que sea, no vuelve fácil cualquier problema; hace explícito el espacio de estados, y cuando ese espacio es enorme (capacidad en miles de millones, o el estado exponencial de subconjuntos de ciudades del agente viajero), DP ayuda pero no te salva. En producción usarías el DP para capacidades pequeñas y branch-and-bound o un solver de ILP en los demás casos; construir tú mismo ambos knapsacks es lo que convierte la división fraccionario/0-1 —una de las distinciones "¿esto es greedy o DP?" más importantes— en algo que ya viste en lugar de algo memorizado.

Dónde te lo vas a encontrar

Los problemas de knapsack están en todos lados donde se asignan recursos bajo un presupuesto. La carga de mercancía, contenedores y vehículos optimiza el valor bajo límites de peso o volumen. La selección de portafolios financieros maximiza el rendimiento bajo un tope de costo (una variante de knapsack). Los schedulers de nube y de clúster acomodan trabajos en máquinas bajo restricciones de CPU y memoria (knapsack multidimensional, bin-packing). Cutting-stock y manufactura minimizan el desperdicio empacando órdenes. La selección de anuncios y la programación de medios maximizan el valor bajo un límite de espacios o presupuesto. Subset-sum —un caso especial de knapsack— aparece en conciliación contable y en criptografía. Y la técnica de DP en sí, tomar o saltar sobre una capacidad, se repite a lo largo del software de optimización de recursos. La versión fraccionaria aparece dondequiera que se asignen recursos divisibles por densidad (flujos fraccionarios, ciertos tipos de scheduling). Cuando la pregunta es "máximo valor bajo un límite de capacidad", lo más probable es que abajo haya un modelo de knapsack.

Puntos clave

La familia knapsack enseña dónde termina greedy y dónde empieza la programación dinámica. El knapsack fraccionario —objetos divisibles— es óptimo con greedy: toma primero el más denso. El knapsack 0/1 —todo o nada— destruye la propiedad de elección greedy (el greedy por densidad no tiene garantía en el peor caso y puede ser arbitrariamente malo) y necesita una tabla de DP, dp[i][w] = max(saltar, tomar), O(n · capacidad). Esa complejidad es pseudo-polinomial —polinomial en el valor de la capacidad pero exponencial en su longitud en bits—, así que knapsack es NP-hard y aun así se resuelve eficientemente para capacidades modestas, una distinción crucial entre "rápido para mis entradas" y "tiempo polinomial". Una sola regla, fracciones o no, decide toda la dificultad.

El siguiente capítulo mantiene el DP sobre tablas bidimensionales pero pasa de empacar a secuencias. La distancia de edición y la subsecuencia común más larga miden qué tan parecidas son dos cadenas llenando una cuadrícula donde cada celda compara un carácter de cada cadena: son los algoritmos detrás de los correctores ortográficos, diff, el autocorrector y el alineamiento de secuencias de ADN. Como knapsack, son DP sobre un estado bidimensional; a diferencia de knapsack, ese estado sí es genuinamente polinomial, y los problemas están entre los más útiles de toda la computación.