Répétitions bornées — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 3)

Répétitions bornées

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

Énoncé

L'objet $i$ est disponible en $b_{i}$ exemplaires au plus.

Adapter la première version de la récurrence. Quelle est la complexité du calcul ?
Application : $T = [3, 4, 5]$ , $V = [4, 5, 7]$ , $b = [1, 2, 1]$ , $C = 11$ .
Pourquoi la seconde version (« aucun exemplaire, ou au moins un ») ne s'adapte-t-elle pas directement ?

$m (k, c) = max {r v_{k - 1} + m (k - 1, c - r t_{k - 1}) : 0 \leq r \leq b_{k - 1}, r t_{k - 1} \leq c},$

avec la même base $m (0, c) = 0$ . Chaque case demande au plus $b_{k - 1} + 1$ termes : la complexité est $Θ (C \sum_{i} (b_{i} + 1))$ .

Le programme donne $m (3, 11) = 14$ : deux exemplaires de l'objet $1$ (taille $8$ , valeur $10$ ) et un de l'objet $0$ (taille $3$ , valeur $4$ ). Le sac optimal sans borne ( $15$ , deux exemplaires de l'objet $0$ ) est interdit puisque $b_{0} = 1$ .
La seconde version ajoute un exemplaire de l'objet $k - 1$ à un sac $m (k, c - t_{k - 1})$ dont on ignore combien d'exemplaires il contient déjà : rien ne garantit que la borne $b_{k - 1}$ est respectée. Il faudrait ajouter ce nombre comme paramètre de la valeur.