Page 78 - Revista ingeniantes 2 No1 Vol 1 Interactiva

Revista Ingeniantes Año 2 No. 1 Vol. 1

Comparación de algoritmos di-
námicos y voraces en la solución
del problema de la devolución de
cambio

Resumen: El problema de devolver
el cambio óptimo (con el menor
número de monedas) consiste en:
Dado un sistema monetario de un
país formado por monedas de va-
cloarmesbivo1, cvo2n,.s..i,stven,eenl problema del
descomponer Colaboración
cualquier cantidad dada “M” en Isaac Alberto Aldave Rojas, Instituto Tecnológico Superior
monedas de ese país utilizando el de Ciudad Serdán
menor número posible de mone-
das, de tal manera que se optimice
el proceso.

Normalmente este proceso es sim-
ple y se puede resolver con un al-
goritmo voraz, pero no todos los
sistemas monetarios son iguales
o algunas veces no se cuenta con
monedas de cierta denominación,
lo cual dificulta aún más el proceso.

Un ejemplo claro es cuando se tie- Abstract: The problem of returning the optimal change (with the
nen monedas de 1, 4 y 6 unidades y least number of coins) consists of: Given a monetary system of
se requiere devolver 8 unidades; el a country consists of currency vaamluoeusnvt 1“,Mv2”, ..., vn, the problem
algoritmo voraz propondría devol- of change is to break any given in the currencies of
ver una moneda de 6 y dos de 1, lo the country using the fewest number of coins, so that the pro-
cual implicaría darle tres monedas, cess is optimized.
pero fácilmente podemos darnos Normally this process is simple and can be solved with a greedy
cuenta de que dos monedas de 4 algorithm, but not all monetary systems are equal or sometimes
unidades es una mejor solución. do not have coins of a certain denomination, which makes the
process even more.
En este trabajo se presentan dos
soluciones una utilizando un enfo- A clear example is when you have coins of 1, 4 and 6 units and
que de algoritmos voraces y la otra 8 units are required to return; the greedy algorithm would pro-
con un enfoque de algoritmo diná- pose returning a one coin of 6 and two coins of 1, implying give
mico y compararemos sus resulta- three coins, but we can easily realize that two coins of 4 units is
dos al devolver cantidades desde 1 a better solution.
hasta 100, con monedas ficticias de In this work two solutions have a voracious approach using al-
60, 40, 10, 6, 4, 1 unidades. gorithms and the other with a focus on dynamic algorithm and
compare its results to return amounts from 1-100, with fake
Palabras clave: Algoritmos dinámi- coins 60, 40, 10, 6, 4, 1 units.
cos, Algoritmos voraces, Análisis
de algoritmos, Comparación, Pro- Keywords: Dynamic algorithms, Greedy algorithms, Algorithm
blema del cambio analysis, Comparison, Problem of change.

72