Mochila fraccionaria por proporción
Elija primero el mayor valor por unidad de peso
Mochila fraccionaria por proporción es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 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.
La configuración de la mochila
Tiene objetos con un valor y un peso, además de una mochila con capacidad limitada. El objetivo es transportar el mayor valor total posible. 🎒
Fraccionaria significa divisible
En la versión fraccionaria puede tomar una parte de un objeto, como medio saco de grano. Esta libertad es lo que permite que greedy funcione en este caso.
Valor por peso
La métrica clave es la proporción entre el valor y el peso de cada objeto. Una proporción alta significa mucho valor concentrado en muy poco espacio.
ratio = value / weightOrdenar por la mejor proporción
Ordene los objetos por valor por peso, de mayor a menor. El plan greedy consiste en tomar siempre el valor más denso disponible.
items.sort(key=lambda i: i[0] / i[1], reverse=True)Tomar el objeto completo mientras quepa
Recorra la lista ordenada y tome cada objeto completo si todavía cabe en la capacidad restante. Añada todo su valor al total.
if weight <= cap:
total += value
cap -= weightRellenar el último espacio
Cuando un objeto sea demasiado grande, tome una fracción que llene exactamente el espacio restante. Entonces la mochila estará llena y podrá detenerse.
total += value * (cap / weight)Por qué funciona el orden por proporción
Cada unidad de capacidad debe contener el mayor valor posible, así que el objeto más denso debe ir primero. Sustituirlo por uno de menor densidad solo reduce el valor.
La mochila 0/1 es diferente
Si los elementos no se pueden dividir, ordenarlos vorazmente por proporción deja de funcionar. La versión 0/1 requiere programación dinámica, no esta ordenación sencilla.
El tiempo de ejecución
Ordenar por proporción cuesta O(n log n), y el bucle de llenado es lineal. Es más que suficiente para los límites habituales de los concursos.
Tenga cuidado con la fracción final
Use números de coma flotante o racionales exactos para el elemento parcial. Truncar demasiado pronto puede reducir el valor y producir una respuesta incorrecta.
Dónde aparece
Piense en cargar mercancías, mezclar combustibles o dividir recursos. Siempre que los elementos se puedan dividir, la estrategia voraz basada en proporciones es su herramienta.
Comprobación rápida
Está llenando una bolsa en el problema de la mochila fraccionaria.
Resumen
Ordene los elementos por valor por peso, tome elementos completos mientras quepan y, después, una fracción para llenar la bolsa. Este algoritmo voraz solo es óptimo cuando los elementos se pueden dividir. 🚀
Preguntas frecuentes
¿La lección «Mochila fraccionaria por proporción» es gratis?
Sí — el texto completo de «Mochila fraccionaria por proporción» 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 fraccionaria por proporción»?
Elija primero el mayor valor por unidad de peso 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 3 de 4.
¿Cuánto tiempo toma la lección «Mochila fraccionaria por proporción»?
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
- La mentalidad greedy
- Selección de actividades por finalización más temprana
- Mochila fraccionaria por proporción
- Detecte cuándo falla greedy