CREO EN MI….

Programacion

                                                   ¿Planificando asistir a una convención?

La Universidad tiene ha planificado un evento cultural que consiste en n conferencias que se celebraran en 10 aulas diferentes. Cada conferencia se celebra una sola vez y se conoce el aula donde se celebra, la hora de comienzo y su duración. Un alumno desea sacar el mayor partido posible a este evento cultural, teniendo en cuenta que el único objetivo es asistir al máximo número posible de conferencias, desarrolla un algoritmo voraz que solucione el problema.

Lo primero para resolver el problema es crear los tipos adicionales que vamos a utilizar, en este caso solo tendremos que añadir uno para almacenar los datos relativos a cada conferencia:

01 struct Conferencia {
02     public Conferencia(int a, int h, int d) {
03         this.aula = a;
04         this.hora = h;
05         this.duración = d;
06     }
07     public int aula;
08     public int hora;
09     public int duración;
10 }

Después diseñamos el algoritmo que va a realizar la planificación. Nuestra función objetivo es maximizar el número de charlas a las que asistir. Para ello lo que haremos será  tomar todas las que quedan en un momento X en el que estamos libres, y buscar la primera que termine antes (que no es lo mismo que buscar la que menos dure).

01 static Conferencia[] Planificar(Conferencia[] lista) {
02     List<Conferencia> r = new List<Conferencia>();
03     List<Conferencia> aux = null;
04     Conferencia candidato;
05     int hora = 0;
06   
07     aux = lista.Where(x => x.hora >= hora)
08                .OrderBy(x => x.hora + x.duración)
09                .ToList();
10   
11     while(aux.Count() > 0) {
12         candidato = aux.First();
13         r.Add(candidato);
14         hora += candidato.duración;
15         aux = aux.Where(x => x.hora >= hora).ToList();
16     }
17   
18     return r.ToArray();
19 }

Como se puede ver, para poder montar el chiringuito, tendremos que ordenar la lista en relación a la hora a la que finalicen las charlas. Con la lista ordenada, siempre que queden futuras charlas, tomaremos la primera y actualizaremos la marca del tiempo, para volver a filtrar la lista, eliminando las que ya no se puede asistir porque están empezadas o terminadas.

01 public static void Resolver() {
02     Conferencia[] lista =
03     {
04         new Conferencia(1, 0, 60), new Conferencia(1, 60, 60),
05         new Conferencia(1, 120, 60), new Conferencia(1, 180, 60),
06         new Conferencia(1, 240, 60),
07   
08         new Conferencia(2, 10, 30), new Conferencia(2, 45, 30),
09         new Conferencia(2, 80, 30), new Conferencia(2, 115, 45),
10         new Conferencia(2, 165, 45), new Conferencia(2, 215, 45),
11   
12         new Conferencia(3, 0, 30), new Conferencia(3, 60, 90),
13         new Conferencia(3, 160, 60), new Conferencia(3, 240, 40),
14   
15         new Conferencia(4, 0, 45), new Conferencia(4, 60, 30),
16   
17         new Conferencia(5, 20, 60), new Conferencia(5, 90, 30),
18   
19         new Conferencia(6, 120, 30), new Conferencia(6, 160, 60),
20         new Conferencia(6, 230, 40),
21   
22         new Conferencia(7, 150, 30), new Conferencia(7, 180, 50),
23         new Conferencia(7, 230, 40),
24   
25         new Conferencia(8, 0, 60), new Conferencia(8, 90, 90),
26         new Conferencia(8, 190, 40), new Conferencia(8, 240, 30),
27   
28         new Conferencia(9, 0, 50), new Conferencia(9, 60, 50),
29         new Conferencia(9, 120, 90), new Conferencia(9, 230, 30),
30         new Conferencia(9, 260, 30),
31   
32         new Conferencia(10, 0, 90), new Conferencia(10, 90, 90),
33         new Conferencia(10, 180, 90)
34     };
35   
36     Conferencia[] result = Planificar(lista);
37     foreach(Conferencia i in result) {
38         Console.WriteLine("Aula {0} hora {1} duración {2}",
39                           i.aula, i.hora, i.duración);
40     }
41 }

Y aquí está el ejemplo de función de entrada al problema. No sé si hay alguna combinación que pueda dar una planificación que no sea óptima, pero parece intuitivo que para poder ir al máximo número posible, tengamos que ir asistiendo a las que acaben antes, que entre otras cosas serán siempre charlas cortas, por lo que podremos en un mismo periodo de tiempo asistir a más que otras cuya duración sea mayor. Pero nuevamente, para poder demostrar esto habría que realizar una demostración por inducción.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s