Contre-exemples — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Contre-exemples

Le sac de valeur maximum · niveau 2

Énoncé

Construire un exemple à trois objets sur lequel le glouton par tailles croissantes (« on met d'abord les petits objets ») échoue.
Montrer que, pour tout entier $N$ , il existe une instance où la valeur maximum vaut au moins $N$ fois la valeur du sac obtenu par le glouton par rapport valeur/taille. Deux objets suffisent.

Contenance $C = 2$ , deux objets de taille $1$ et de valeur $1$ , un objet de taille $2$ et de valeur $10$ . Le glouton par tailles croissantes met les deux petits objets : valeur $2$ . Le sac optimal contient le gros objet : valeur $10$ .
Contenance $C$ , un objet $A$ de taille $1$ et de valeur $2$ (rapport $2$ ), un objet $B$ de taille $C$ et de valeur $2 C - 1$ (rapport $2 - 1/ C < 2$ ). Le glouton prend d'abord $A$ ; $B$ ne rentre plus : valeur $2$ . Le sac ${B}$ vaut $2 C - 1$ . Le rapport des deux valeurs est $(2 C - 1) /2$ , qui dépasse $N$ dès que $C \geq N + 1$ . Le programme le confirme :


tailles croissantes : glouton 2, optimum 10
rapport, C = 11 : glouton 2, optimum 21
rapport, C = 101 : glouton 2, optimum 201

Le glouton par rapport n'est donc pas « presque optimal » : il peut se tromper d'un facteur arbitrairement grand.