¿Qué hace que greedy funcione?
Paso 1 de 9
Greedy (voraz) tiene una sola regla: toma la moneda más grande que aún cabe y nunca lo reconsideres.
La idea
Un algoritmo greedy (voraz) toma la jugada que parece mejor en este momento y nunca la reconsidera. Sin árbol de búsqueda, sin deshacer: una sola pasada.
Eso solo es correcto cuando una ganancia local nunca puede costarte una mejor respuesta global. La prueba habitual es un argumento de intercambio: toma cualquier respuesta óptima, pon en ella la elección greedy y demuestra que el resultado sigue siendo óptimo. Si ese intercambio siempre se sostiene, greedy es seguro. Basta un contraejemplo para que no lo sea.
Ejemplo del mundo real
Dar el cambio en una caja. Con monedas de 25, 10, 5 y 1, tomar la moneda más grande que todavía cabe siempre es óptimo. Si acuñas monedas de 1, 3 y 4, el mismo reflejo paga 4 + 1 + 1 por seis, cuando bastaban dos de 3.
El código
Te toca
¿Qué imprime esto?
print(greedy_coins([1, 5, 7], 10))Mini quiz
1 / 3