La table du sac, remplie à la main

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 17 — Programmation dynamique

Énoncé

Quatre objets de poids $p = (2, 3, 4, 5)$ et de valeurs $v = (3, 4, 5, 6)$ , capacité $C = 5$ . Remplir la table $M$ du chapitre, lire l'optimum, puis reconstruire les objets choisis.

Corrigé

La table (ligne $i$ : les $i$ premiers objets ; colonne $c$ : la capacité) :

$c =$	2	3	4	5
$i = 0$	0	0	0	0
$i = 1$	3	3	3	3
$i = 2$	3	4	4	7
$i = 3$	3	4	5	7
$i = 4$	3	4	5	7

L'optimum est $M [4] [5] = 7$ .

La reconstruction se lit de bas en haut, à capacité courante $c = 5$ :

$i = 4$ : $M [4] [5] = M [3] [5] = 7$ , l'objet $4$ n'est pas pris ;
$i = 3$ : $M [3] [5] = M [2] [5] = 7$ , l'objet $3$ n'est pas pris ;
$i = 2$ : $M [2] [5] = 7 \neq = M [1] [5] = 3$ , l'objet $2$ est pris ; $c$ devient $5 - 3 = 2$ ;
$i = 1$ : $M [1] [2] = 3 \neq = M [0] [2] = 0$ , l'objet $1$ est pris ; $c$ devient $0$ .

Solution : les objets $1$ et $2$ , poids $2 + 3 = 5$ , valeur $3 + 4 = 7$ . La capacité restante est nulle, ce qui est un bon contrôle : elle doit toujours être $\geq 0$ , et l'on peut vérifier que la somme des poids des objets choisis vaut $C$ moins la capacité restante.

Le piège de la reconstruction est de tester m[i][c] > m[i-1][c] avec un $>$ strict et d'en tirer que l'objet est pris — c'est correct — mais d'oublier que l'égalité n'exclut rien : quand deux solutions de même valeur existent, la table n'en désigne qu'une. La remontée rend une solution optimale, jamais « la » solution optimale.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.