Mochila 0/1 y optimización del espacio
Deduzca la recurrencia de 0/1 knapsack, rellene la tabla bidimensional y redúzcala a un array unidimensional recorriendo la capacidad en orden inverso.
Mochila 0/1 y optimización del espacio es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
El problema de la mochila 0/1
El problema de la mochila 0/1: dados n ítems, cada uno con un peso w[i] y un valor v[i], y una mochila con capacidad W, elija ítems para maximizar el valor total sin superar la capacidad. Cada ítem se selecciona exactamente una vez (0 = omitirlo, 1 = seleccionarlo). Este problema es el arquetipo de una gran familia de problemas de programación dinámica de entrevistas, como partition-equal-subset-sum y target-sum.
Estado y recurrencia de la programación dinámica
Defina dp[i][c] como el valor máximo que se puede obtener utilizando los primeros i ítems con una capacidad c. Hay dos opciones para el ítem i: omitirlo (dp[i-1][c]) o seleccionarlo si w[i] <= c (dp[i-1][c-w[i]] + v[i]). La recurrencia es: dp[i][c] = max(dp[i-1][c], dp[i-1][c-w[i]] + v[i]) cuando w[i] <= c; de lo contrario, dp[i][c] = dp[i-1][c]. Caso base: dp[0][c] = 0 para todo c.
Implementación con una tabla de programación dinámica 2D
La tabla 2D tiene (n+1) x (W+1) entradas y se completa fila por fila para cada ítem. Después de completar todas las filas, dp[n][W] contiene el valor máximo. Esto se ejecuta en tiempo O(n × W) y utiliza espacio O(n × W): una complejidad seudopolinómica que resulta eficiente cuando W es pequeño.
def knapsack_2d(weights, values, W):
n = len(weights)
dp = [[0]*(W+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(W+1):
dp[i][c] = dp[i-1][c] # skip item i
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
return dp[n][W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_2d(weights, values, 8)) # 10Por qué se debe iterar sobre la capacidad en orden inverso en la programación dinámica 1D
La observación clave es que la fila i solo depende de la fila i-1. Por tanto, podemos utilizar un único arreglo 1D y actualizarlo en el mismo lugar. Sin embargo, si iteramos sobre la capacidad c de izquierda a derecha (de menor a mayor), el ítem i podría contarse dos veces: podríamos usar el valor actualizado de c-w[i], que ya incluye el ítem i. Iterar de derecha a izquierda (de mayor a menor) garantiza que cada ítem se utilice como máximo una vez en cada actualización de fila.
# Forward iteration (WRONG for 0/1 knapsack - counts items multiple times)
# for c in range(W+1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] may already use item i
# Backward iteration (CORRECT for 0/1 knapsack)
# for c in range(W, w-1, -1):
# dp[c] = max(dp[c], dp[c-w] + v) <-- dp[c-w] still from previous rowImplementación optimizada en espacio con programación dinámica 1D
Al conservar un solo arreglo e iterar sobre la capacidad desde W hasta w[i] en orden descendente, obtenemos el mismo resultado que con la tabla 2D utilizando espacio O(W). La complejidad temporal sigue siendo O(n × W). Es fundamental memorizar esta optimización espacial: los entrevistadores suelen pedirle que reduzca la mochila 2D a 1D.
def knapsack_1d(weights, values, W):
dp = [0] * (W + 1)
for i in range(len(weights)):
w, v = weights[i], values[i]
for c in range(W, w - 1, -1): # iterate RIGHT TO LEFT
dp[c] = max(dp[c], dp[c - w] + v)
return dp[W]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_1d(weights, values, 8)) # 10Reconstrucción de los ítems seleccionados
Para averiguar qué ítems se seleccionaron, necesita la tabla 2D completa. Después de completarla, comience en dp[n][W] y retroceda: si dp[i][c] != dp[i-1][c], el ítem i se incluyó; reste su peso a c y pase a la fila i-1. Continúe hasta que i = 0. La optimización 1D descarta esta capacidad de reconstrucción.
def knapsack_with_items(weights, values, W):
n = len(weights)
dp = [[0]*(W+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(W+1):
dp[i][c] = dp[i-1][c]
if c >= w:
dp[i][c] = max(dp[i][c], dp[i-1][c-w] + v)
# Reconstruct
selected, c = [], W
for i in range(n, 0, -1):
if dp[i][c] != dp[i-1][c]:
selected.append(i-1)
c -= weights[i-1]
return dp[n][W], selected[::-1]
print(knapsack_with_items([2,3,4,5],[3,4,5,6],8))Ejemplo práctico: maximizar el valor total
Considere los siguientes ítems: weights=[2,3,4,5], values=[3,4,5,6], W=8. La solución óptima consiste en seleccionar los ítems de peso 3 (valor 4) y peso 5 (valor 6): peso total 8 y valor 10. También se podrían seleccionar los pesos 2 y 5, con un valor total de 9, o los pesos 2 y 3, con un valor de 7. La programación dinámica encuentra correctamente el máximo, que es 10. Observe que el enfoque voraz (seleccionar primero el mayor cociente valor/peso) elegiría el ítem con cociente 1.5 (peso 2, valor 3), lo que no siempre es óptimo.
Mochila fraccionaria frente a mochila 0/1
En la mochila fraccionaria, puede seleccionar fracciones de los ítems. Se resuelve de forma voraz ordenando por el cociente valor/peso. En la mochila 0/1, los ítems son indivisibles: el enfoque voraz falla y se necesita programación dinámica. Los entrevistadores utilizan esta distinción para comprobar si sabe cuándo se puede aplicar un enfoque voraz. Si le preguntan por la variante fraccionaria, mencione inmediatamente el enfoque voraz con ordenación; si se trata de la variante 0/1, recurra a la programación dinámica.
# Fractional knapsack: greedy by value/weight ratio
def fractional_knapsack(weights, values, W):
items = sorted(zip(values, weights), key=lambda x: x[0]/x[1], reverse=True)
total = 0
for v, w in items:
if W >= w:
total += v; W -= w
else:
total += v * (W / w); break
return total
print(fractional_knapsack([2,3,4,5],[3,4,5,6],8))Complejidad temporal seudopolinómica
La mochila 0/1 es NP-completa, pero podemos resolverla en tiempo O(nW). La contradicción se resuelve porque O(nW) es seudopolinómica: W es un valor, no el tamaño de la entrada. La representación binaria de W ocupa O(log W) bits, por lo que la complejidad real es O(n × 2^(log W)), que es exponencial respecto al tamaño de la entrada. Cuando W es pequeño (por ejemplo, 10⁴), la programación dinámica resulta práctica; cuando W puede ser 10⁹, necesitamos otros enfoques.
Seguimiento del entrevistador: capacidad grande
Si el entrevistador establece que W es muy grande (por ejemplo, 10⁹), pero n es pequeño, la programación dinámica estándar deja de ser viable. Entre las alternativas se incluyen: (1) meet-in-the-middle en tiempo O(2^(n/2) × n), (2) una aproximación voraz para la variante fraccionaria, o (3) branch-and-bound. En la mayoría de los problemas de entrevistas con W <= 10⁵, la respuesta esperada es la programación dinámica 1D con iteración hacia atrás.
Meet-in-the-middle para capacidades grandes
Cuando W es muy grande pero n es pequeño (por ejemplo, n=40), la programación dinámica estándar O(nW) no es viable, pero la fuerza bruta 2^n es demasiado lenta. Meet-in-the-middle divide los ítems en dos mitades, enumera los 2^(n/2) subconjuntos de cada mitad y los empareja de forma óptima. Ordene una mitad por peso y, para cada subconjunto de la otra mitad, utilice búsqueda binaria para encontrar el mejor emparejamiento que respete la capacidad. Esto se ejecuta en O(2^(n/2) × n), por lo que resulta práctico para valores de n de hasta 40.
Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: la programación dinámica de la mochila 0/1 tiene un estado dp[i][c] que representa el valor máximo con i ítems y una capacidad c, la recurrencia decide si se omite o se selecciona cada ítem, y la optimización espacial 1D itera sobre la capacidad de derecha a izquierda para evitar contar dos veces los ítems. A continuación exploraremos la mochila ilimitada, en la que los ítems se pueden reutilizar, y la aplicaremos a Coin Change II.
Preguntas frecuentes
¿La lección «Mochila 0/1 y optimización del espacio» es gratis?
Sí — el texto completo de «Mochila 0/1 y optimización del espacio» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Mochila 0/1 y optimización del espacio»?
Deduzca la recurrencia de 0/1 knapsack, rellene la tabla bidimensional y redúzcala a un array unidimensional recorriendo la capacidad en orden inverso. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Mochila 0/1 y optimización del espacio»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Mochila 0/1 y optimización del espacio
- Mochila ilimitada y Coin Change II
- Suma de subconjunto con partición igual
- Target Sum con signos positivos y negativos