Para este problema se dispone de un conjunto finito de tipos de monedas, \(T={m^0,m^1,m^2,...,m^{n-1}}\) y se dispone de una cantidad ilimitada de monedas de cada tipo.El problema consiste en calcular el número mínimo de monedas que necesitamos para entregar una cantidad \(C>0\) .
La ecuación que representa el problema es la siguiente, siendo \(N\) el número de tipos diferentes de monedas y \(C\) la cantidad que tenemos que entregar:
\[ Cambio(N,C) = \begin{cases} Cambio(N-1,C) & \text{si } x_N > C \\ min\{Cambio(N-1,C), Cambio(N,C-x_N)+1\} & \text{si } x_N <= C \end{cases} \]
El caso trivial ocurre cuando se completa la cantidad \(C\) o cuando ya no quedan más tipos de monedas \(N\) a considerar:
\[Cambio(k,0) = 0 \text{ si } 0 ≤ k ≤ n\]
\[Cambio(0,C′) = \text{ si } 0 < C′ ≤ C \]
Los resultados parciales se almacenan en una tabla que contiene una fila por cada tipo posible de moneda y una columna para cada cantidad posible entre 0 y \(C\). La solución al problema estaría contenido en la última casilla, es decir, \(t[N,C]\). La tabla se construye partiendo de los casos base, es decir, \(t[1.0] = 0\)
En la zona de visualización podrás ver cómo funciona y cómo se construye la tabla. Introduce los valores de las monedas separados por comas y la cantidad a pagar y pulsa ACTUALIZAR. Podrás ver la evolución del algoritmo y de las estructuras de datos utilizadas utilizando los botones de control superiores