1. ¿Qué es la mochila 0-1?

El problema de la mochila 0-1 es un clásico de la optimización combinatoria. Dado un conjunto de n ítems, cada uno con un peso w_i y un valor v_i, y una capacidad máxima W de la mochila, debemos seleccionar un subconjunto de ítems de forma que:

• La suma de los pesos no supere W.
• El valor total sea máximo.

La restricción "0‑1" indica que cada ítem puede estar una sola vez (0 = no tomado, 1 = tomado). No se permiten fracciones.

2. Formulación matemática

max  Σ v_i·x_i
s.t. Σ w_i·x_i ≤ W
     x_i ∈ {0,1}   ∀ i = 1…n

Donde x_i es la variable de decisión que indica si el ítem i se incluye.

3. Solución con Programación Dinámica (DP)

La DP construye una tabla dp[i][c] que representa el valor máximo alcanzable usando los primeros i ítems con capacidad c. La recurrencia es:

dp[i][c] = dp[i-1][c]                              // no tomar el ítem i
if w_i ≤ c:
    dp[i][c] = max(dp[i][c], dp[i-1][c-w_i] + v_i)   // tomar el ítem i

La complejidad temporal es O(n·W) y la espacial O(n·W). Con una optimización de espacio podemos reducirla a O(W) usando una sola fila y recorriendo la capacidad en sentido descendente.

4. Implementación en Python (versión clásica)

def knapsack_01(weights, values, capacity):
    n = len(weights)
    # tabla DP de (n+1) x (capacity+1)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w = weights[i-1]
        v = values[i-1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i-1][c]                 # no tomar
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)  # tomar
    return dp[n][capacity]

# Ejemplo de uso
weights = [2, 3, 4, 5]
values  = [3, 4, 5, 6]
capacity = 5
print(knapsack_01(weights, values, capacity))  # → 7 (ítems 1 y 2)

Salida esperada: 7 (seleccionamos los ítems con peso 2 y 3).

5. Optimización de espacio (O(W) memoria)

def knapsack_01_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        w, v = weights[i], values[i]
        # recorrer de mayor a menor para evitar reutilizar el ítem en la misma iteración
        for c in range(capacity, w-1, -1):
            dp[c] = max(dp[c], dp[c-w] + v)
    return dp[capacity]

print(knapsack_01_optimized(weights, values, capacity))  # → 7

Esta versión es ideal cuando W es grande y la tabla completa no cabe en memoria.

6. Recuperar los ítems seleccionados

def knapsack_items(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        w, v = weights[i-1], values[i-1]
        for c in range(capacity + 1):
            dp[i][c] = dp[i-1][c]
            if w <= c:
                dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
    # backtrack para obtener los ítems
    res, c = [], capacity
    for i in range(n, 0, -1):
        if dp[i][c] != dp[i-1][c]:
            res.append(i-1)          # índice del ítem
            c -= weights[i-1]
    res.reverse()
    return dp[n][capacity], res

valor, items = knapsack_items(weights, values, capacity)
print('Valor máximo:', valor)
print('Ítems elegidos:', items)   # → [0, 1]

7. Comparativa con otras variantes

8. Buenas prácticas y trucos de rendimiento

• Ordenar por relación valor/peso: Útil antes de aplicar heurísticas o B&B.
• Uso de numpy para la tabla: Operaciones vectorizadas pueden reducir el factor constante.
• Memoria compartida en procesos paralelos: Cuando se evalúan múltiples instancias (ej. diferentes capacidades) se puede reutilizar la tabla parcial.
• Limitar la capacidad: Redondear pesos a la unidad más grande que mantenga la precisión requerida reduce W y acelera DP.

import numpy as np

def knapsack_numpy(weights, values, capacity):
    dp = np.zeros(capacity + 1, dtype=int)
    for w, v in zip(weights, values):
        dp[w:] = np.maximum(dp[w:], dp[:-w] + v)
    return dp[capacity]

9. Depuración y troubleshooting comunes

10. Extensiones y casos de uso reales

El algoritmo 0‑1 Knapsack aparece en:

• Planificación de recursos en la nube: Asignar VMs a servidores físicos respetando límites de CPU y RAM.
• Optimización de contenedores Docker/Podman: Seleccionar imágenes que maximizan funcionalidades dentro de un límite de tamaño de capa.
• Selección de características en Machine Learning: Elegir subconjunto de variables que maximiza precisión bajo una restricción de coste computacional.