Soy tutor de un estudiante cuyo trabajo clásico sobre la moneda de cambio de problema. Para aquellos que no están familiarizados con el problema o el algoritmo voraz utilizados para ello. El objetivo es encontrar el menor número de monedas necesarias para dar a $x$ cambio de uso de trimestres ($25¢$), monedas de diez centavos ($10¢$), monedas de cinco centavos ($5¢$), y un centavo ($1¢$). El algoritmo voraz básicamente dice que recoger la moneda más grande disponible. Sé que la codicia enfoque es óptimo ya que el tiempo que tienen todas las monedas disponibles, por ejemplo: Encontrar el cambio de $16¢$. Solución óptima: $1$ moneda de diez centavos, $1$ de níquel y $1$ penny $(10 + 5 + 1)$. Tres el total de monedas.
Sin embargo, si usted no tiene monedas de cinco centavos disponibles para elegir. El algoritmo voraz no se cumple para todos los casos. Por ejemplo: encontrar el cambio de $40¢$. El algoritmo voraz dice a recoger $1$ trimestre $1$ moneda de diez centavos, y $5$ centavos $(25 + 10 + 1 + 1 + 1 + 1 + 1)$. Siete monedas total. Una mejor solución es coger $4$ monedas de diez centavos en lugar de $(10 + 10 + 10 + 10)$. Cuatro monedas total.
Él supone que debe demostrar que lo que es el mayor número de monedas de un centavo en la solución óptima puede tener y cuál es el mayor número de monedas de diez centavos que una solución óptima puede tener? Ambos estamos de acuerdo en que sin nickels disponible debe utilizar monedas de un centavo mientras $x < 9$ (asumiendo $x$ es el cambio de la izquierda). Si $x \geq 10$, entonces es mejor elegir una moneda de diez centavos en su lugar. Y en el caso de las monedas de diez centavos, la mayoría de las monedas que usted puede tener es $4$ mientras $x < 50$. Al $x \geq 50$ más que la solución óptima es utilizar al menos dos trimestres.
El problema que estoy teniendo es que viene con una sólida prueba de ello. Me puede explicar en palabras, pero soy incapaz de encontrar un razonamiento matemático. Estoy pensando en la prueba por contradicción, pero no sé cómo escribir uno para este escenario. Cualquier ayuda se agradece.
