Ir al contenido principal

Algoritmia II: algoritmos voraces

Imagen
De

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/)
Etiquetas:

Entradas populares de este blog

Un bot con Telegram en Termux

De
En las últimas semanas he retomado un par de ideas que tuve hace algunos años: por un lado la idea de hacer un Bot con el que hacer operaciones a través de comandos específicos. En concreto me gustaría hacer poder realizar comandos de inversión en bolsa (de manera ficticia) por otro lado desplegar la aplicación en un móvil con Termux (emulador de Linux para Android) Así que os cuento los pasos que he hecho para realizar estas tareas. Creación de Bot con Telegram Busca el contacto @BotFather (es el bot oficial de Telegram para crear otros Bots). Pulsa en Iniciar o escribe /start para comenzar. Escribe el comando: /newbot BotFather te pedirá que le pongas un nombre visible a tu Bot. Ejemplo: Nombre: MiBotJava Luego te pedirá un username único que termine en Bot. Ejemplo: Username: MiBotJava_bot Si el nombre de usuario está disponible, te dará un mensaje de éxito. Obtén el token Después de crear el Bot, BotFather te dará un mensaje como este: Done! Congratulations on your new bot. You wil...
Leer más

Spring Boot: Página inicial con Bootstrap

De
  Este es el segundo artículo de la serie sobre Spring Boot que comenzamos hace dos semanas, si quieres ver el primero puedes acceder pulsando aquí . En el primer artículo vimos cómo descargar nuestro proyecto configurado para nuestros intereses y listo para ser importado en nuestro IDE (nosotros usaremos Eclipse ). Lo primero que vamos a hacer es importar el proyecto: File -> Import Existing Maven Projects Seleccionamos el fichero pom.xml en la carpeta donde lo hemos descomprimido y esperamos unos segundos Cuando acabe la importación, esta es la estructura que nos aparecerá: Con Spring Boot no necesitamos configurar el servidor, ya se encarga él de facilitarnos la vida. Lo único que tenemos que hacer es arrancar la clase BootApplication.java , que se encargará de arrancar Tomcat y dejar nuestra aplicación funcionando en el puerto 8080.  Y si todo fuera bien, podríamos acceder a través de la URL:  http://localhost:8080/ Pero ahora mismo tenemos un error de conexión c...
Leer más

Control Parental en Windows: navegadores

De
  Este año, mis hijos ya han empezado a necesitar trabajar en casa con ordenadores. De momento, solo para navegar, con un par de aplicaciones web que les indican en el colegio. Pero claro, esto ya conlleva una serie de riesgos que estamos intentando paliar: Paso 1: aplicaciones no deseadas Los ordenadores que tenemos son Windows, y para empezar lo que hemos hecho es utilizar cuentas con contraseña: una cuenta con privilegios de administrador para nosotros (los padres), y otra sin privilegios para los niños. Con esto conseguimos que no puedan instalar nada que nosotros no queramos... Sí, se lo pueden saltar, pero todavía no lo saben. Paso 2: control de páginas que visitan Esto ya es más complicado. He estado buscando, incluso programando soluciones, pero al final he descubierto Kurupira : https://www.kurupira.net/en Básicamente, monitoriza todas las URLs que pasan por cualquier navegador (por cualquiera que esté instalado), sin utilizar proxy ni nada parecido. Por defecto, tiene un ...
Leer más