Mochila optimizada en espacio
Reduzca una matriz 2D a una sola fila
Mochila optimizada en espacio es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 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 Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Por qué optimizar el espacio
Una tabla completa consume n por cap de memoria, lo que puede dispararse con entradas grandes. La optimización de espacio lo reduce a una sola fila reutilizable.
Solo importa la última fila
Observe que cada celda solo lee la fila anterior, nunca nada más antiguo. Por tanto, no necesita almacenar toda la cuadrícula a la vez.
Reduzca a un arreglo
Mantenga un único arreglo dp de longitud cap+1. Al procesar cada objeto, sobrescríbalo en el mismo lugar para representar la nueva fila.
dp = [0] * (cap + 1)La trampa de la reutilización
Si recorre la capacidad de izquierda a derecha, dp[w - wt[i]] puede haberse actualizado ya para este mismo objeto. Eso permitiría tomar el objeto i dos veces.
Recorra la capacidad hacia atrás
La solución consiste en recorrer la capacidad de mayor a menor. Avanzar hacia atrás garantiza que dp[w - wt[i]] todavía contenga el valor de la fila anterior.
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Por qué funciona hacia atrás
Al calcular dp[w], el índice menor w - wt[i] todavía no se ha modificado en esta ronda, por lo que refleja la fila superior como se esperaba.
Deténgase pronto en el peso
Las capacidades inferiores a wt[i] no pueden contener el objeto, así que el bucle se detiene en wt[i]. Omitirlas ahorra algunos ciclos innecesarios.
El bucle completo
Toda la solución consta de dos bucles anidados sobre un único arreglo. Los objetos en el exterior, la capacidad hacia atrás en el interior y la respuesta aparece por sí sola.
for i in range(n):
for w in range(cap, wt[i] - 1, -1):
dp[w] = max(dp[w], val[i] + dp[w - wt[i]])Lea la celda final
Después de procesar todos los objetos, dp[cap] contiene el valor máximo. Es el mismo número que produciría la tabla 2D, pero usando mucha menos memoria.
El mismo tiempo, menos memoria
No ha acelerado el algoritmo: sigue realizando un trabajo de orden n por cap. Solo ha reducido la memoria de cuadrática a lineal.
Cuándo resulta útil
Este recurso le ayuda cuando cap es grande y la cuadrícula 2D superaría el límite de memoria. Es una técnica habitual en concursos que merece la pena memorizar.
Comprobación rápida
Ponga a prueba la regla fundamental de la mochila 1D.
Resumen
Ha reducido la tabla 2D a un arreglo y ha recorrido la capacidad hacia atrás para mantener la corrección, cambiando memoria cuadrática por memoria lineal. 🚀
Preguntas frecuentes
¿La lección «Mochila optimizada en espacio» es gratis?
Sí — el texto completo de «Mochila optimizada en 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 Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Mochila optimizada en espacio»?
Reduzca una matriz 2D a una sola fila Practicas Coding 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 Coding Interview Prep?
No se requiere experiencia previa. Coding 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 2 de 4.
¿Cuánto tiempo toma la lección «Mochila optimizada en 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 Coding Interview Prep?
Sí. Cada lección de Coding 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: elegir o dejar
- Mochila optimizada en espacio
- DP de mochila ilimitada y cambio de monedas
- Suma de subconjuntos y partición