Compter les sous-ensembles — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Compter les sous-ensembles

Le sac de valeur maximum · niveau 2

Énoncé

On ne veut plus savoir s'il existe un sous-ensemble de $X$ de somme $S$ , mais combien il en existe. On note $c (k, s)$ le nombre de sous-ensembles des $k$ premiers éléments de somme $s$ .

Donner l'équation de récurrence des valeurs $c (k, s)$ . Que vaut $c (0, 0)$ ? Pourquoi ?
Écrire la fonction long compter(int[] X, int S).
Combien de sous-ensembles de ${1, 2, 3, 4, 5}$ ont pour somme $10$ ? Les énumérer. Et de ${1, \dots, 10}$ pour la somme $20$ ?

Corrigé

Les sous-ensembles des $k$ premiers éléments de somme $s$ se partagent en deux familles disjointes : ceux qui ne contiennent pas $x_{k - 1}$ (il y en a $c (k - 1, s)$ ) et ceux qui le contiennent (autant que de sous-ensembles des $k - 1$ premiers de somme $s - x_{k - 1}$ ). On additionne au lieu de prendre un maximum. Base : $c (0, 0) = 1$ (le sous-ensemble vide a pour somme $0$ , et c'est le seul sous-ensemble de l'ensemble vide), $c (0, s) = 0$ pour $s \geq 1$ . Hérédité : $\forall k \geq 1$ , $\forall s$ ,

$c (k, s) = c (k - 1, s) + {c (k - 1, s - x_{k - 1}) 0 si x_{k - 1} \leq s, sinon.$


static long compter(int[] X, int S) { int n = X.length;
    long[][] N = new long[n + 1][S + 1];
    N[0][0] = 1;                                     // base
    for (int k = 1; k < n + 1; k++)
        for (int s = 0; s < S + 1; s++)
            N[k][s] = N[k-1][s] + (X[k-1] <= s ? N[k-1][s - X[k-1]] : 0);
    return N[n][S];
}

Le programme donne $3$ sous-ensembles de ${1, \dots, 5}$ de somme $10$ : ${1, 4, 5}$ , ${2, 3, 5}$ , ${1, 2, 3, 4}$ . Pour ${1, \dots, 10}$ et la somme $20$ , il en trouve $31$ . Les nombres de sous-ensembles croissent vite : on utilise des long.