Mochila 0/1: elegir o dejar
Maximice el valor con un límite de peso
Mochila 0/1: elegir o dejar es una lección gratuita de Competitive Programming Academy 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 Competitive Programming Academy, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Competitive Programming Academy incluye 4 lecciones en total.
La historia de la mochila
Tiene una bolsa con un límite de peso y un montón de objetos. La mochila 0/1 pregunta: ¿qué objetos maximizan el valor sin sobrepasar la capacidad? 🎒
Tomar o dejar
La expresión 0/1 significa que cada objeto se toma por completo o se omite por completo. Nunca puede tomar solo una parte, así que cada elección es sí o no.
Por qué greedy falla
Tomar primero el objeto más barato o el de mayor valor puede desperdiciar capacidad. El atajo greedy falla aquí, por lo que debe considerar las combinaciones reales.
Las dos entradas
Se le proporcionan dos listas paralelas: un peso y un valor para cada objeto, además de una capacidad. El objeto i tiene peso wt[i] y valor val[i].
wt = [1, 3, 4, 5]
val = [1, 4, 5, 7]
cap = 7Defina el estado
Sea dp[i][w] el mejor valor usando los primeros i objetos con capacidad w. Nombrar el estado con precisión es lo más importante.
La opción de omitir
Si omite el objeto i, su valor es el que ya tenía: dp[i-1][w]. La capacidad permanece intacta para el resto.
La opción de tomar
Si toma el objeto i, sume su valor y reduzca la capacidad: val[i] + dp[i-1][w - wt[i]]. Esto solo es válido cuando w es al menos wt[i].
Elija la mejor alternativa
La recurrencia simplemente conserva con max la mayor de las dos opciones. Cada celda se basa en las respuestas ya calculadas debajo de ella.
dp[i][w] = max(dp[i-1][w],
val[i] + dp[i-1][w - wt[i]])La fila base
Con cero objetos, puede transportar un valor cero con cualquier capacidad. Ese caso base rellena la primera fila con ceros para construir a partir de ella.
dp = [[0] * (cap + 1) for _ in range(n + 1)]Rellene la tabla
Recorra los objetos en el bucle exterior y las capacidades en el interior. Cada celda solo lee la fila superior, así que un único recorrido lo rellena todo.
for i in range(1, n + 1):
for w in range(cap + 1):
dp[i][w] = dp[i-1][w]Lea la respuesta
La celda inferior derecha dp[n][cap] contiene el valor máximo para todos los objetos y la capacidad completa. Esa única celda es la respuesta final.
Comprobación rápida
Ponga a prueba la recurrencia fundamental de la mochila 0/1.
Resumen
Ha aprendido la mochila 0/1: cada objeto se toma o se deja, dp[i][w] conserva el mejor resultado entre omitirlo y tomarlo, y dp[n][cap] es la respuesta. 🎉
Preguntas frecuentes
¿La lección «Mochila 0/1: elegir o dejar» es gratis?
Sí — el texto completo de «Mochila 0/1: elegir o dejar» 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 Competitive Programming Academy, actualiza a CoddyKit PRO. El curso de Competitive Programming Academy incluye 4 lecciones en total.
¿Qué aprenderé en «Mochila 0/1: elegir o dejar»?
Maximice el valor con un límite de peso Practicas Competitive Programming Academy 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 Competitive Programming Academy?
No se requiere experiencia previa. Competitive Programming Academy 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: elegir o dejar»?
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 Competitive Programming Academy?
Sí. Cada lección de Competitive Programming Academy 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