Page 80 - Revista ingeniantes 2 No1 Vol 1 Interactiva
P. 80
Revista Ingeniantes Año 2 No. 1 Vol. 1
En general, se pueden resolver problemas con subes- la menor cantidad posible de monedas con el fin de
tructuras óptimas siguiendo estos tres pasos: que sean fácilmente contadas y transportadas. Sin
• Dividir el problema en subproblemas más peque- importar la cantidad a devolver. Exprese una solu-
ción a dicho problema asumiendo en este primer
ños. ejemplo (caso de estudio) que la cantidad de mone-
• Resolver estos problemas de manera óptima usan- das de cada denominación es ilimitada.
Una aplicación práctica a este problema son las
do este proceso de tres pasos recursivamente. máquinas expendedoras, las cuales deben devol-
• Usar estas soluciones óptimas para construir una ver cambio en la mayoría de las transacciones que
se realizan optimizando los recursos que posee ya
solución óptima al problema original. [3] que a diferencia del problema académico clásico,
Los subproblemas se resuelven a su vez dividiéndolos no existen en esta monedas ilimitadas de cada valor.
en subproblemas más pequeños hasta que se alcance Otra forma de utilizar estas implementaciones es
el caso fácil, donde la solución al problema es trivial. la realización de aplicaciones que permitan eva-
Decir que un problema tiene subproblemas super- luar que tan eficientemente un niño de educación
puestos es decir que se usa un mismo subproblema básica comprende el uso de su sistema monetario
para resolver diferentes problemas mayores. En una cuando debe devolver cambio tras una transacción
mala implementación puede acabar desperdiciando comercial, siguiendo la regla de menor cantidad de
tiempo recalculando las soluciones óptimas a proble- monedas, fortaleciendo tanto la realización de ope-
mas que ya han sido resueltos anteriormente. raciones como el análisis del problema para dar su
Esto se puede evitar guardando las soluciones que ya solución, y el reforzamiento positivo que debe dar la
hemos calculado. Entonces, si necesitamos resolver aplicación tanto cuando se acierta como cuando se
el mismo problema más tarde, podemos obtener la comete algún error.
solución de la lista de soluciones calculadas y reutili- A continuación se presenta la descripción de la im-
zarla. plementación voraz y dinámica a este problema.
Este acercamiento al problema se llama memoizacion Solución voraz
(no confundir con memorización; en inglés es llamado Es fácil implementar un algoritmo voraz para resol-
memoization,). Si estamos seguros de que no volvere- ver este problema, que es el que sigue el proceso
mos a necesitar una solución en concreto, la podemos que usualmente utilizamos en nuestra vida diaria. Sin
descartar para ahorrar espacio. En algunos casos, se embargo, tal algoritmo va a depender del sistema
pueden calcular las soluciones a problemas que de monetario utilizado y por ello vamos a plantearnos
antemano sabemos que vamos a necesitar. dos situaciones para las cuales deseamos conocer
MATERIAL Y MÉTODOS si el algoritmo ávido encuentra siempre la solución
El Problema de la devolución del cambio. óptima:
Aunque este problema puede parecernos a nosotros Suponiendo que cada moneda del sistema moneta-
trivial, el explicarle a un equipo de cómputo la forma rio del país vale al menos el doble que la moneda
en que debe devolver el cambio de una transacción de valor inferior, que existe una moneda de valor uni-
(por ejemplo para una máquina expendedora) y que tario, y que disponemos de un número ilimitado de
sea además con el menor número de monedas po- monedas de cada valor.
sible, con el fin de optimizar sus recursos, que por lo Suponiendo que el sistema monetario está com-
general son limitados, es importante, no solo para este puesto por monedas de valores 1, p, p2, p3,..., pn,
problema en particular, sino también para aquellos donde p > 1 y n > 0, y que también disponemos de un
que se basen en los mismo principios. Este problema ´ número ilimitado de monedas de cada valor.
se ocupa a menudo en los ámbitos académicos para La mejor solución siguiendo la metodología de aná-
mostrar como la elección de la técnica algorítmica a lisis y planteamiento del problema de forma voraz
utilizar tiene influencia sobre el resultado final de una es definiendo los siguientes puntos:
aplicación informática.
El enunciado general de este problema es el si-
guiente:
En un país X se tienen monedas con las siguientes • Conjunto de candidatos.- Conjunto de monedas
denominaciones M1, M2,…, Mn dichas monedas pue- • Función de solución.- el valor total del conjunto
den representar cualquier cantidad real. Cuando se de monedas elegidas es exactamente igual a la
realiza una transacción monetaria con una cantidad cantidad a pagar.
superior a lo pactado y se tiene que devolver el so- • Función objetivo.- minimizar el número de mone-
brante (cambio), se espera que dicho vuelto tenga das utilizadas en la solución.
74
