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

Les algorithmes gloutons · niveau 1 (application)

Énoncé

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

Une entreprise charge un camion de capacité $C$ kilogrammes avec des marchandises divisibles (sable, gravier, etc.). Chaque marchandise a une quantité disponible (en kg) et un prix au kilo. On veut maximiser la valeur transportée et indiquer la composition du chargement.

Corrigé

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 lo g n)$ .