Problème — Comparer glouton et programmation dynamique sur le sac à dos entier

La version dynamique remplit un tableau dp[i][w] (valeur maximale avec les $i$ premiers objets et une capacité $w$).

def sac_entier_glouton(objets, W):
    objets = sorted(objets, key=lambda o: o[1] / o[0], reverse=True)
    reste, valeur = W, 0
    for poids, val in objets:
        if poids <= reste:
            reste -= poids
            valeur += val
    return valeur

def sac_entier_dynamique(objets, W):
    n = len(objets)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        poids, val = objets[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]              # objet i non pris
            if poids <= w:                        # objet i pris
                dp[i][w] = max(dp[i][w], dp[i - 1][w - poids] + val)
    return dp[n][W]

objets = [(10, 60), (20, 100), (30, 120)]
print(sac_entier_glouton(objets, 50))     # 160 (sous-optimal)
print(sac_entier_dynamique(objets, 50))   # 220 (optimal)

Le glouton donne $160$ alors que l'optimum est $220$ : pour le sac à dos entier, le choix localement optimal (meilleur rapport valeur/poids) ne suffit pas. La programmation dynamique, en $O(n\times W)$, examine toutes les combinaisons utiles et garantit l'optimum, au prix d'une complexité supérieure au $O(n\log n)$ du glouton.