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

p

sacs

Sacs avec répétitions, multi-ensembles et couples de sacs · niveau 3 (difficile)

Énoncé

Généraliser le problème des deux sacs à $p$ sacs de contenances $C_{0}, \dots, C_{p - 1}$ . Combien de cas comporte l'hérédité ? Quelle est la taille du tableau et la complexité du calcul ? Pour quelles valeurs de $p$ cette approche reste-t-elle raisonnable ?

Corrigé

Pour chaque objet, il y a $p + 1$ cas : dans aucun sac, ou dans l'un des $p$ sacs. La valeur $m (k, c_{0}, \dots, c_{p - 1})$ a $p + 1$ paramètres :

$m (k, c_{0}, \dots, c_{p - 1}) = max {m (k - 1, c_{0}, \dots, c_{p - 1}), i : t_{k - 1} \leq c_{i} max (v_{k - 1} + m (k - 1, \dots, c_{i} - t_{k - 1}, \dots))} .$

Le tableau a $(n + 1) \prod_{i} (C_{i} + 1)$ cases, chacune calculée en $Θ (p)$ : complexité $Θ (n p \prod_{i} (C_{i} + 1))$ , soit $Θ (n p C^{p})$ si toutes les contenances valent $C$ . Avec $C = 100$ , on dépasse $1 0^{10}$ cases dès $p = 5$ : l'approche n'est raisonnable que pour $p = 2$ ou $3$ et de petites contenances. Le problème des sacs multiples est NP-difficile ; on le traite en pratique par des heuristiques.