27. Algoritmo voraz

Implementa un algoritmo voraz para resolver el problema del cambio de monedas.

Crea una función que, dado un importe de dinero y una lista de denominaciones de monedas disponibles, devuelva la menor cantidad de monedas necesarias para dar ese cambio. Asume que siempre hay suficientes monedas de cada denominación.

def dar_cambio_voraz(importe: int, denominaciones: list[int]) -> dict[int, int]:
    # Las denominaciones deben estar ordenadas de mayor a menor para el algoritmo voraz
    # Tu código aquí
    pass

# Ejemplo: monedas disponibles: 25, 10, 5, 1
dar_cambio_voraz(78, [25, 10, 5, 1])
# {25: 3, 1: 3} (3 monedas de 25 y 3 monedas de 1 = 75 + 3 = 78)

dar_cambio_voraz(30, [10, 5, 1])
# {10: 3}

dar_cambio_voraz(12, [5, 10, 1]) # Ojo: Las denominaciones deben estar ordenadas en el código
# {10: 1, 1: 2} o {5: 2, 1: 2} si se pasan ordenadas (lo cual es crucial para el algoritmo voraz)

Ratoncito

Implementa el algoritmo voraz para dar cambio, asumiendo que las denominaciones de las monedas están en un orden que permite que el algoritmo voraz funcione óptimamente (por ejemplo, sistemas monetarios estándar como el euro o el dólar).

Dragón

Considera un sistema de monedas donde el algoritmo voraz no siempre da la solución óptima (por ejemplo, si las monedas disponibles son [1, 5, 8] y el importe es 10).

• Explica cuándo el algoritmo voraz es óptimo y cuándo no.

• Si el algoritmo voraz no es óptimo, ¿cómo abordarías el problema para encontrar la solución mínima (esto ya sería un problema de programación dinámica)? Para el reto, podrías simplemente señalar que el algoritmo voraz fallaría para ciertos conjuntos de monedas.