El problema de creación de cambios aborda la cuestión de encontrar el número mínimo de monedas (de ciertas denominaciones) que suman una cantidad determinada de dinero. Es un caso especial del problema de la mochila entera, y tiene aplicaciones más amplias que solo la moneda.
También es la variación más común del problema de cambio de moneda, un caso general de partición en el que, dadas las denominaciones disponibles de un conjunto infinito de monedas, el objetivo es averiguar el número de formas posibles de hacer un cambio para una cantidad específica de dinero, sin considerar el orden de las monedas.
hacer cambios es un problema de minimización, elegimos la solución donde tenemos que dar un número mínimo de monedas por una cantidad dada.
- Método codicioso
2. Método dinámico
programación dinámica
Una estrategia de programación dinámica clásica funciona hacia arriba encontrando las combinaciones de todos los valores más pequeños que sumarían al umbral actual.Por lo tanto, en cada umbral, todos los umbrales anteriores se consideran potencialmente para trabajar hacia arriba a la cantidad de meta W. Por esta razón, este enfoque de programación dinámica puede requerir un número de pasos que sea al menos cuadrático en la cantidad de meta W.
cambio de moneda óptimo Hemos visto esto, desea realizar cambios utilizando un sistema de denominaciones, utilizando el menor número de monedas posible. A veces el algoritmo codicioso da la solución óptima. Pero a veces no — un ejemplo fue el sistema (12, 5, 1), donde el algoritmo dinámico da 15 = 12 + 1 + 1 + 1 pero la mejor respuesta es 15 = 5 + 5 + 5. pero dynamic siempre da una solución óptima o posibles monedas mínimas dentro de esos denominadores.
Pasos: –
Encontraremos el número mínimo. de monedas necesarias para la cantidad .Cantidad es la cantidad por la que estamos haciendo el cambio.
primero estableceremos min. no. de monedas necesario decir,, min = INFINITY
Esto significa que inicialmente no sabemos cuántas monedas se necesitarán.
Luego comprobamos cada moneda de denominación y vemos si se puede usar para obtener la solución.
Si es posible, actualizamos las variables min y coin.
donde, min = número mínimo. de monedas necesarias para hacer cambios por cantidad
moneda = primer índice de la moneda en la solución
Ejemplo:
Cantidad = 5
monedas = {1,2,3}
Formas de hacer cambios = 5
