Problema de cambio de monedas
Los valores de las monedas se pueden representar mediante un conjunto de n valores enteros positivos distintos, ordenados en forma creciente desde w1 = 1 hasta wn.
El planteo del problema es: dada una cantidad W, que es un entero positivo, encontrar un conjunto de números enteros no negativos (positivos o cero) {x1, x2, ..., xn}, donde cada incógnita xj representa cuantas monedas de valor wj se utilizan, de forma tal de minimizar el número total de monedas que se utilizan para sumar W sujeto a Una situación similar al problema de cambio, es por ejemplo encontrar las formas en que se puede hacer el lanzamiento de cierto número de dardos en un juego de dardos y obtener un puntaje W. Para este caso se tienen n valores distintos marcados en el tablero de forma tal que al lanzar cada dardo y atinar a un valor, estos valores se van sumando hasta llegar al puntaje objetivo W. El objetivo sería llegar a obtener el puntaje objetivo W con la mínima cantidad posible de lanzamientos.
Por lo tanto, en cada umbral, se considera potencialmente que todos los umbrales previos funcionan de forma ascendente para alcanzar la cantidad objetivo W. Por esta razón, este enfoque de programación dinámica puede requerir una cantidad de pasos que se incrementa en forma al menos cuadrática según sea el valor de la cantidad objetivo W. Como el problema presenta una subestructura óptima, se puede aplicar una estrategia de programación dinámica para encontrar una solución.
fuese la solución óptima para el sub-problema que contiene exactamente
monedas y no es óptimo, por lo que la solución se conoce como
se obtiene la solución óptima que contiene exactamente
no era la solución óptima para el problema original.
El siguiente algoritmo es una implementación de programación dinámica (con Python 3) que utiliza una matriz para realizar un seguimiento de las soluciones óptimas para sub-problemas y devuelve el número mínimo de monedas.
Este proceso se repite hasta que las dos colecciones finales de resultados se combinan en una, lo que lleva a un árbol binario equilibrado con W log(W) operaciones de fusión.
En los denominados sistemas canónicos de monedas, tales como el que se usa en Estados Unidos, y en muchos otros países, se emplea un algoritmo codicioso o voraz.
Según este algoritmo se elige la moneda de mayor denominación tal que no sea mayor que la cantidad restante para alcanzar el valor objetivo.
El "problema de denominación óptima"[3] es un problema que se adecúa a las personas que diseñan monedas completamente nuevas.
En este problema se pregunta qué denominaciones se deben elegir para las monedas a fin de minimizar el costo promedio de hacer el cambio, es decir, el número promedio de monedas necesarias para hacer el cambio.
