.

Como vimos ayer en clase, el algoritmo voraz para devolver una cantidad de dinero con el menor número posible de monedas es correcto (es decir, calcula el número mínimo de monedas) para los sistemas de monedas “habituales”, como el del Euro o el Dólar, que suelen denominarse sistemas canónicos de monedas.

Sin embargo, en general, el voraz no es un algoritmo correcto, no calcula el valor mínimo (ejemplo de monedas marcianas).

Aquí podéis acceder (sólo desde la red de Unizar, o desde vuestra casa usando https://vpn.unizar.es) a un artículo reciente que estudia el sistema de monedas que se requiere para que el algoritmo voraz sea correcto (ojo, no es fácil de leer porque, como ocurre con la mayoría de trabajos de investigación, requiere cierta experiencia en el tema):

Xuan Cai: “Canonical Coin Systems for CHANGE-MAKING Problems“. Proceedings of the Ninth International Conference on Hybrid Intelligent Systems, pp. 499–504. Shenyang, China, August 12-14, 2009.