Deux sacs avec répétitions — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 3)

Deux sacs avec répétitions

Sacs avec répétitions, multi-ensembles et couples de sacs · niveau 2

Énoncé

Chaque objet est maintenant disponible en nombre illimité, et l'on remplit deux sacs de contenances $C_{0}$ et $C_{1}$ .

Donner une équation de récurrence des valeurs $m (k, c_{0}, c_{1})$ en vous inspirant de la seconde version du cours, et un ordre de calcul.
Montrer que le problème se ramène à deux sacs indépendants : $m (n, C_{0}, C_{1}) = m (n, C_{0}) + m (n, C_{1})$ , où $m (n, c)$ est la valeur du sac avec répétitions. Vérifier sur $T = [3, 4, 5]$ , $V = [4, 5, 7]$ , $C_{0} = 5$ , $C_{1} = 6$ .

Corrigé

Pour l'objet $k - 1$ : aucun exemplaire nulle part, ou au moins un exemplaire dans $S_{0}$ , ou au moins un dans $S_{1}$ . Base : $m (0, c_{0}, c_{1}) = 0$ . Hérédité :

$m (k, c_{0}, c_{1}) = max {m (k - 1, c_{0}, c_{1}), v_{k - 1} + m (k, c_{0} - t_{k - 1}, c_{1}), v_{k - 1} + m (k, c_{0}, c_{1} - t_{k - 1})},$

les deux derniers termes existant si $t_{k - 1} \leq c_{0}$ (resp. $c_{1}$ ). On calcule par $k$ croissants, puis $c_{0}$ et $c_{1}$ croissants.

Avec des répétitions, les objets placés dans $S_{0}$ ne privent plus $S_{1}$ de rien : chaque sac peut prendre autant d'exemplaires qu'il veut. Le contenu optimal de $S_{0}$ est donc un sac avec répétitions optimal de contenance $C_{0}$ , indépendamment de $S_{1}$ , et réciproquement. Le programme confirme :


repetitions, C0 = 5, C1 = 6 : 15 = 7 + 8

( $S_{0}$ : un objet de taille $5$ , valeur $7$ ; $S_{1}$ : deux objets de taille $3$ , valeur $8$ .) Le tableau à trois dimensions est inutile : deux calculs en $Θ (n C)$ suffisent.