Problème — Rendu de monnaie optimal avec reconstruction

La récursivité · niveau 3 (difficile)

Énoncé

Problème — Rendu de monnaie optimal avec reconstruction.

On souhaite non seulement connaître le nombre minimal de pièces pour rendre une somme, mais aussi la liste des pièces utilisées. Écrire une fonction récursive rendu_liste(somme, pieces) renvoyant une liste de pièces de longueur minimale, ou None si le rendu est impossible.

Corrigé

On essaie chaque pièce inférieure ou égale à la somme, on résout récursivement pour la somme restante, et on conserve la solution la plus courte. Le cas de base est somme == 0, qui renvoie une liste vide.


def rendu_liste(somme, pieces):
    if somme == 0:
        return []
    meilleur = None
    for p in pieces:
        if p <= somme:
            reste = rendu_liste(somme - p, pieces)
            if reste is not None:
                candidat = reste + [p]
                if meilleur is None or len(candidat) < len(meilleur):
                    meilleur = candidat
    return meilleur

print(rendu_liste(11, [1, 2, 5]))   # affiche [1, 5, 5]
print(rendu_liste(7, [2, 4]))       # affiche None (impossible)

Cette version explore toutes les combinaisons : elle est correcte mais coûteuse. En pratique, on l'améliore par mémoïsation pour éviter de recalculer plusieurs fois le rendu d'une même somme.