Capítulo 18. Algoritmos Greedy: Ejemplo del cambio

En este y capítulos posteriores iremos analizando distintos ejemplos de aplicación de la técnica de algoritmos Greedy. Comenzaremos con estudiar el más sencillo de todos: el problema del cambio.

Se desea encontrar la forma de devolver un vuelto de valor 'v' con monedas de denominaciones d₁, d₂, ..., d_n considerando que existe una cantidad infinita de monedas de cada denominación.

Por ejemplo, queremos devolver $1.83 y disponemos de monedas de 1, 5, 10, 25, 50 centavos y 1 peso. La forma más sencilla e intuitiva de hacerlo es con una moneda de 1 peso, una moneda de 50 centavos, una moneda de 25 centavos, una moneda de 5 centavos y tres monedas de 1 centavo.

Esto que hacemos en forma intuitiva (devolver la cantidad pedida con la menor cantidad posible de monedas) puede expresarse en el siguiente algoritmo:

Cómo se estudió en el capítulo 16, debería ser posible identificar las 4 funciones que caracterizan a los algoritmos Greedy.

Así, el conjunto de candidatos es el conjunto de monedas disponibles y se dispone de infinitas monedas de cada denominación. El conjunto de candidatos pendientes viene dado por las posiciones mayores o iguales a i en la cadena 'monedas'.

La función selección es la que elige el elemento de la posición i sumado a que las monedas están ordenadas de mayor a menor (se indicó como 100 la moneda de 1 peso para diferenciarla de la moneda de 1 centavo).

La función de factibilidad es la que pregunta si s + monedas[i] < v (es decir, está preguntando si al sumarle el candidato elegido en ese momento al vuelto parcial 's', no nos estamos pasando del valor v a devolver).

La función solución es la que evalúa s < v y la función objetivo, implícita, es la que minimiza la cantidad de monedas.

Debemos tener en cuenta que este algoritmo es correcto para las denominaciones de monedas utilizadas. Para otras instancias del problema el algoritmo deja de ser óptimo y es necesario emplear otra técnica distinta que estudiaremos más avanzado el curso.

Para ilustrar este hecho supongamos que nuestra cadena de monedas es = [6, 4, 1] y se nos pide devolver un cambio de 8.

El algoritmo presentado en este capítulo nos daría el vuelto con una moneda de 6 y dos monedas de 1 (totalizando 3 monedas) cuando intuitivamente podemos apreciar que la manera más óptima sería devolver dos monedas de 4.

Fuentes:

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.

Capítulo 17. Algoritmos Greedy (Parte II)

Presentaremos en este capítulo la forma general en formato pseudocódigo de los algoritmos Greedy.

GREEDY
Entrada: C -> conjunto de candidatos.
Salida:  S -> solución del problema.

     mientras C <> vacío y no esSolucion(S)
          x <- Seleccionar(C)
          C <- C\{x}          
          si esFactible(S U {x})
              S <- S U {x} 
          fin si
     fin mientras
     si esSolucion(S) 
         devolver S
     fin si
     sino 
         devolver No hay solución
     fin si
fin GREEDY

Al tratarse de operaciones entre conjuntos vale aclarar la notación:

• C\{x} quiere decir que al conjunto de candidatos C se le quita el elemento x (ya que 'x' había sido seleccionado en el paso anterior).
• S U {x} significa que al conjunto de solución se le agrega el elemento x.

En los siguientes capítulos nos dedicaremos a estudiar ejemplos de aplicación de esta técnica de diseño de algoritmos.