Écrire une résolution exhaustive du rendu de monnaie par programmation…

def rendu_exhaustif(somme, pieces):
    """Nombre minimal de pieces, en construisant les resultats de 1 a somme."""
    infini = float("inf")
    meilleur = [0] + [infini] * somme
    for s in range(1, somme + 1):
        for p in pieces:
            if p <= s and meilleur[s - p] + 1 < meilleur[s]:
                meilleur[s] = meilleur[s - p] + 1
    return meilleur[somme]

L'idée, en une phrase. Pour rendre $s$, on essaie chaque pièce $p$ comme dernière pièce posée : il reste alors à rendre $s-p$, dont on connaît déjà le meilleur résultat puisqu'on avance dans l'ordre croissant. On ne revient jamais en arrière et rien n'est recalculé — c'est le contraire du glouton, qui décide sans regarder les conséquences.

Le prix. Le tableau meilleur a $\text{somme}+1$ cases et chacune coûte un parcours des pièces : le travail croît avec la somme, pas avec le nombre de pièces. Sur de très grandes sommes, la méthode devient impraticable là où le glouton ne coûte rien. C'est l'arbitrage que le cours annonce, et que la terminale reprendra.

Vérification, et l'usage qu'on en fait.

assert rendu_exhaustif(8, [6, 4, 1]) == 2
assert rendu_exhaustif(67, EURO) == 4

for s in range(0, 60):
    assert rendu_exhaustif(s, EURO) == len(rendu_monnaie(s, EURO))

La boucle finale est le vrai résultat : sur soixante sommes consécutives, le glouton et l'optimum coïncident avec le système européen. Une résolution exhaustive ne sert pas seulement à mieux résoudre — elle sert d'oracle pour juger une méthode approchée.