Problema de canvi de monedes

Eixemple de solució al problema de donar canvi en models, si s'utilisa un algoritme voraç per a determinar el mínim número de monedes que deu tornar-se en el canvi. En la figura es mostren els passos que un ser humà deuria seguir per a emular a un algoritme voraç per a acumular 36 centaus usant només monedes de valors nominals d'1, 5, 10 i 20 centaus cada una. La moneda del major valor menor que el restant degut és l'òptim local en cada pas. Note's que en general el problema de devolució del canvi requerix programació dinàmica o programació llineal per a trobar una solució òptima. No obstant, molts sistemes monetaris, incloent l'euro i el dólar nortamericà, són casos especials a on en l'estratègia de l'algoritme voraç dona en la solució òptima.

El problema de canvi de monedes aborda la forma de trobar el número mínim de monedes (de certes denominacions) tals que entre elles sumen una certa cantitat. És un tipo de problema de la mochila, i té aplicacions que excedixen l'àmbit específic de la circulació de diners.

Definició matemàtica

Els valors de les monedes es poden representar per mig d'un conjunt de n valores sancers positius distints, ordenats en forma creixent des de w₁ = 1 fins a w_n.

El plantege del problema és: donada una cantitat W, que és un sancer positiu, trobar un conjunt de número entero no negatius (positius o zero) {x₁, x₂, ..., x_n}, a on cada incògnita x_j representa quantes monedes de valor w_j s'utilisen, de forma tal de minimisar el número total de monedes que s'utilisen per a sumar W

$\sum _{j=1}^n{x}_j$

subjecte a

$\sum _{j=1}^n{w}_j{x}_j=W.$

Eixemple sense monedes

Una situació similar al problema de canvi, és per eixemple trobar les formes en que es pot fer el llançament de cert número de darts en un joc de darts i obtindre un puntaje W. Per a este cas es tenen n valores distints marcats en el tauler de forma tal que en llançar cada dart i atinar a un valor, estos valors es van sumant fins a aplegar al puntaje objectiu W. L'objectiu seria aplegar a obtindre el puntaje objectiu W en la mínima cantitat possible de llançaments.

Vore també

• Problema de la mochila
• Problema de la moneda

Bibliografia

• X. Cai (2009). “Canonical Coin Systems for Change-Making Problems”. Proceedings of the Ninth International Conference on Hybrid Intelligent Systems: 499–504. doi:10.1109/HIS.2009.103.
• M. Adamaszek, A. Niewiarowska (2010). “Combinatorics of the change-making problem”. European Journal of Combinatorics 31 (1): 47–63. doi:10.1016/j.ejc.2009.05.002.