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

Cours · algorithmique (école d'ingénieur), chapitre 3 · école d'ingénieur, informatique · le début du chapitre, la suite sur Adloun

Objectifs du chapitre

Adapter la récurrence du sac lorsque chaque objet est disponible en nombre illimité d'exemplaires.
Mémoriser les arguments des maximums dans un tableau $A = ar g M$ pour reconstruire efficacement une solution.
Obtenir une seconde récurrence, plus rapide, en changeant la façon de découper les cas.
Passer à trois paramètres et à un tableau à trois dimensions avec le problème des deux sacs.

3.1 Le sac avec possibles répétitions

On reprend le problème du chapitre 2 avec une différence : chaque objet est disponible en autant d'exemplaires que l'on veut. Le sac peut contenir zéro, un, deux exemplaires ou plus de chaque objet, tant que la taille totale ne dépasse pas la contenance $C$ .

Définition 3.1Multi-ensemble

Un multi-ensemble est un « ensemble » dont les éléments peuvent apparaître en plusieurs exemplaires, par exemple ${5, 5, 2}$ . Un multi-sous-ensemble (MSE) d'un ensemble d'objets est un multi-ensemble dont tous les éléments sont des objets de cet ensemble. Sa taille et sa valeur sont les sommes des tailles et des valeurs de ses éléments, comptés avec leur multiplicité.

Problème

Calculer un MSE des $n$ objets de taille au plus $C$ et de valeur maximum.

Exemple 3.2deux objets, contenance

19

L'objet $0$ a pour valeur $2$ et pour taille $5$ ; l'objet $1$ a pour valeur $1$ et pour taille $3$ . Le sac de contenance $C = 19$ peut contenir trois exemplaires de l'objet $0$ (taille $15$ , valeur $6$ ) et un exemplaire de l'objet $1$ (taille $3$ , valeur $1$ ) : taille $18$ , valeur $7$ . C'est le maximum.

Avec les cinq objets du chapitre 2 ( $V = [11, 4, 5, 4, 4]$ , $T = [9, 3, 2, 3, 3]$ , $C = 10$ ), la possibilité de répéter change tout : cinq exemplaires de l'objet $2$ (taille $2$ , valeur $5$ ) donnent un sac de valeur $25$ , presque le double de la valeur $13$ obtenue sans répétition.

Attention

On ne peut pas se ramener au chapitre 2 en « dupliquant » chaque objet autant de fois qu'il pourrait entrer dans le sac ( $⌊ C / t_{i} ⌋$ copies) : c'est correct, mais le nombre d'objets devient de l'ordre de $C$ , et le calcul de l'ordre de $n C^{2}$ . Nous ferons mieux.

3.2 Première récurrence : combien d'exemplaires du dernier objet ?

3.2.1 Supposons le problème résolu

Notons $m (n, C)$ la valeur maximum d'un sac de contenance $C$ contenant un MSE des $n$ objets, et considérons un tel sac optimal. Le dernier objet (numéro $n - 1$ ) y figure en un certain nombre $r \geq 0$ d'exemplaires. Comme $r$ exemplaires occupent la place $r \cdot t_{n - 1}$ , nécessairement $r \cdot t_{n - 1} \leq C$ .

Fixons $r$ . Les $r$ exemplaires de l'objet $n - 1$ contribuent pour $r \cdot v_{n - 1}$ à la valeur du sac. Le reste du sac est un MSE des $n - 1$ premiers objets, de taille au plus $C - r \cdot t_{n - 1}$ , et ce reste est de valeur maximum : sinon, on le remplacerait par un MSE meilleur et le sac entier ne serait pas optimal. Sa valeur est donc $m (n - 1, C - r \cdot t_{n - 1})$ .

On ne connaît pas $r$ ; on prend le meilleur de toutes les valeurs possibles :

$m (n, C) = r \geq 0 r \cdot t_{n - 1} \leq C max {r \cdot v_{n - 1} + m (n - 1, C - r \cdot t_{n - 1})} .$

3.2.2 L'équation de récurrence

Proposition 3.3Sac avec répétitions (première version)

Pour $0 \leq k < n + 1$ et $0 \leq c < C + 1$ , $m (k, c)$ est la valeur maximum d'un sac de contenance $c$ contenant un MSE des $k$ premiers objets.

Base. $\forall c, 0 \leq c < C + 1$ : $m (0, c) = 0$ .

Hérédité. $\forall k, 1 \leq k < n + 1$ , $\forall c, 0 \leq c < C + 1$ :

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

Le cas $r = 0$ est toujours possible : il donne le terme $m (k - 1, c)$ . On retrouve le sac sans répétition en se limitant à $r \in {0, 1}$ .

3.3 Mémoriser les arguments : le tableau $A = ar g M$

Pour reconstruire le sac au chapitre 2, on comparait $M [k] [c]$ à $M [k - 1] [c]$ . Ici, il faudrait retrouver quelle valeur de $r$ donne le maximum, ce qui obligerait à refaire la boucle sur $r$ . Il est plus simple et plus efficace de retenir cette valeur au moment où on la trouve.

Définition 3.4Argument d'un maximum

On note $a (k, c) = ar g m (k, c)$ une valeur de $r$ pour laquelle le maximum de l'hérédité est atteint : c'est le nombre d'exemplaires du $k$ -ème objet dans un sac optimal $S (k, c)$ . Les valeurs $a (k, c)$ sont mémorisées « à la volée » dans un tableau $A [0 : n + 1] [0 : C + 1]$ , de mêmes dimensions que $M$ . Les valeurs $a (0, c)$ sont sans importance ; on les pose égales à $0$ .

La fonction de calcul doit retourner deux tableaux. En Java, on les range dans un tableau de tableaux : new int[][][] {M, A} est un tableau à trois dimensions dont la case $0$ est $M$ et la case $1$ est $A$ .

La suite du cours est sur Adloun

Le chapitre en entier, formules et figures comprises, avec le tuteur, les fiches, les QCM et les exercices.

Lire la suite du cours

En accès libre, sans inscription.

Exercices corrigés de ce chapitre

Lire la suite du cours →