Sesión 40: Grokking Algorithms (Capítulo 9, Parte 1) — La Mochila 0/1 (0/1 Knapsack) y Partición de Subconjuntos (LC 416)#

Navegación rápida:

• ← Sesión 39: CTCI Ch8 — DP: Triple Step y Robot en Grilla
• Sesión 41: CTCI Ch8 — DP: Coin Change y Permutaciones de Monedas →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_40.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión abordamos el problema arquetípico de optimización combinatoria bajo restricción de capacidad: la Mochila 0/1 y su aplicación a la partición exacta de conjuntos. Consulta el Glosario Maestro y la Guía de Diagramas.

Problema de la Mochila 0/1 (0/1 Knapsack Problem)#

• (a) En palabras simples (intuición): Eres un explorador con una mochila que soporta como máximo W kilogramos. Frente a ti hay una cueva con varios tesoros, cada uno con su propio peso y su valor en oro. No puedes partir una gema ni un cuadro en pedazos: o te lo llevas entero ($1$) o lo dejas en el suelo ($0$). ¿Qué combinación exacta de tesoros empacas para llevarte la mayor fortuna posible sin que se rompa la mochila?
• (b) Definición técnica paso a paso: Problema de optimización combinatoria NP-completo. Dado un conjunto de N elementos, donde cada elemento i posee un peso wᵢ ∈ ℕ y un valor vᵢ ∈ ℕ, y una capacidad máxima W ∈ ℕ, se busca un vector binario x ∈ {0, 1}^N que maximice:

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante una matriz Vec<Vec<u64>> de tamaño (N + 1) × (W + 1) asignada en el Heap, o un vector plano 1D Vec<u64> de capacidad W + 1 para máxima contigüidad espacial.
• (d) Error típico de Junior: Intentar resolverlo con una estrategia codiciosa (greedy) ordenando por ratio valor/peso; esta heurística solo funciona en la Mochila Fraccionaria, pero falla estrepitosamente en la 0/1 al dejar espacios inutilizables.

Ecuación de Recurrencia de Bellman (Inclusión vs Exclusión)#

• (a) En palabras simples (intuición): Para decidir qué hacer con el objeto que tienes en la mano, evalúas solo dos escenarios en tu cabeza:

1. Dejarlo: Tu ganancia es la misma que ya habías logrado con los objetos anteriores usando toda tu capacidad.
2. Llevarlo: Tu ganancia es el valor de este objeto más lo mejor que pudiste haber hecho antes con el espacio que te queda libre tras meterlo.

Eliges la opción que te deje más dinero.

• (b) Definición técnica paso a paso: Relación de optimalidad para el subproblema dp[i][w] (primeros i objetos con capacidad w):

• (c) Cómo funciona en Rust (memoria y tipos): Se evalúa mediante dos bucles for anidados. En Rust, la expresión idiomática es: dp[i][w] = dp[i - 1][w].max(v_item + dp[i - 1][w - w_item]);.
• (d) Error típico de Junior: Indexar los arreglos con desfase erróneo (off-by-one): en la fila i, el objeto correspondiente se encuentra en el índice i - 1 de los arreglos de entrada weights y values.

Bucle Inverso en Optimización 1D (.rev() / Evitar Reutilización)#

• (a) En palabras simples (intuición): Imagina una hilera de vasos que indican cuánta agua puedes guardar para cada capacidad. Si actualizas los vasos de izquierda a derecha, llenar el vaso de 2 litros con una botella puede hacer que luego uses esa misma botella ya vacía para llenar el vaso de 4 litros. Al recorrer de derecha a izquierda, siempre consultas vasos con el agua de la ronda anterior, garantizando que cada objeto se use a lo sumo una sola vez.
• (b) Definición técnica paso a paso: Técnica indispensable al comprimir la tabla 2D a un vector 1D de tamaño W + 1. Al iterar w en reversa desde W hasta wᵢ, el subproblema w - wᵢ aún conserva el valor proveniente de la iteración del ítem anterior (i - 1). Si se iterase en sentido ascendente, dp[w - wᵢ] ya habría sido sobrescrito con el ítem actual, transformando el algoritmo en Mochila Ilimitada (Unbounded Knapsack).
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante el iterador estándar inverso: for w in (w_item..=capacity).rev() { dp[w] = dp[w].max(v_item + dp[w - w_item]); }.
• (d) Error típico de Junior: Escribir w_item..=capacity en sentido forward por inercia, permitiendo que un ítem de peso 2 se empaque infinitas veces hasta saturar la mochila.

Reconstrucción de Estados por Backtracking sobre Matriz DP#

• (a) En palabras simples (intuición): Seguir el rastro de migas de pan desde la esquina inferior derecha del mapa hacia el inicio. Si el valor de la casilla actual es idéntico al de la casilla de arriba, significa que pudiste lograr esa fortuna sin usar el objeto actual (no lo empacaste). Si el valor subió respecto a la casilla de arriba, significa que obligatoriamente empacaste ese objeto.
• (b) Definición técnica paso a paso: Algoritmo de recuperación de testigos. Partiendo de (i = N, w = W), se compara dp[i][w] con dp[i - 1][w]. Si dp[i][w] ≠ dp[i - 1][w], se deduce que el ítem i - 1 fue seleccionado; se añade a la lista de salida y se decrementa la capacidad de rastreo: w = w - w_{i - 1}. El proceso se repite hasta que i = 0 o w = 0.
• (c) Cómo funciona en Rust (memoria y tipos): Opera sobre una referencia compartida &[Vec<u64>] y genera un vector de índices Vec<usize> asignado en el Heap.
• (d) Error típico de Junior: Intentar reconstruir la solución sobre la versión optimizada a 1D sin haber almacenado una matriz de decisiones; el arreglo 1D sobrescribe la historia y solo preserva el valor numérico escalar final, haciendo imposible recuperar los objetos originales sin re-computar.

Complejidad Pseudopolinomial (O(N · W) vs NP-Completo)#

• (a) En palabras simples (intuición): Un algoritmo es de tiempo polinomial si su velocidad depende solo de cuántos elementos le pasas en la lista. Si le pasas 100 números, tarda una fracción de segundo. Pero si uno de los parámetros es un número enorme (como capacidad 10,000,000,000), el algoritmo tendrá que dar miles de millones de vueltas solo por el valor de ese número, no por el tamaño de la lista.
• (b) Definición técnica paso a paso: La complejidad O(N · W) no es polinomial en el sentido estricto de la teoría de complejidad computacional. El tamaño de entrada de un entero W en bits es B = ⌈ log₂ W ⌉. Por lo tanto, el tiempo de ejecución en función del tamaño físico de la entrada en bits es O(N · 2^B), que es estrictamente exponencial. Por esta razón la Mochila 0/1 es NP-completo y su solución por DP es pseudopolinomial.
• (c) Cómo funciona en Rust (memoria y tipos): Si capacity es 10⁹, crear vec![0u64; capacity + 1] intentará alojar 8 GB de memoria contigua en el Heap, provocando un pánico inmediato por falta de memoria (allocation failure).
• (d) Error típico de Junior: Prometerle al entrevistador que "la mochila siempre corre en tiempo lineal O(N)", desconociendo el impacto devastador de un W astronómico.

Reducción de Partición de Subconjuntos (Subset Sum / LC 416)#

• (a) En palabras simples (intuición): Tienes una bolsa de monedas y quieres repartirlas entre dos hermanos para que ambos reciban exactamente la misma cantidad de dinero. Lo primero que haces es sumar todas las monedas: si la suma es impar (por ejemplo \15), sabes al instante que es imposible. Si la suma es par (por ejemplo20), el problema se reduce a encontrar un grupo de monedas que sume exactamente la mitad (\$10).
• (b) Definición técnica paso a paso: Reducción formal del problema Partition Equal Subset Sum a una Mochila 0/1 booleana. Dado un arreglo de enteros positivos:

1. Calcular S = sum_{i=1}^N nums[i].
2. Si S ±od 2 ≠ 0 ⟹ false.
3. Definir target = S / 2. Cada número se comporta simultáneamente como su propio peso y su propio valor (wᵢ = vᵢ = nums[i]). Se busca determinar si existe un subconjunto con suma acumulada exactamente igual a target.

• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante un vector booleano dp: Vec<bool> de tamaño target + 1, donde dp[0] = true y cada número actualiza en reversa: if dp[w - num] { dp[w] = true; }.
• (d) Error típico de Junior: Olvidar la verificación de paridad al principio o usar un tipo signed (i32) que permita valores negativos sin manejar los desplazamientos de índice.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

¿Por qué la Estrategia Voraz (Greedy) Fracasa Rotundamente?#

Consideremos el siguiente contraejemplo clásico:

• Capacidad de la mochila: W = 50 kg
• Ítem 1: Peso 10 kg, Valor \60 (Ratio:6/kg)
• Ítem 2: Peso 20 kg, Valor \100 (Ratio:5/kg)
• Ítem 3: Peso 30 kg, Valor \120 (Ratio:4/kg)

Enfoque Voraz por Ratio Valor/Peso:

1. Selecciona el Ítem 1 (10 kg, \$60). Capacidad restante: 50 - 10 = 40 kg.
2. Selecciona el Ítem 2 (20 kg, \$100). Capacidad restante: 40 - 20 = 20 kg.
3. El Ítem 3 pesa 30 kg, no cabe en los 20 kg restantes. Se descarta.

• Ganancia Voraz Total: 60 + \100 = mathbf{160}$ (Peso usado: 30 kg; 20 kg desperdiciados).

Enfoque Óptimo con Programación Dinámica:

• Selecciona el Ítem 2 (20 kg) y el Ítem 3 (30 kg).
• Peso total: 20 + 30 = 50 kg (Uso perfecto de la capacidad).
• Ganancia Óptima Total: 100 + \120 = mathbf{220}$.

La estrategia voraz perdió \$60 porque es miope: no puede anticipar que dejar ir un ítem con ratio alto permite empaquetar una combinación más densa que llene completamente la mochila.

La Demostración Matemática del Bucle Inverso (.rev())#

Veamos qué ocurre en la memoria al optimizar la tabla a un vector 1D dp[w].

Supongamos un único ítem con peso w₁ = 3 y valor v₁ = 10, en una mochila de capacidad W = 6. Inicialmente dp = [0, 0, 0, 0, 0, 0, 0].

Caso A: Bucle Hacia Adelante (Forward: 3..=6) — ¡ERROR!#

• w = 3: dp[3] = max(dp[3], 10 + dp[3 - 3]) = max(0, 10 + 0) = 10.
• w = 4: dp[4] = max(dp[4], 10 + dp[4 - 3]) = max(0, 10 + 0) = 10.
• w = 5: dp[5] = max(dp[5], 10 + dp[5 - 3]) = max(0, 10 + 0) = 10.
• w = 6: dp[6] = max(dp[6], 10 + dp[6 - 3]) = max(0, 10 + dp[3]).

¡Pero dp[3] acaba de ser actualizado a 10 en este mismo bucle! dp[6] = max(0, 10 + 10) = 20. Consecuencia: ¡El ítem 1 fue empacado dos veces! Esto resolvió la Mochila Ilimitada, violando la regla 0/1.

Caso B: Bucle en Reversa (Reverse: (3..=6).rev()) — CORRECTO#

• w = 6: dp[6] = max(dp[6], 10 + dp[6 - 3]) = max(0, 10 + dp[3]).

En este momento dp[3] sigue valiendo 0 (valor de la ronda anterior). dp[6] = max(0, 10 + 0) = 10.

• w = 5: dp[5] = max(dp[5], 10 + dp[2]) = max(0, 10 + 0) = 10.
• w = 4: dp[4] = max(dp[4], 10 + dp[1]) = max(0, 10 + 0) = 10.
• w = 3: dp[3] = max(dp[3], 10 + dp[0]) = max(0, 10 + 0) = 10.
• Resultado: Cada capacidad contiene a lo sumo una instancia del ítem. Invariante 0/1 estrictamente preservado.

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama de Transición de Estados#

Consulta el diagrama vectorial:

flowchart TD
    FOR_ITEM["Para cada ítem i con (peso w_i, valor v_i)"] --> REV_LOOP["Iterar w desde Capacidad W en REVERSA hasta w_i"]
    REV_LOOP --> DECIDE{"dp[w] < v_i + dp[w - w_i]"}
    DECIDE -->|Sí: Conviene empacar| UPDATE["dp[w] = v_i + dp[w - w_i]"]
    DECIDE -->|No: Mantener sin cambios| KEEP["dp[w] queda igual"]
    UPDATE --> MORE_W{"¿Quedan w >= w_i?"}
    KEEP --> MORE_W
    MORE_W -->|Sí| REV_LOOP
    MORE_W -->|No| NEXT_ITEM["Avanzar al siguiente ítem i + 1"]

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Consideremos la ejecución de knapsack_01_optimized(&[2, 3], &[4, 7], 4):

ESTADO INICIAL:
Stack: capacity = 4, weights = &[2, 3], values = &[4, 7]
Heap: dp = vec![0, 0, 0, 0, 0] (5 elementos u64, 40 bytes contiguos)
Índices:          0   1   2   3   4
dp antes de i=0: [0,  0,  0,  0,  0]

PROCESANDO ÍTEM 0: peso = 2, valor = 4. Rango w: (2..=4).rev() -> w = 4, 3, 2
- w = 4: dp[4] = max(dp[4], 4 + dp[4 - 2]) = max(0, 4 + dp[2]=0) = 4
- w = 3: dp[3] = max(dp[3], 4 + dp[3 - 2]) = max(0, 4 + dp[1]=0) = 4
- w = 2: dp[2] = max(dp[2], 4 + dp[2 - 2]) = max(0, 4 + dp[0]=0) = 4
Heap tras ítem 0:
Índices:          0   1   2   3   4
dp:              [0,  0,  4,  4,  4]

PROCESANDO ÍTEM 1: peso = 3, valor = 7. Rango w: (3..=4).rev() -> w = 4, 3
- w = 4: dp[4] = max(dp[4], 7 + dp[4 - 3]) = max(4, 7 + dp[1]=0) = 7
- w = 3: dp[3] = max(dp[3], 7 + dp[3 - 3]) = max(4, 7 + dp[0]=0) = 7
Heap tras ítem 1:
Índices:          0   1   2   3   4
dp:              [0,  0,  4,  7,  7]

VALOR FINAL RETORNADO: dp[4] = 7.
Costo total de memoria Heap: exactamente 40 bytes para capacidad 4.

4. Las 3 Trampas Clásicas en Entrevistas y Cómo Evitarlas#

Trampa 1: El Bucle Hacia Adelante en el Vector 1D (La Fuga a Mochila Ilimitada)#

• El error: Escribir for w in w_item..=capacity en lugar de for w in (w_item..=capacity).rev().
• Por qué falla: Sobrescribe los valores pequeños antes de calcular los valores grandes de la misma fila, permitiendo que un objeto sea empacado múltiples veces en una mochila 0/1.
• La solución: Memorizar la regla de oro:
• Mochila 0/1 (cada ítem 1 sola vez) ⟹ Bucle en Reversa (.rev()).
• Mochila Ilimitada / Coin Change (ítems infinitos) ⟹ Bucle Hacia Adelante (ascendente).

Trampa 2: Ignorar la Paridad de la Suma Total en Partition Equal Subset Sum (LC 416)#

• El error: Ejecutar el algoritmo DP directamente sin comprobar si total_sum % 2 != 0.
• Por qué falla: La división entera en Rust (total_sum / 2) trunca los decimales hacia abajo. Si la suma total es 11, 11 / 2 = 5. El algoritmo intentará buscar un subconjunto que sume 5; si lo encuentra (por ejemplo [2, 3]), responderá incorrectamente true, cuando en realidad el resto del arreglo sumará 11 - 5 = 6 ≠ 5.
• La solución: Colocar siempre el guardián de paridad:

  if total_sum % 2 != 0 { return false; }

Trampa 3: Intentar Reconstruir la Lista de Objetos con la Tabla Comprimida 1D#

• El error: El entrevistador te pide: "No solo me des el valor máximo, entrégame los nombres o índices de los ítems que metiste en la mochila", y tú intentas hacer backtracking sobre el arreglo 1D dp[w].
• Por qué falla: La compresión 1D es una optimización destructiva: al escribir el valor nuevo sobre el anterior, destruye la información sobre si el valor provino de la fila de arriba (i - 1) o de la celda desplazada (w - wᵢ).
• La solución: Informar proactivamente al entrevistador: "Para recuperar los ítems exactos se requiere preservar la matriz 2D de dimensiones (N + 1) × (W + 1), o bien almacenar una matriz booleana de decisiones de inclusión en espacio O(N · W)".

5. Implementación Canónica en Rust y Comparativa con Python#

Implementación en Rust (practica-rust/dia_40.rs)#

/// Mochila 0/1 con optimización espacial a arreglo 1D O(W) con iteración en reversa.
pub fn knapsack_01_optimized(
    weights: &[usize],
    values: &[u64],
    capacity: usize,
) -> u64 {
    assert_eq!(weights.len(), values.len());
    let mut dp = vec![0u64; capacity + 1];

    for (&w_item, &v_item) in weights.iter().zip(values.iter()) {
        if w_item > capacity {
            continue;
        }
        for w in (w_item..=capacity).rev() {
            dp[w] = dp[w].max(v_item + dp[w - w_item]);
        }
    }

    dp[capacity]
}

/// Reconstrucción exacta de los ítems seleccionados mediante backtracking sobre tabla 2D.
pub fn knapsack_01_items(
    weights: &[usize],
    values: &[u64],
    capacity: usize,
) -> (u64, Vec<usize>) {
    let n = weights.len();
    let mut dp = vec![vec![0u64; capacity + 1]; n + 1];

    for i in 1..=n {
        let w_item = weights[i - 1];
        let v_item = values[i - 1];
        for w in 0..=capacity {
            if w_item <= w {
                dp[i][w] = dp[i - 1][w].max(v_item + dp[i - 1][w - w_item]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    let mut w = capacity;
    let mut selected_indices = Vec::new();

    for i in (1..=n).rev() {
        if dp[i][w] != dp[i - 1][w] {
            selected_indices.push(i - 1);
            w -= weights[i - 1];
        }
    }

    selected_indices.reverse();
    (dp[n][capacity], selected_indices)
}

/// LeetCode 416: Partition Equal Subset Sum en espacio O(target).
pub fn can_partition_equal_subset_sum(nums: &[usize]) -> bool {
    if nums.len() < 2 {
        return false;
    }

    let total_sum: usize = nums.iter().sum();
    if total_sum % 2 != 0 {
        return false;
    }

    let target = total_sum / 2;
    let mut dp = vec![false; target + 1];
    dp[0] = true;

    for &num in nums {
        if num > target {
            continue;
        }
        for w in (num..=target).rev() {
            if dp[w - num] {
                dp[w] = true;
            }
        }
        if dp[target] {
            return true;
        }
    }

    dp[target]
}

Implementación en Python de Referencia (practica/dia_40_dp_knapsack_01_subset_sum.py)#

from typing import List, Tuple


def knapsack_01_optimized(weights: List[int], values: List[int], capacity: int) -> int:
    """Mochila 0/1 con optimización espacial a arreglo 1D O(W)."""
    dp = [0] * (capacity + 1)

    for w_item, v_item in zip(weights, values):
        for w in range(capacity, w_item - 1, -1):
            dp[w] = max(dp[w], v_item + dp[w - w_item])

    return dp[capacity]


def knapsack_01_items(
    weights: List[int], values: List[int], capacity: int
) -> Tuple[int, List[int]]:
    """Reconstrucción de índices mediante backtracking sobre matriz DP 2D."""
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        w_item, v_item = weights[i - 1], values[i - 1]
        for w in range(capacity + 1):
            if w_item <= w:
                dp[i][w] = max(dp[i - 1][w], v_item + dp[i - 1][w - w_item])
            else:
                dp[i][w] = dp[i - 1][w]

    w = capacity
    selected_indices: List[int] = []
    for i in range(n, 0, -1):
        if dp[i][w] != dp[i - 1][w]:
            selected_indices.append(i - 1)
            w -= weights[i - 1]

    selected_indices.reverse()
    return dp[n][capacity], selected_indices


def can_partition_equal_subset_sum(nums: List[int]) -> bool:
    """LeetCode 416: Partición en subconjuntos iguales."""
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False

    target = total_sum // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for w in range(target, num - 1, -1):
            if dp[w - num]:
                dp[w] = True
        if dp[target]:
            return True

    return dp[target]

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

  // Mochila 0/1 (Cada ítem a lo sumo 1 vez):
  for w in (w_item..=capacity).rev() { ... }

  // Mochila Ilimitada (Cada ítem reutilizable indefinidamente):
  for w in w_item..=capacity { ... }

7. Ejercicios de Práctica Independiente y Casos Límite#

1. Paso Límite 1: Arreglo con Elemento Superior a la Mitad (LC 416): - Dado nums = [100, 1, 2, 3], la suma total es 106 y el target es 53. El número 100 supera por sí solo el target. - Verifica que el filtro guardián if num > target { continue; } previene subdesbordamientos (underflow) en w - num.
2. Paso Límite 2: Mochila con Capacidad Exactamente Cero: - Para cualquier conjunto de ítems con capacity = 0, el resultado debe ser rigurosamente 0. Verifica que el vector vec![0u64; 1] maneje este caso sin accesos fuera de límites.
3. Paso Límite 3: Reducción a Target Sum (LeetCode 494): - Dado un arreglo de enteros positivos nums y un entero target, asigna signos + o - a cada elemento para que la suma total sea target. - Demuestra formalmente que este problema es idéntico a Subset Sum donde buscamos un subconjunto positivo con suma:
   subset_sum = (total_sum + target) / (2)

Navegación final:

• ← Sesión 39: CTCI Ch8 — DP: Triple Step y Robot en Grilla
• Sesión 41: CTCI Ch8 — DP: Coin Change y Permutaciones de Monedas →
• Glosario Maestro
• Guía de Diagramas de Arquitectura