El problema de la mochila

La idea

Tenemos n objetos, cada uno con un peso wᵢ y un valor vᵢ, y una mochila que soporta como máximo W unidades de peso. En la versión 0/1 cada objeto se lleva entero o se deja: hay que elegir el subconjunto de valor total máximo cuyo peso no exceda W. Probar todos los subconjuntos cuesta 2ⁿ operaciones, inviable para n = 60; el problema es NP-difícil.

La programación dinámica lo resuelve con una tabla. Sea T[i][w] el valor máximo alcanzable usando solo los primeros i objetos con capacidad w. La recurrencia distingue dos decisiones: o no metemos el objeto i, y heredamos T[i−1][w], o lo metemos (si cabe) y sumamos vᵢ al mejor valor con la capacidad que queda, T[i−1][w − wᵢ]. Se toma el máximo de ambas. Rellenando la tabla fila a fila en O(n·W) obtenemos el óptimo en T[n][W], y recorriéndola hacia atrás se reconstruye qué objetos se eligieron. Nótese que O(n·W) no es polinómico en el tamaño de la entrada (W se escribe con log W dígitos): es un algoritmo pseudopolinómico.

La estrategia voraz —ordenar por densidad de valor vᵢ/wᵢ y coger mientras quepa— es rapidísima pero no óptima en la versión 0/1: puede llenar la mochila con objetos ligeros y muy rentables y luego no dejar sitio al objeto grande que valía más. Curiosamente, si se permitiera partir los objetos (mochila fraccionaria), la misma regla voraz sí daría el óptimo exacto. El caso 0/1 admite además esquemas de aproximación que garantizan quedarse a un (1 − ε) del óptimo.

Fórmulas clave

• Problema 0/1max Σ vᵢ xᵢ s.a. Σ wᵢ xᵢ ≤ W, xᵢ ∈ {0, 1}
• Recurrencia de programación dinámicaT[i][w] = max( T[i−1][w], vᵢ + T[i−1][w − wᵢ] )
• Casos baseT[0][w] = 0; si wᵢ > w → T[i][w] = T[i−1][w]
• Costetiempo y memoria O(n · W) (pseudopolinómico)
• Criterio vorazordenar por densidad vᵢ / wᵢ decreciente
• Cota de la relajaciónz_fraccionaria ≥ z_0/1

Dónde se aplica

El problema aparece disfrazado en todas partes: un satélite con masa limitada elige qué instrumentos embarcar, una empresa con presupuesto fijo selecciona la cartera de proyectos de mayor rendimiento (capital budgeting) y un camión de reparto decide qué pedidos carga. En informática, los sistemas de copias de seguridad reparten archivos entre discos y los planificadores de anuncios eligen qué creatividades mostrar con un espacio limitado. La misma recurrencia sirve para el corte de materiales y para problemas de subconjunto suma en criptografía.

Con programación (Python)

def mochila_01(pesos, valores, cap):
    n = len(pesos)
    T = [[0] * (cap + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(cap + 1):
            T[i][w] = T[i - 1][w]
            if pesos[i - 1] <= w:
                cand = T[i - 1][w - pesos[i - 1]] + valores[i - 1]
                if cand > T[i][w]:
                    T[i][w] = cand
    sel, w = [], cap
    for i in range(n, 0, -1):
        if T[i][w] != T[i - 1][w]:
            sel.append(i - 1)
            w -= pesos[i - 1]
    return T[n][cap], sorted(sel)

pesos = [10, 20, 30]
valores = [60, 100, 120]
cap = 50
opt, sel = mochila_01(pesos, valores, cap)
print("Programacion dinamica: valor =", opt, " objetos =", sel)

orden = sorted(range(len(pesos)), key=lambda i: -valores[i] / pesos[i])
peso_v, valor_v, sel_v = 0, 0, []
for i in orden:
    if peso_v + pesos[i] <= cap:
        peso_v += pesos[i]
        valor_v += valores[i]
        sel_v.append(i)
print("Voraz por densidad:   valor =", valor_v, " objetos =", sorted(sel_v), " peso =", peso_v)
print("Perdida del voraz:", opt - valor_v)

La versión en JavaScript, editable y ejecutable en el navegador, está en la página interactiva del tema.

Temas relacionados

Programación entera · Recursión y memoización · Complejidad y notación O grande