CHAPITRE 4 : COUPER LES SACS : LE GLOUTON REDEVIENT OPTIMAL

Même car, mêmes marchandises, même capacité de 15 kilos. On change une seule règle : Tonton Émile peut maintenant prendre une partie d'un sac. Et le glouton, qui perdait 10 000 FCFA, devient soudain parfait.

La nouvelle règle

Les marchandises sont désormais fractionnables. Le cacao arrive en vrac : on peut en charger 6 kg sur les 12 disponibles, et payer la moitié du prix. C'est le cas pour tout ce qui se pèse : grains, poudres, liquides.

Ce n'était pas vrai au chapitre précédent, où les marchandises étaient emballées en sacs scellés.

Le même algorithme

Le critère ne change pas : on commence par ce qui rapporte le plus au kilo. Mais la fin du parcours change : quand la prochaine marchandise ne rentre pas en entier, au lieu de la sauter, on en prend ce qu'on peut.

Poivre de Penja, 11 111 FCFA/kg. On prend les 9 kg. Reste 6 kg.
Cacao, 5 833 FCFA/kg. Il pèse 12 kg, on n'a que 6 kg de place. On en prend 6 kg.
Le car est plein. On s'arrête.

poivre : 9 kg entiers        ->  100 000 FCFA
cacao  : 6 kg sur 12         ->   70 000 x 6/12 = 35 000 FCFA
                                 -----------------------------
         15 kg               ->  135 000 FCFA

135 000 FCFA, contre 120 000 pour le meilleur chargement en sacs entiers. Et cette fois, c'est l'optimum absolu.

Pourquoi c'est mieux qu'avant

Deux choses ont changé, et il faut bien les distinguer.

Un : le résultat est plus élevé. C'est normal : on a donné plus de liberté. Pouvoir couper les sacs ne peut qu'aider : toute solution en sacs entiers reste permise.

Deux : le glouton est devenu exact. C'est cela, le vrai changement. Ce n'est plus « il a eu de la chance ». On peut le démontrer.

La démonstration

Affirmation. Pour le sac à dos fractionnaire, charger par densité décroissante donne toujours la valeur maximale.

Démonstration. Supposons qu'il existe un meilleur chargement que celui du glouton, et appelons-le M.

Le glouton remplit le car en commençant par la marchandise la plus dense. Puisque tout est fractionnable, il remplit toujours le car entièrement (sauf si l'on a moins de 15 kg de marchandise en tout, cas sans intérêt). M aussi remplit le car entièrement, sinon il suffirait d'ajouter n'importe quoi pour l'améliorer.

Les deux chargements pèsent donc 15 kg. S'ils diffèrent, c'est qu'il existe une marchandise A, plus dense, dont M prend moins que le glouton, et une marchandise B, moins dense, dont M prend davantage.

Retirons alors de M un kilo de B et remplaçons-le par un kilo de A. Le poids total ne bouge pas : toujours 15 kg. Mais comme A est plus dense que B :

valeur gagnée (1 kg de A) > valeur perdue (1 kg de B)

Donc M vient d'augmenter. Or nous l'avions supposé maximal : c'est contradictoire.

Aucun chargement ne peut donc faire mieux que le glouton. ∎

Ce raisonnement porte un nom : l'argument d'échange. On prend une prétendue meilleure solution, on montre qu'on peut la rapprocher de la solution gloutonne sans jamais la dégrader, et on en conclut que le glouton est au moins aussi bon. C'est la façon standard de prouver qu'un glouton est optimal, et nous la réutiliserons au chapitre 6.

Pourquoi l'argument ne marchait pas au chapitre 3

Voilà la question importante. Relisons l'échange : « retirons un kilo de B et mettons un kilo de A ».

En sacs entiers, c'est impossible. On ne retire pas un kilo de safou : on retire le sac entier, ou rien. L'échange ne se fait plus kilo pour kilo, il se fait sac pour sac, et les sacs n'ont pas le même poids. Toute la démonstration s'effondre.

C'est la divisibilité qui rend le glouton exact. Retirez-la, et il redevient une approximation.

Le code

def charger_fractionnaire(marchandises, capacite):
    # marchandises : liste de (nom, poids, valeur). Les lots sont divisibles
    par_densite = sorted(marchandises,
                         key=lambda m: m[2] / m[1],
                         reverse=True)

    reste = capacite
    valeur = 0.0
    chargement = []

    for nom, poids, prix in par_densite:
        if reste <= 0:
            break

        pris = min(poids, reste)              # tout, ou juste ce qui tient
        valeur += prix * pris / poids         # on paie au prorata
        chargement.append((nom, pris))
        reste -= pris

    return valeur, chargement

>>> charger_fractionnaire(MARCHANDISES, 15)
(135000.0, [('Poivre de Penja', 9), ('Cacao', 6)])

Une seule ligne sépare ce code de celui du chapitre 3 : le min(poids, reste) qui autorise la coupe, au lieu du test si ça rentre entièrement.

Complexité

Étape	Coût
Calcul des densités	O(n)
Tri par densité	O(n log n)
Remplissage	O(n)
Total	O(n log n)

Le tri domine. Sur un million de marchandises, c'est encore immédiat : là où la force brute aurait abandonné bien avant la cinquantième.

Une leçon de modélisation. Deux problèmes qui se ressemblent comme deux gouttes d'eau, même car, mêmes sacs, même capacité, se comportent de façon radicalement différente selon un détail de l'énoncé.

Avant de choisir un algorithme, lisez l'énoncé jusqu'au bout. La question « les objets sont-ils divisibles ? » décide à elle seule entre un glouton exact en O(n log n) et un problème NP-difficile.

À retenir

Sac fractionnaire : on peut prendre une partie d'un lot, et payer au prorata.
Même critère qu'avant, la densité, mais le glouton devient exact.
La preuve se fait par argument d'échange : un kilo du plus dense contre un kilo du moins dense.
Cet échange est impossible avec des sacs entiers : c'est là que tout se joue.

Exercices d'application

Exercice 1

Avec une capacité de 20 kg au lieu de 15, que charge le glouton fractionnaire, et pour quelle valeur ?

Voir le corrigeMasquer le corrige

On reprend l'ordre par densité : poivre (11 111), cacao (5 833), safou (5 000), ndolé (4 286), miel (4 000).

poivre :  9 kg entiers   -> 100 000      reste 11 kg
cacao  : 11 kg sur 12    ->  70 000 x 11/12
                         =   64 167      reste  0 kg

total  : 20 kg           ->  164 167 FCFA

Le cacao est pris aux onze douzièmes. Il reste un kilo de cacao à quai, et le safou, le ndolé et le miel ne partent pas du tout.

Noter qu'on ne coupe qu'une seule marchandise, la dernière. C'est une propriété générale du sac fractionnaire : toutes les marchandises retenues sont prises en entier sauf au plus une, celle qui boucle le chargement.

Exercice 2

Démontrez que, dans le sac à dos fractionnaire, au plus une marchandise est coupée.

Voir le corrigeMasquer le corrige

Suivons l'algorithme. Il parcourt les marchandises par densité décroissante et, pour chacune, prend min(poids, reste).

Deux cas se présentent à chaque tour :

poids ≤ reste : la marchandise est prise en entier. Elle n'est pas coupée.
poids > reste : on en prend reste kilos. Elle est coupée, mais alors reste devient exactement zéro.

Dès que reste vaut zéro, la boucle s'arrête (le break). Aucune marchandise suivante n'est donc examinée, et a fortiori aucune n'est coupée.

La coupe ne peut survenir qu'une fois, et c'est nécessairement la dernière opération. ∎

Cette propriété a une conséquence pratique : la solution du sac fractionnaire ne diffère de celle du sac entier que par un seul objet. C'est ce qui fournit la borne supérieure utilisée dans les algorithmes exacts de type séparation-évaluation.

Exercice 3

Un commerçant propose du poivre à 100 000 FCFA les 9 kg, mais exige qu'on prenne au moins 5 kg. Le glouton fractionnaire fonctionne-t-il encore ?

Voir le corrigeMasquer le corrige

Non, la démonstration tombe.

L'argument d'échange repose sur la possibilité de déplacer n'importe quelle quantité, aussi petite soit-elle, d'une marchandise à l'autre. Un minimum d'achat brise cette liberté.

Concrètement, imaginons une capacité de 7 kg. Le glouton voudrait prendre 7 kg de poivre : c'est permis (7 ≥ 5). Mais si la capacité n'était que de 3 kg, il ne pourrait pas prendre de poivre du tout, alors qu'il est de loin le plus rentable. Il devrait se rabattre sur le cacao, et un algorithme qui doit choisir entre « respecter le minimum sur A » et « prendre B » n'est plus un glouton simple.

On retombe sur un problème combinatoire : pour chaque marchandise, la décision « j'en prends, ou pas du tout » redevient binaire. C'est le sac à dos 0-1 déguisé, avec toute sa difficulté.

Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.