Problème — Comparaison glouton / dynamique sur le rendu de monnaie

L'algorithme glouton choisit d'abord la plus grosse pièce $\le 6$, soit $4$, puis deux pièces de $1$ : il rend $6=4+1+1$, soit 3 pièces. La programmation dynamique trouve la solution optimale $6=3+3$, soit 2 pièces. Voici les deux approches comparées :

def rendu_glouton(pieces, somme):
    pieces = sorted(pieces, reverse=True)
    nb, reste = 0, somme
    for p in pieces:
        nb += reste // p
        reste = reste % p
    return nb if reste == 0 else -1

def rendu_dynamique(pieces, somme):
    INFINI = float('inf')
    table = [0] + [INFINI] * somme
    for s in range(1, somme + 1):
        for p in pieces:
            if p <= s:
                table[s] = min(table[s], table[s - p] + 1)
    return table[somme] if table[somme] != INFINI else -1

# rendu_glouton([1, 3, 4], 6)   -> 3 (sous-optimal)
# rendu_dynamique([1, 3, 4], 6) -> 2 (optimal)

Cet exemple montre que le glouton ($O(k\log k)$) est plus rapide mais peut être sous-optimal, tandis que la programmation dynamique ($O(S\times k)$) garantit toujours l'optimum.