Sous-ensemble de taille minimum — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Sous-ensemble de taille minimum

Le sac de valeur maximum · niveau 2

Énoncé

On reprend le problème du sous-ensemble de somme $S$ , mais on veut, parmi les sous-ensembles de somme $S$ , en afficher un qui a le plus petit nombre d'éléments. Exemple : $X = {3, 5, 2}$ et $S = 5$ ; on veut afficher ${5}$ et non ${3, 2}$ .

On note $p (k, s)$ le nombre minimum d'éléments d'un sous-ensemble des $k$ premiers éléments de $X$ de somme $s$ , avec $p (k, s) = + \infty$ s'il n'en existe pas. Donner l'équation de récurrence.
Écrire le calcul du tableau $P$ et la fonction d'affichage.
Application : $X = {1, 2, 3, 4, 5, 6}$ et $S = 10$ .

Corrigé

Supposons le problème résolu : un sous-ensemble de taille minimum des $k$ premiers éléments, de somme $s$ , contient ou non $x_{k - 1}$ . Base : $p (0, 0) = 0$ et $p (0, s) = + \infty$ pour $1 \leq s < S + 1$ . Hérédité : $\forall k, 1 \leq k < n + 1$ , $\forall s, 0 \leq s < S + 1$ ,

$p (k, s) = {p (k - 1, s) min {p (k - 1, s), 1 + p (k - 1, s - x_{k - 1})} si x_{k - 1} > s, sinon.$

On représente $+ \infty$ par INF = Integer.MAX_VALUE / 2 ( $INF + 1$ ne déborde pas).


static int[][] calculerP(int[] X, int S) { int n = X.length;
    int[][] P = new int[n + 1][S + 1];
    for (int s = 1; s < S + 1; s++) P[0][s] = INF;  // base ; P[0][0] = 0
    for (int k = 1; k < n + 1; k++)
        for (int s = 0; s < S + 1; s++) {
            P[k][s] = P[k-1][s];                          // x_{k-1} absent
            if (X[k-1] <= s && P[k-1][s - X[k-1]] + 1 < P[k][s])
                P[k][s] = P[k-1][s - X[k-1]] + 1;         // x_{k-1} présent
        }
    return P;
}
static void afficherP(int[][] P, int[] X, int k, int s) {
    // précondition : P[k][s] < INF. Appel principal : afficherP(P, X, n, S)
    if (k == 0) return;                              // sous-ensemble vide
    if (P[k][s] == P[k-1][s]) afficherP(P, X, k-1, s);
    else { afficherP(P, X, k-1, s - X[k-1]); System.out.print(" " + X[k-1]); }
}

Calcul en $Θ (n S)$ , affichage en $Θ (n)$ . -


X = [3, 5, 2], S = 5 : p = 1, sous-ensemble { 5 }
X = [1, 2, 3, 4, 5, 6], S = 10 : p = 2, sous-ensemble { 4 6 }

Parmi les sous-ensembles de somme $10$ (par exemple ${1, 2, 3, 4}$ ou ${1, 3, 6}$ ), ${4, 6}$ a le moins d'éléments.