Su suposición de que el algoritmo codicioso para contar el cambio produce la menor cantidad posible de monedas no siempre es cierta. Por ejemplo, dadas las denominaciones [matemáticas] 1 [/ matemáticas], [matemáticas] 3 [/ matemáticas] y [matemáticas] 4 [/ matemáticas], podemos hacer [matemáticas] 6 [/ matemáticas] con [matemáticas] 2 [ / math] usando [math] \ {3,3 \} [/ math] pero el algoritmo codicioso produciría [math] 3 [/ math] monedas usando [math] \ {4,1,1 \} [ /matemáticas]. Sin embargo, si está hablando de las denominaciones de la moneda estadounidense, entonces su suposición es válida, como se indica en el método codicioso para el problema de hacer cambios. Esto se debe a que el sistema de monedas de los Estados Unidos es canónico.
En general, cualquier sistema de denominación puede clasificarse como canónico (algoritmo codicioso para que cualquier cambio produzca la menor cantidad de monedas) o no canónico. Si estamos trabajando con [math] n [/ math] monedas en nuestro sistema, hay al menos un algoritmo [math] \ mathcal {O} (n ^ 3) [/ math] para determinar si ese sistema es canónico o no , como se describe en http://graal.ens-lyon.fr/~abenoi…. Si desea saber por qué el algoritmo codicioso funciona para sistemas canónicos, puede leer http://arxiv.org/pdf/0809.0400.pdf o sus referencias.