Le plus léger des sacs optimaux — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Le plus léger des sacs optimaux

Le sac de valeur maximum · niveau 2

Énoncé

Plusieurs sacs peuvent avoir la valeur maximum. On veut, parmi eux, un sac de taille totale minimum.

Sur $V = [7, 4, 3, 3]$ , $T = [6, 3, 2, 2]$ , $C = 6$ , quel sac affiche la fonction asvm du cours ? Existe-t-il un sac de même valeur plus léger ?
Modifier le calcul pour qu'il mémorise, en plus de $m (k, c)$ , la taille $p (k, c)$ du sac retenu, et qu'il départage les égalités de valeur par la taille.

Corrigé

$m (4, 6) = 7$ . La fonction asvm préfère, en cas d'égalité, « l'objet n'est pas dans le sac » ; elle affiche le sac ${0}$ , de taille $6$ . Le sac ${1, 2}$ a la même valeur $4 + 3 = 7$ et pour taille $3 + 2 = 5$ .
On calcule en même temps $p (k, c)$ , la taille du sac retenu, et l'on compare les couples (valeur, taille) : plus grande valeur d'abord, plus petite taille en cas d'égalité.


for (int k = 1; k < n + 1; k++)
    for (int c = 0; c < C + 1; c++) {
        M[k][c] = M[k-1][c]; P[k][c] = P[k-1][c];      // objet k-1 absent
        if (T[k-1] <= c) {
            int v = V[k-1] + M[k-1][c - T[k-1]];
            int p = T[k-1] + P[k-1][c - T[k-1]];
            if (v > M[k][c] || (v == M[k][c] && p < P[k][c])) {
                M[k][c] = v; P[k][c] = p;                  // objet k-1 présent
            }
        }
    }

On obtient la valeur $7$ et la taille minimum $5$ . Pour afficher ce sac, on reconstruit en comparant les couples $(M, P)$ au lieu des seules valeurs $M$ (ou l'on mémorise un tableau $A$ des décisions).