Un sac à la main — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Un sac à la main

Le sac de valeur maximum · niveau 1 (application)

Énoncé

Quatre objets de tailles $T = [2, 3, 4, 5]$ et de valeurs $V = [3, 4, 5, 6]$ , un sac de contenance $C = 5$ .

Calculer à la main le tableau $M$ ( $5$ lignes, $6$ colonnes) de terme général $M [k] [c] = m (k, c)$ .
En déduire un sac de valeur maximum en remontant le tableau depuis la case $(4, 5)$ .
Que donnent le glouton par valeurs décroissantes et le glouton par rapport valeur/taille décroissant ?

Ligne par ligne, $m (k, c) = m (k - 1, c)$ si $T [k - 1] > c$ , sinon $m (k, c) = max {m (k - 1, c), V [k - 1] + m (k - 1, c - T [k - 1])}$ :


k=4 : [0, 0, 3, 4, 5, 7]
k=3 : [0, 0, 3, 4, 5, 7]
k=2 : [0, 0, 3, 4, 4, 7]
k=1 : [0, 0, 3, 3, 3, 3]
k=0 : [0, 0, 0, 0, 0, 0]

Par exemple $m (2, 5) = max {m (1, 5), 4 + m (1, 2)} = max {3, 7} = 7$ .


nom : M[1]
valeurs : 0 0 3 3 3 3
vert : 2 5
legende : ligne k = 1 : on lit m(1,5) = 3 et m(1,2) = 3


nom : M[2]
valeurs : 0 0 3 4 4 7
colorier : 5
legende : m(2,5) = max(m(1,5), 4 + m(1,2)) = max(3, 7) = 7

$m (4, 5) = m (3, 5) = 7$ : l'objet $3$ n'est pas dans le sac ; $m (3, 5) = m (2, 5) = 7$ : l'objet $2$ non plus ; $m (2, 5) = 7 \neq = m (1, 5) = 3$ : l'objet $1$ est dans le sac, on passe en $(1, 5 - 3) = (1, 2)$ ; $m (1, 2) = 3 \neq = m (0, 2) = 0$ : l'objet $0$ est dans le sac. Le sac ${0, 1}$ a pour taille $2 + 3 = 5$ et pour valeur $7$ .
Le glouton par valeurs prend l'objet $3$ (valeur $6$ , taille $5$ ) et le sac est plein : $6$ . Le glouton par rapport (rapports $1, 5$ ; $1, 33$ ; $1, 25$ ; $1, 2$ ) prend les objets $0$ et $1$ : $7$ , ici optimal.