Un algoritmo codicioso es un algoritmo que en cada paso elige la variante óptima (dentro del paso actual) con la expectativa de que la solución final sea óptima en el sentido global.
Pequeño ejemplo:
Supongamos que tenemos un número ilimitado de monedas de diferentes denominaciones y necesitamos recolectar la cantidad S. Consideremos dos casos específicos, cada uno de los cuales intentaremos resolver con un algoritmo codicioso.
Es decir, actuaremos de la siguiente manera: en cada paso tomaremos una moneda de la denominación más alta (la mejor opción dentro del paso), que no supere la cantidad restante.
a) Sean las denominaciones de las monedas 1, 5 y 10, y S = 27.
1) Toma 10, S: 27 -> 17
2) Tomar 10, S: 17 -> 7
3) Toma 5, S: 7 -> 2
4) Toma 1, S: 2 -> 1
5) Toma 1, S: 1 -> 0
Como resultado, anotaron la cantidad de cinco monedas. Puedes asegurarte de forma independiente (por ejemplo, fuerza bruta) de que por 4 monedas o menos no podrás anotar 27.
b) Sean las denominaciones de las monedas 1, 5 y 7, y S = 24.
1) Toma 7, S: 24 -> 17
2) Toma 7, S: 17 -> 10
3) Toma 7, S: 10 -> 3
4) Toma 1, S: 3 -> 2
5) Toma 1, S: 2 -> 1
6) Toma 1, S: 1 -> 0.
Anotamos con seis monedas, pero pudimos obtener S con cuatro monedas: dos con un valor nominal de 7 y dos con un valor nominal de 5.
Como se puede ver en el ejemplo, no siempre es posible resolver problemas con un algoritmo codicioso. Pero si conduce a una respuesta óptima general, entonces será más fácil que usar programación dinámica u otros métodos.