Le sac de valeur maximum

Cours · algorithmique (école d'ingénieur), chapitre 2 · école d'ingénieur, informatique · le début du chapitre, la suite sur Adloun

Objectifs du chapitre

Modéliser un problème de choix d'objets sous contrainte de contenance (le « sac à dos »).
Montrer, par des contre-exemples, que les stratégies gloutonnes naturelles ne le résolvent pas.
Établir l'équation de récurrence à deux paramètres $m (k, c)$ , la calculer dans un tableau à deux dimensions et reconstruire un sac optimal.
Réutiliser le même schéma sur deux variantes : les spots publicitaires et le sous-ensemble de somme donnée.

2.1 Le problème

On dispose de $n$ objets numérotés $0, 1, \dots, n - 1$ . L'objet $i$ a une taille $t_{i}$ et une valeur $v_{i}$ , deux entiers strictement positifs. On dispose aussi d'un sac de contenance $C$ , un entier positif ou nul.

Définition 2.1Sac, taille et valeur d'un sous-ensemble

La taille d'un sous-ensemble d'objets est la somme des tailles de ses éléments ; sa valeur est la somme de leurs valeurs. Un sac de contenance $C$ est un sous-ensemble d'objets de taille inférieure ou égale à $C$ . Chaque objet est disponible en un seul exemplaire : il est dans le sac ou il n'y est pas.

Problème

Calculer un sac de contenance $C$ de valeur maximum.

Ce problème, connu en anglais sous le nom de 0/1 knapsack problem, est l'un des plus étudiés de l'optimisation discrète. Il modélise d'innombrables situations : choisir des projets sous une contrainte de budget, charger un camion, découper une barre de métal, remplir un créneau publicitaire (section 2.8), composer un portefeuille d'investissements…

Exemple 2.2cinq objets, un sac de contenance

10

objet $i$	0	1	2	3	4
valeur $v_{i}$	11	4	5	4	4
taille $t_{i}$	9	3	2	3	3

Le sac ${1, 2, 3}$ a pour taille $3 + 2 + 3 = 8 \leq 10$ et pour valeur $4 + 5 + 4 = 13$ . Nous verrons qu'aucun sac de contenance $10$ ne fait mieux. On remarque que ce sac optimal n'est pas « rempli à ras bord » : il reste deux unités de place libre, et pourtant on ne peut pas faire mieux.

En Java, les données sont deux tableaux $V [0 : n]$ et $T [0 : n]$ de termes généraux $V [i] = v_{i}$ et $T [i] = t_{i}$ , et un entier $C$ .

2.2 Deux gloutons et un contre-exemple

2.2.1 Glouton par valeurs décroissantes

Première idée : « je prends d'abord les objets les plus précieux ». On range les objets par valeurs décroissantes, puis on les examine dans cet ordre en ajoutant au sac chaque objet qui tient dans la place restante.

Sur l'exemple, l'objet $0$ (valeur $11$ , taille $9$ ) est pris en premier ; il ne reste qu'une unité de place, aucun autre objet n'entre. Le sac glouton vaut $11$ , contre $13$ pour le sac ${1, 2, 3}$ . L'objet le plus précieux est aussi le plus encombrant : il « bouche » le sac.

2.2.2 Glouton par rapport valeur/taille

Deuxième idée, plus fine : « je prends d'abord les objets les plus rentables », c'est-à-dire ceux dont la valeur par unité de taille $v_{i} / t_{i}$ est la plus grande. Sur l'exemple, l'objet $2$ a le meilleur rapport ( $5/2$ ), suivi des objets $1, 3, 4$ ( $4/3$ ), puis de l'objet $0$ ( $11/9$ ). Ce glouton construit ${2, 1, 3}$ de valeur $13$ : il trouve l'optimum… par chance.

Exemple 2.3le glouton par rapport mis en défaut

Trois objets de (taille, valeur) $(6, 7)$ , $(5, 5)$ , $(5, 5)$ , et un sac de contenance $C = 10$ . Le premier objet a le meilleur rapport ( $7/6 > 1$ ) ; une fois pris, il reste $4$ unités de place et aucun autre objet n'entre. Le sac glouton vaut $7$ . Or le sac formé des deux autres objets vaut $10$ .

Le programme SacGlouton.java compare les deux gloutons à la valeur maximum $m (n, C)$ calculée plus loin :


$ java SacGlouton
V = [11, 4, 5, 4, 4], T = [9, 3, 2, 3, 3], C = 10
  glouton par valeurs        : 11
  glouton par valeur/taille  : 13
  valeur maximum m(n,C)      : 13
V = [7, 5, 5], T = [6, 5, 5], C = 10
  glouton par valeurs        : 7
  glouton par valeur/taille  : 7
  valeur maximum m(n,C)      : 10

À retenir

Aucun des deux gloutons ne résout le problème du sac. Le second est souvent bon en pratique, mais « souvent bon » n'est pas « juste ».

2.2.3 L'énumération exhaustive

Chaque objet est dans le sac ou n'y est pas : il y a $2^{n}$ sous-ensembles. Pour $n = 60$ objets, $2^{60} \approx 1, 15 \times 1 0^{18}$ : à un milliard de sous-ensembles examinés par seconde, il faudrait plus de 36 ans. L'énumération est juste mais inutilisable dès que $n$ dépasse quelques dizaines.

2.3 Supposons le problème résolu

Appliquons la méthode du chapitre 1. Notons $m (n, C)$ la valeur maximum d'un sac de contenance $C$ dont le contenu est un sous-ensemble des $n$ objets, et considérons un tel sac optimal $s$ . Regardons le dernier objet, celui de numéro $n - 1$ . Il n'y a que deux cas.

La suite du cours est sur Adloun

Le chapitre en entier, formules et figures comprises, avec le tuteur, les fiches, les QCM et les exercices.

Lire la suite du cours

En accès libre, sans inscription.

Exercices corrigés de ce chapitre

Lire la suite du cours →