Dans le sac à dos, comparer trois stratégies gloutonnes

def sac_glouton(objets, capacite, cle):
    tries = sorted(objets, key=cle, reverse=True)
    choisis, restant, valeur = [], capacite, 0
    for nom, poids, v in tries:
        if poids <= restant:
            choisis.append(nom); restant -= poids; valeur += v
    assert restant >= 0
    return choisis, valeur

def sac_exhaustif(objets, capacite):
    """Oracle : toutes les combinaisons, pour de PETITES instances."""
    meilleure = 0
    for r in range(len(objets) + 1):
        for combi in itertools.combinations(objets, r):
            if sum(o[1] for o in combi) <= capacite:
                meilleure = max(meilleure, sum(o[2] for o in combi))
    return meilleure

massique = lambda o: o[2] / o[1]
valeur_seule = lambda o: o[2]
poids_leger = lambda o: -o[1]

Sur l'exemple du cours (capacité $10$ ; $A$ : $6$/$30$, $B$ et $C$ : $5$/$20$) :

OBJETS = [("A", 6, 30), ("B", 5, 20), ("C", 5, 20)]
assert sac_glouton(OBJETS, 10, massique)[1] == 30
assert sac_glouton(OBJETS, 10, valeur_seule)[1] == 30
assert sac_glouton(OBJETS, 10, poids_leger)[1] == 40    # ici, la meilleure !
assert sac_exhaustif(OBJETS, 10) == 40

Le « plus léger d'abord », qui semblait naïf, trouve l'optimum là où la valeur massique échoue. Mais il suffit de retourner l'exemple pour l'humilier :

AUTRES = [("A", 1, 1), ("B", 5, 50), ("C", 5, 50)]
assert sac_glouton(AUTRES, 10, poids_leger)[1] == 51    # il prend le grain de sable
assert sac_glouton(AUTRES, 10, massique)[1] == 100

La mesure sur $400$ instances tirées au hasard (six objets, capacités de $5$ à $20$) :

Non, les deux questions n'ont pas la même réponse — et c'est tout l'intérêt de l'exercice. La valeur massique échoue plus souvent que la valeur seule ($87$ contre $66$), et pourtant elle rapporte davantage en moyenne. Trier par valeur seule tombe juste plus fréquemment, mais quand il se trompe, il se trompe plus lourdement.

Ce qu'il faut en retenir sur la mesure elle-même. Compter les échecs et mesurer la perte sont deux critères différents, qui peuvent classer les méthodes en sens contraire. Choisir un critère avant de mesurer n'est pas un détail méthodologique : c'est ce qui décide de la conclusion. Aucune des trois stratégies n'est d'ailleurs toujours optimale — c'est bien le propre d'un glouton.