CHAPITRE 3 : QUAND LE GLOUTON SE TROMPE

Tonton Émile fait la ligne Yaoundé–Douala. Dans la soute de son car, il lui reste 15 kilos à vendre pour le compte de commerçants. Plusieurs marchandises lui sont proposées. Il doit choisir, et il va se tromper.

Ce qu'on lui propose

Les sacs ne se coupent pas : on prend la marchandise entière, ou on la laisse. C'est ce qu'on appelle le sac à dos 0-1 : zéro ou un exemplaire, jamais une moitié.

Le raisonnement de Tonton Émile

Il est transporteur depuis vingt ans, et sa règle est simple : je charge d'abord ce qui rapporte le plus au kilo. C'est un critère glouton, et il est tout à fait raisonnable.

1. Le poivre de Penja rapporte 11 111 FCFA/kg. Il le prend. 9 kg chargés, 6 restants.
2. Le cacao vient ensuite, mais il pèse 12 kg. Impossible.
3. Le safou ? 2 kg, ça rentre. Il le prend. 11 kg chargés, 4 restants.
4. Le ndolé pèse 7 kg, le miel 5 kg. Ni l'un ni l'autre ne rentre dans les 4 kg qui restent.

Chargement final : 11 kg pour 110 000 FCFA

Ce qu'il aurait fallu faire

En testant les 32 combinaisons possibles, on trouve mieux :

Poivre (9 kg) + Miel d'Oku (5 kg) = 14 kg pour 120 000 FCFA

Tonton Émile a perdu 10 000 FCFA, soit 8,3 % de ce qu'il pouvait gagner. Sur une ligne qu'il fait deux fois par semaine, cela fait plus d'un million de francs sur l'année.

Où est l'erreur ?

Elle n'est pas dans le critère. Le safou rapporte bien plus au kilo que le miel : 5 000 contre 4 000. Le glouton a correctement appliqué sa règle.

L'erreur est ailleurs : en prenant le safou, qui ne pèse que 2 kg, Tonton Émile s'est retrouvé avec 4 kg inutilisables. Trop peu pour le miel, trop peu pour le ndolé. Ces 4 kg sont partis à vide.

Le miel rapporte moins au kilo, mais il remplit mieux le car. Le glouton ne sait pas voir cela : il regarde les marchandises une par une, pas la place qu'elles laissent derrière elles.

Le code, quand même

Même imparfait, l'algorithme reste utile. Le voici :

def charger(marchandises, capacite):
    # marchandises : liste de (nom, poids, valeur). Renvoie (valeur, chargement)
    # on trie du plus rentable au kilo au moins rentable
    par_densite = sorted(marchandises,
                         key=lambda m: m[2] / m[1],
                         reverse=True)

    poids, valeur, pris = 0, 0, []

    for nom, p, v in par_densite:
        if poids + p <= capacite:        # ca rentre encore
            pris.append(nom)
            poids += p
            valeur += v

    return valeur, pris, poids

>>> charger(MARCHANDISES, 15)
(110000, ['Poivre de Penja', 'Safou'], 11)

Et la force brute ?

from itertools import combinations


def charger_exact(marchandises, capacite):
    # Teste toutes les combinaisons. Exact, mais exponentiel
    meilleur = (0, ())

    for taille in range(len(marchandises) + 1):
        for essai in combinations(marchandises, taille):
            poids = sum(m[1] for m in essai)
            if poids <= capacite:
                valeur = sum(m[2] for m in essai)
                if valeur > meilleur[0]:
                    meilleur = (valeur, essai)

    return meilleur

Sur cinq marchandises, c'est instantané : 32 combinaisons. Sur cinquante, c'est un million de milliards : inenvisageable.

Alors, faut-il jeter le glouton ?

Non. Il faut savoir ce qu'on achète.

Perdre 8 % sur un calcul instantané est souvent un bon marché. Et on peut démontrer que ce glouton-là ne descend jamais en dessous de la moitié de l'optimum : il est mauvais, mais pas catastrophique.

Au chapitre suivant, nous changerons une seule règle du problème, et le même glouton deviendra parfaitement optimal.

vanille 1 kg   -> 1 kg,  15 000    reste 14 kg
poivre  9 kg   -> 10 kg, 115 000    reste  5 kg
cacao  12 kg   -> ne rentre pas
safou   2 kg   -> 12 kg, 125 000    reste  3 kg
ndole   7 kg   -> ne rentre pas
miel    5 kg   -> ne rentre pas

total : 12 kg, 125 000 FCFA