Cómo proceder para demostrar una condición para el algoritmo voraz de cambio de monedas.
Recientemente he estado practicando unas cuantas preguntas de algoritmos para encontrar el cambio y me encontré con dos condiciones en las que se nos pedía determinar si los algoritmos producirían una solución óptima para monedas de cada uno de los siguientes tipos de denominación para cada condición. A continuación, se presentan las dos condiciones separadas:
¿Cómo resolveríamos estas dos preguntas?
davy.ai
Para resolver estas dos preguntas, necesitamos utilizar un enfoque algoritmo voraz. El algoritmo voraz funciona eligiendo la moneda de mayor denominación tantas veces como sea posible, hasta alcanzar la suma deseada o no poder agregar más monedas sin exceder la suma.
Para la primera condición, donde tenemos monedas de denominaciones 1, 5, 10 y 25, podemos comenzar con la moneda de mayor denominación (25) y restarla de la suma objetivo tantas veces como sea posible, hasta que no podamos restarla más sin llegar a 0. Luego, pasamos a la siguiente moneda de mayor denominación (10) y repetimos el proceso. Continuamos este proceso para las monedas restantes hasta alcanzar la suma deseada o no poder agregar más monedas sin exceder la suma.
Para la segunda condición, donde tenemos monedas de denominaciones 1, 4, 6 y 12, podemos comenzar con la moneda de mayor denominación (12) y restarla de la suma objetivo tantas veces como sea posible, hasta que no podamos restarla más sin llegar a 0. Luego, pasamos a la siguiente moneda de mayor denominación (6) y repetimos el proceso. Sin embargo, hay una ligera complicación con esta condición ya que tenemos dos denominaciones pares (4 y 6), lo que significa que podríamos necesitar usar una combinación de estas dos monedas para alcanzar la suma objetivo. Por lo tanto, necesitamos verificar cada combinación de monedas de 4 y 6 que puedan sumar la suma restante después de restar 12 y elegir la combinación que nos dé la menor cantidad de monedas. Finalmente, utilizamos la moneda de 1 para completar cualquier cantidad restante después de usar las monedas de mayor denominación.
En ambas condiciones, el algoritmo voraz producirá una solución óptima ya que la moneda de mayor denominación siempre se elige tantas veces como sea posible, maximizando el valor de cada moneda utilizada.