Elegir lo mejor que tienes delante

Agarra lo mejor ahora

Debes dar 870 de cambio.
¿Cómo lo haces?
La forma voraz es simple.
Agarra primero "la moneda más grande
que puedas usar ahora".
Un 500,
tres de 100,
un 50,
dos de 10.
Solo agarraste la más grande cada vez,
y quedó listo en un instante.

Haz clic primero en la moneda más grande. (870 → 500 · 100 · 100 · 100 · 50 · 10 · 10)

Esto es un algoritmo voraz.
No sopesa
cómo saldrán las cosas después.
Solo elige "lo mejor
en este preciso momento".
La cuenta es ligera,
así que la decisión es rápida.

No mira el conjunto

Este es el rasgo real de lo voraz.
Nunca despliega el mapa entero.
En cada bifurcación
solo da un paso
hacia "lo que se ve mejor ahora".
Como no mira lejos hacia adelante,
hay poco lío y es rápido.
A cambio, una vez que elige,
no mira atrás.

En cada bifurcación haz clic en el número mayor, paso a paso. El mapa entero queda oculto; eliges solo entre los dos que tienes delante.

No mirar el conjunto
es una fuerza y una debilidad.
Rápido es la fuerza.
Pero como no ve lejos,
el camino que se ve bien ahora
podría ser un callejón sin salida después.
Aun así, para algunos problemas
este método rápido
resulta encajar perfecto.

Cuando funciona

Quieres meter cuantas reuniones
puedas en una sola sala.
Sin solapamientos.
El truco voraz es
agarrar primero "la reunión que termina más temprano".
Cuanto antes se libera la sala,
más caben después.
Esta pizca de codicia, increíblemente,
te da la respuesta de verdad mejor.

Haz clic primero en la reunión que termina más temprano. Los solapes se descartan solos, y lo voraz mete el máximo, cuatro.

¿Por qué es la respuesta correcta?
Elige la que termina más temprano
y la sala se libera lo antes posible.
Queda el mayor tiempo abierto,
así que caben dentro
la mayor cantidad de otras reuniones.
Así que aun siendo voraz paso a paso,
el conjunto sale el mejor.
Para problemas así, lo voraz es la respuesta.

El caso donde se equivoca

Esta vez las monedas son raras.
Solo hay de 1, 3 y 4.
Debes devolver 6.
Ve voraz, la más grande primero:
una de 4, luego dos de 1.
Tres monedas.
Pero ¿y dos de 3?
Eso se resuelve con dos monedas.
Lo mejor que tenías delante
se perdió lo mejor en total.

Haz clic para comparar las dos vías. Voraz (4·1·1 = 3 monedas) frente a la mejor (3·3 = 2 monedas). Lo voraz cayó en la trampa.

Lo voraz falló porque
en cuanto agarró el 4,
los 2 que sobraban solo podían
llenarse con dos de 1.
El paso grande de ahora
arruinó lo que vino después.
Así que con monedas normales acierta,
pero con monedas torcidas como estas falla.
Si lo voraz sirve
hay que comprobarlo en cada problema.

En resumen

Un algoritmo voraz en una línea va así.
En cada paso, elige lo que se ve mejor ahora.
Al no mirar el conjunto, es rápido y simple.
Para algunos problemas, como el cambio o la sala de reuniones,
esta es justo la respuesta correcta.
Pero con monedas raras
o un camino enredado,
lo mejor que tienes delante se vuelve una trampa.
Así que lo voraz es rápido y acierta seguido,
pero si de verdad acierta hay que comprobarlo en cada problema.

Haz clic en los cuatro puntos clave en orden para cerrar. Mejor ahora → sin vista del conjunto → acierta seguido → a veces falla.

Lo voraz es la forma más simple de codicia.
Elige lo bueno de ahora y avanza.
Atrae por ser rápido y ligero,
pero esa simpleza a veces tropieza en una trampa.
Si le agarraste el tacto
a cuándo funciona y cuándo no,
ahora puedes sumar una cosa más:
un método más cuidadoso que sopesa todo.
Eso queda para la próxima.