domingo, 19 de enero de 2020

Algoritmia II: algoritmos voraces


Los algoritmos voraces son muy fáciles de entender y de implementar, por lo que se usan muy a menudo en programación.

Imaginaros un problema como este: en la mesa hay diez fragmentos de tarta de diferente grosor y peso, y un comensal quiere elegir los dos trozos que sean más grandes.

Al utilizar un algoritmo voraz, primero seleccionará el elemento de mayor peso y grosor, una vez seleccionado ya no puede volver a elegirlo, porque el algoritmo se lo ha "comido", de ahí su nombre.

Para solucionar el problema anterior mediante un algoritmo voraz podríamos realizar los siguientes pasos:

  1. recorremos los diez fragmentos de tarta buscando el mas grande
  2. escogemos el más grande
  3. recorremos los nueve fragmentos restantes buscando el más grande
  4. escogemos el más grande

Seguro que se os ocurren un par de formas de optimizarlo (como ordenar previamente los trozos).

Ahora vamos con un problema un poco más complejo:

En Tecnificados hemos organizado un festival de cine de terror. Durante 24 horas se proyectarán N películas diferentes en las 10 salas disponibles de cine de Metro City (cada película solo se proyectará una vez a lo largo del festival). En la programación aparecen todas las películas que se van a proyectar, junto con el título, duración de la película y otros datos, se indica la sala de proyección y la hora de comienzo.

Una persona desea planificar su maratón de cine, teniendo en cuenta que el único objetivo es ver el máximo número posible de películas. 

Debemos realizar un algoritmo voraz para realizar ese maratón.

La solución en nuestro repositorio: https://github.com/tecnificados/algoritmos/tree/master/voraz

(Imagen Principal generada con https://es.cooltext.com/)