Algoritmos voraces con ordenamiento

Recursos

Video de YouTube (cG5kt0zzbes)

Introducción

Un algoritmo voraz (greedy) elige el mejor movimiento en cada paso individual, con la esperanza de alcanzar el mejor resultado global.

Por lo general, al usar un algoritmo voraz hay una función de valor que determina qué elección se considera más óptima. Por ejemplo, a menudo queremos maximizar o minimizar cierta cantidad, así que tomamos el valor más grande o más pequeño posible en el siguiente paso.

Aquí nos concentraremos en problemas en los que interviene algún paso de ordenamiento.

Ejemplo - Studying Algorithms

Steph quiere mejorar su conocimiento de algoritmos durante las vacaciones de invierno. Tiene un total de $X$ ($1 \leq X \leq 10^4$) minutos para dedicar a aprender algoritmos. Hay $N$ ($1 \leq N \leq 100$) algoritmos, y cada uno de ellos requiere $a_i$ ($1 \leq a_i \leq 100$) minutos para aprenderlo. Hallar la cantidad máxima de algoritmos que puede aprender.

Solución - Studying Algorithms

La primera observación es que Steph debería priorizar aprender algoritmos de más fácil a más difícil; en otras palabras, empezar por el algoritmo que requiere menos tiempo y luego elegir los siguientes en orden creciente de tiempo requerido. Veamos el siguiente ejemplo:

Después de ordenar el arreglo, tenemos $\{ 3, 3, 4, 4, 7, 8 \}$. En un máximo de 15 minutos, Steph puede aprender cuatro algoritmos en un total de $3+3+4+4 = 14$ minutos.

La implementación de este algoritmo es muy simple. Ordenamos el arreglo y luego tomamos tantos elementos como sea posible mientras la suma de los tiempos de los algoritmos elegidos hasta el momento sea menor que $X$. Ordenar el arreglo toma tiempo $\mathcal{O}(N \log N)$, e iterar sobre el arreglo toma tiempo $\mathcal{O}(N)$, para una complejidad temporal total de $\mathcal{O}(N \log N)$.

// read in the input, store the algorithms in a vector, algorithms
sort(algorithms.begin(), algorithms.end());
int count = 0;  // number of minutes used so far
int i = 0;
while (i < N && count + algorithms[i] <= x) {
	// while there is enough time, learn more algorithms
	count += algorithms[i];
	i++;
}
cout << i << endl;  // print the ans

// read in the input, store the algorithms in int[] algorithms
Arrays.sort(algorithms);
int count = 0;  // number of minutes used so far
int i = 0;
while (i < N && count + algorithms[i] <= x) {
	// while there is enough time, learn more algorithms
	count += algorithms[i];
	i++;
}
pw.println(i);  // print the ans
pw.close();

# read in the input, store the algorithms in a list, algorithms
algorithms.sort()
count = 0  # number of minutes used so far
i = 0
while i < N and count + algorithms[i] <= x:
	# while there is enough time, learn more algorithms
	count += algorithms[i]
	i += 1
print(i)  # print the ans

Ejemplo - The Scheduling Problem

Hay $N$ eventos, cada uno descrito por sus tiempos de inicio y de fin. Solo podemos asistir a un evento a la vez, y si elegimos asistir a un evento, debemos asistir al evento completo. El viaje entre eventos es instantáneo. ¿Cuál es la cantidad máxima de eventos a los que podemos asistir?

Voraz incorrecto - Siguiente evento que empieza más temprano

Un posible orden para un algoritmo voraz consistiría en seleccionar siempre el siguiente evento posible que empiece lo antes posible. Veamos el siguiente ejemplo, donde los eventos seleccionados están resaltados en rojo:

En este ejemplo, el algoritmo voraz selecciona dos eventos, lo cual es óptimo. Sin embargo, esto no siempre funciona, como muestra el siguiente contraejemplo:

En este caso, el algoritmo voraz selecciona asistir a un solo evento. Sin embargo, la solución óptima sería la siguiente:

Voraz correcto - Siguiente evento que termina más temprano

En su lugar, podemos seleccionar el evento que termina lo antes posible. Esto selecciona correctamente los tres eventos.

De hecho, este algoritmo siempre funciona. Una breve explicación de la corrección es la siguiente. Si tenemos dos eventos $E_1$ y $E_2$, con $E_2$ terminando más tarde que $E_1$, entonces siempre es óptimo seleccionar $E_1$. Esto se debe a que seleccionar $E_1$ nos da más opciones para eventos futuros. Si podemos seleccionar un evento para ir después de $E_2$, entonces ese evento también puede ir después de $E_1$, porque $E_1$ termina primero. Así, el conjunto de eventos que pueden ir después de $E_2$ es un subconjunto de los eventos que pueden ir después de $E_1$, lo que hace de $E_1$ la elección óptima.

Para el siguiente código, digamos que tenemos el arreglo events de eventos, cada uno con un punto de inicio y uno de fin.

// read in the input, store the events in pair<int, int>[] events.
sort(events, events + n);                       // sorts by first element (ending time)
int currentEventEnd = -1;                       // end of event currently attending
int ans = 0;                                    // how many events were attended?
for (int i = 0; i < n; i++) {                   // process events in order of end time
	if (events[i].second >= currentEventEnd) {  // if event can be attended
		// we know that this is the earliest ending event that we can attend
		// because of how the events are sorted
		currentEventEnd = events[i].first;
		ans++;
	}
}
cout << ans << endl;

static class Event implements Comparable<Event> {
	int start;
	int end;
	public Event(int s, int e) {
		start = s;
		end = e;
	}
	public int compareTo(Event e) { return Integer.compare(this.end, e.end); }
}

// read in the input, store the events in Event[] events.
Arrays.sort(events);                           // sorts by comparator we defined above
int currentEventEnd = -1;                      // end of event currently attending
int ans = 0;                                   // how many events were attended?
for (int i = 0; i < n; i++) {                  // process events in order of end time
	if (events[i].start >= currentEventEnd) {  // if event can be attended
		// we know that this is the earliest ending event that we can attend
		// because of how the events are sorted
		currentEventEnd = events[i].end;
		ans++;
	}
}
pw.println(ans);
pw.close();

# read in the input, store the events in [begin, end] format in list events.
events.sort(key=lambda x: x[1])
# sorts by second element (ending time)
currentEventEnd = -1
ans = 0  # how many events were attended?
for i in range(n):  # process events in order of end time
	if events[i][0] >= currentEventEnd:  # if event can be attended
		# we know that this is the earliest ending event that we can attend
		# because of how the events are sorted
		currentEventEnd = events[i][1]
		ans += 1
print(ans)

Cuándo falla lo voraz

Daremos algunos ejemplos habituales de cuándo falla lo voraz, para evitar caer en trampas evidentes y perder tiempo obteniendo respuestas incorrectas en un contest.

Cambio de monedas

Este problema da varias denominaciones de monedas y pide la cantidad mínima de monedas necesarias para formar cierto valor. Los algoritmos voraces se pueden usar para resolver este problema solo en casos muy específicos (se puede demostrar que funciona para el sistema de monedas estadounidense y también para el del euro). Sin embargo, no funciona en el caso general. Por ejemplo, sean las denominaciones $\{1, 3, 4\}$, y digamos que el valor que queremos es 6. La solución óptima es $\{3, 3\}$, que requiere solo dos monedas, pero el método voraz de tomar la moneda de mayor valor posible que cabe en la denominación restante da la solución $\{4, 1, 1\}$, que es incorrecta.

Mochila (knapsack)

El problema de la mochila da una cantidad de ítems, cada uno con un peso y un valor, y queremos elegir un subconjunto de estos ítems. Estamos limitados a cierto peso, y queremos maximizar el valor de los ítems que tomamos.

Tomemos el siguiente ejemplo, donde tenemos una capacidad máxima de 4:

Si usamos voraz basado en el mayor valor primero, elegimos el ítem A y terminamos, porque no nos queda peso para encajar ninguno de los otros dos. Usar voraz basado en valor por peso otra vez selecciona el ítem A y luego termina. Sin embargo, la solución óptima es seleccionar los ítems B y C, ya que juntos tienen un valor mayor que el ítem A solo. De hecho, no hay una solución voraz que funcione. La solución de este problema usa programación dinámica, que se cubre en Oro.

Problemas

CSES

Otros