agosto 20, 2012

Las Monedas del Avaro


El siguiente pseudocódigo demuestra un algoritmo del tipo “greedy” (voraz o avaro) para resolver el típico problema de dar el cambio correcto según las opciones disponibles en diferentes denominaciones, siendo el objetivo dar la menor cantidad posible de monedas o billetes.

Por ejemplo, dar $123 pesos de cambio se puede hacer de varias formas, la más óptima es con dos de $50, uno de $20, uno de $2 y uno de $1 (cinco monedas). Otra opción posible es seis de $20 y tres de $1 (nueve monedas). Obviamente la peor opción seria dar ciento veintitrés monedas de $1 peso.


Aunque hay diversos algoritmos para resolver este problema, el método “greedy” funciona óptimamente para la mayoría de los sistemas denominativos del mundo, incluyendo a México, ya que estos utilizan la serie “1-2-5” de números preferidos. La lógica de este algoritmo voraz consiste en ir escogiendo la denominación mayor que no sea más grande que el restante a completar.

Los algoritmos voraces se caracterizan por ser:
  • Sencillos: de diseñar y codificar.
  • Miopes: toman decisiones con la información que tienen disponible de forma inmediata, sin tener en cuenta sus efectos futuros.
  • Eficientes: dan una solución óptima pero no necesariamente la mejor.

01.- A Meta ponle 123
02.- A Actual ponle 1
03.- A Acum ponle 0
04.- A Monedas ponle el conjunto {50,20,10,5,2,1}
05.- A Cambio ponle el conjunto {}
06.- HAZ
07.-    SI Acum más el valor del elemento Actual de Monedas es mayor que Meta ENTONCES
08.-       A Actual súmale 1
09.-       SINO ENTONCES
10.-       A Acum súmale el valor del elemento Actual de Monedas
11.-       A Cambio agrégale el elemento actual de Monedas
12.-       FIN SI
13.-    HASTA que Acum sea igual a Meta
14.- IMPRIME todos los elementos de Cambio

No hay comentarios:

Publicar un comentario en la entrada