Problème — Chargement d'un camion (sac à dos fractionnaire)

La densité de valeur est ici directement le prix au kilo : on charge en priorité les marchandises les plus chères au kilo.

def charger_camion(marchandises, capacite):
    """marchandises : liste de (nom, quantite_kg, prix_par_kg)."""
    marchandises = sorted(marchandises, key=lambda m: m[2], reverse=True)
    reste = capacite
    valeur = 0.0
    chargement = []
    for nom, quantite, prix in marchandises:
        if reste <= 0:
            break
        pris = min(quantite, reste)
        chargement.append((nom, pris))
        valeur += pris * prix
        reste -= pris
    return valeur, chargement

stock = [("or_en_poudre", 5, 1000), ("argent", 20, 50),
         ("sable", 100, 2)]
valeur, chargement = charger_camion(stock, 30)
print(valeur)        # 5*1000 + 20*50 + 5*2 = 6010.0
print(chargement)    # [('or_en_poudre', 5), ('argent', 20), ('sable', 5)]

Le glouton remplit d'abord avec l'or (le plus cher au kilo), puis l'argent, et complète avec $5$ kg de sable. Comme les marchandises sont divisibles, cette stratégie est optimale, en $O(n\log n)$.