Exactement p objets — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Exactement

p

objets

Le sac de valeur maximum · niveau 3 (difficile)

Énoncé

On impose en plus que le sac contienne exactement $p$ objets.

Proposer une valeur $m (k, c, q)$ à trois paramètres, son équation de récurrence (base et hérédité) et la complexité du calcul.
Sur l'exemple du cours ( $V = [11, 4, 5, 4, 4]$ , $T = [9, 3, 2, 3, 3]$ , $C = 10$ ), donner la valeur maximum pour $p = 1, 2, 3$ . Pourquoi la valeur pour $p = 2$ est-elle plus petite que pour $p = 1$ ?

Corrigé

Soit $m (k, c, q)$ la valeur maximum d'un sac de contenance $c$ contenant exactement $q$ objets parmi les $k$ premiers ( $- \infty$ si c'est impossible). Base : $m (0, c, 0) = 0$ et $m (0, c, q) = - \infty$ pour $q \geq 1$ . Hérédité : $\forall k \geq 1$ ,

$m (k, c, q) = max {m (k - 1, c, q), v_{k - 1} + m (k - 1, c - t_{k - 1}, q - 1)},$

le second terme n'existant que si $q \geq 1$ et $t_{k - 1} \leq c$ . Le tableau a $(n + 1) (C + 1) (p + 1)$ cases, chacune en temps constant : $Θ (n C p)$ , par $k$ croissants.

Le programme donne :


exactement 1 objet(s), C = 10 : 11
exactement 2 objet(s), C = 10 : 9
exactement 3 objet(s), C = 10 : 13

La contrainte « exactement » n'est pas monotone : l'objet de valeur $11$ (taille $9$ ) ne peut être accompagné d'aucun autre, et la meilleure paire est ${5, 4}$ (tailles $2 + 3$ ). Sans contrainte, le sac optimal compte $3$ objets et vaut $13$ .