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

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

Redirección de puertos en Virtual Box

De
Continuando con mis anteriores "posts", vamos a terminar nuestro entorno de pruebas redirigiendo los puertos que nos interesan de la máquina virtual a nuestro PC. Con Virtual Box podemos configurar la red de diversas formas, una de ellas es redireccionar los puertos de la máquina virtual a la nuestra. Es bastante fácil y rápido de configurar, y lo que hace es que tengamos unos puertos destinados al entorno de desarrollo y otros para el entorno de pruebas. Ejemplo de uso:  - podemos usar el puerto 8080 para desarrollar en eclipse en nuestro entorno de desarrollo con Tomcat. - usaremos el puerto 80 para el Tomcat del entorno de pruebas Más adelante veremos cómo configurar las redes de virtual box para que sean máquinas independientes conectadas a nuestra red y más opciones. Vamos a hacer la redirección del puerto 22 para poder acceder a nuestra máquina virtual a través de uno de los clientes ssh más extendidos (y con nombre controvertido): ...
Leer más

ASP.Net MVC: Subida de imágenes al servidor y recorte con Jcrop

De
Recientemente tuve que incluir, en un proyecto de ASP.Net MVC en el que estoy trabajando, un formulario donde un usuario podía subir su foto al perfil, y si el sistema detectaba que el tamaño de la imagen subida superaba el 100x100, había que recortarla. Esta premisa, aunque parece sencilla, encierra varios problemas técnicos a solucionar: 1) Subida de ficheros al servidor con ASP.Net MVC. 2) Recorte de foto y guardado. 3) Puntos a tener en cuenta: versiones de navegadores y otros aspectos técnicos. Vamos a ir viendo paso a paso cómo implementar esta práctica funcionalidad. Subida de ficheros al servidor con ASP.Net MVC Para subir ficheros al servidor desde la Vista, en Mvc se dispone de la clase System.Web.HttpPostedFileBase.  Para utilizarla, hay que seguir los pasos: - Declarar una propiedad de este tipo en el Model que se va a utilizar: public HttpPostedFileBase Fichero { get; set; } - Crear en la vista el formulario para realizar la subida ...
Leer más