Dado un conjunto de monedas con diferentes denominaciones un valor v desea encontrar la menor cantidad de monedas necesarias para representar el valor v.
Por ejemplo, para el conjunto de monedas 1,5,10,20, esto da 2 monedas por la suma 6 y 6 monedas por la suma 19.
Mi pregunta principal es: ¿cuándo se puede utilizar una estrategia codiciosa para resolver este problema?
Puntos de bonificación: ¿Esta afirmación es simplemente incorrecta? (De: ¿Cómo saber si el codicioso algoritmo es suficiente para el problema de cambio mínimo de monedas? )
Sin embargo, este documento tiene una prueba de que si el algoritmo codicioso funciona para el primer valor más grande y el segundo valor más grande, entonces funciona para todos ellos, y sugiere simplemente usar el algoritmo codicioso frente al algoritmo DP óptimo para verificarlo. http://www.cs.cornell.edu/~kozen/papers/change.pdf
PD. tenga en cuenta que las respuestas en ese hilo son increíblemente malas, es por eso que hice la pregunta nuevamente.
fuente
Respuestas:
Un sistema de monedas es canónico si la cantidad de monedas otorgadas en cambio por el algoritmo codicioso es óptima para todas las cantidades.
El papel es bastante corto.
También hay una discusión en esta pregunta matemática .
fuente
canonical coin system
. Sería genial si pudieras agregar un ejemplo, es decir, cómo probar el sistema sugerido1,5,10,20