Menú principal
Applet | Mochila voraz
Parámetros
Código Python
Visualizador
Capacidad: 0 / 100
Valor total: 0.0
Parámetros
- En el campo Ítems deberás introducir los objetos de la mochila representados mediante pares valor, peso, separados a su vez por puntos y comas (;).
- En el campo Capacidad máxima deberás deberás indicar el límite de capacidad de la mochila.
- El deslizador Velocidad controla la velocidad a la que se ejecuta el algoritmo.
- Los botones de colores permiten iniciar la simulación del algoritmo, pausarla, avanzarla paso a paso y reiniciarla.
Sobre este algoritmo
En el problema de la mochila, dado un conjunto de ítems, donde cada uno tiene asociado un peso (o coste) y un valor, el objetivo consiste en determinar qué ítems se deben seleccionar para que el peso o coste total no exceda un límite establecido, manteniendo el valor total lo más alto posible.
Esta variante en particular recibe el nombre de mochila fraccional (o mochila voraz), ya que permite tomar una parte fraccionaria de cualquier ítem. Esta condición hace que el problema pueda resolverse de forma óptima mediante un algoritmo voraz.
Mochila voraz
Problema de la mochila