¿Qué sistemas de invención de un algoritmo voraz no funciona en la prestación de cambio?

Question

Para el sistema de invención de Estados Unidos, un algoritmo voraz bien permite un algoritmo que proporciona el cambio en la menor cantidad de monedas.

Sin embargo, para un sistema de invención con moneda de 12 céntimos, un algoritmo voraz no funcionaría. Por ejemplo, cambio por 15 centavos sería una moneda de 12 céntimos y 3 monedas (en total 4 monedas) mientras que una moneda de diez centavos y cinco centavos (2 monedas) sería óptimos.

¿En qué tipos de sistemas de invención el algoritmo voraz no funciona?

Answer 1

Intuitivamente, el requisito para el algoritmo codicioso trabajar para una coinset $c_1<c_2<...<c_n$ es que importe válido es menor por 1 la solución de menor $v \in [c_i,c_{i+1}[$ $v-c_i$ la solución de menor $v$.