Somme d'un sous-ensemble, et un mot sur « polynomial »

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 17 — Programmation dynamique

Énoncé

Le programme cite « le problème de la somme d'un sous-ensemble ». Étant donnés $n$ entiers positifs et une cible $S$ , décider s'il existe un sous-ensemble de somme exactement $S$ . Écrire l'algorithme, sa complexité, et dire pourquoi elle n'est pas polynomiale.

Corrigé

Sous-problème : $A [i] [s]$ vaut vrai si l'on peut atteindre la somme $s$ avec les $i$ premiers éléments.

$A [0] [0] = vrai, A [0] [s] = faux (s \geq 1),$

$A [i] [s] = A [i - 1] [s] \lor (s \geq t_{i} \land A [i - 1] [s - t_{i}]) .$

En une seule ligne, avec la boucle décroissante de l'exercice précédent :


/* Vrai ssi un sous-ensemble de t[0..n-1] a pour somme S.
   Preconditions : t[i] >= 1, n >= 0, S >= 0.
   Complexite : Theta(nS) en temps, Theta(S) en memoire. */
bool sous_ensemble(const int t[], int n, int S) {
    assert(n >= 0 && S >= 0);
    bool a[S + 1];
    a[0] = true;
    for (int s = 1; s <= S; s = s + 1) { a[s] = false; }
    for (int i = 0; i < n; i = i + 1) {
        /* DECROISSANT : chaque element au plus une fois (exercice precedent). */
        for (int s = S; s >= t[i]; s = s - 1) {
            if (a[s - t[i]]) { a[s] = true; }
        }
    }
    return a[S];
}

Mesure sur $t = {2, 3, 7, 8, 10}$ : les sommes atteignables sont

$0, 2, 3, 5, 7, 8, 9, 10, 11, 12, 13, 15, 17, 18, 19, 20, 21, 22, 23, 25, 27, 28, 30,$

soit $23$ valeurs distinctes pour $2^{5} = 32$ sous-ensembles : plusieurs sous-ensembles partagent donc la même somme. Les sommes non atteignables entre $0$ et $30$ sont $1, 4, 6, 14, 16, 24, 26, 29$ .

Pourquoi $Θ (n S)$ n'est pas polynomial. C'est l'avertissement du chapitre sur $Θ (n C)$ , au même endroit. La taille de l'entrée est le nombre de bits nécessaires pour l'écrire, soit environ $n lo g_{2} S$ bits. Doubler le nombre de chiffres de $S$ élève $S$ au carré, donc élève le temps au carré aussi : le coût est exponentiel en la taille de l'écriture. Concrètement, $n = 40$ et $S = 1 0^{15}$ tiennent en une ligne de texte et sont hors de portée. On dit que l'algorithme est pseudo-polynomial. Le problème lui-même est np-complet (chapitre chap:decidabilite), et la programmation dynamique ne le rend pas facile : elle le rend faisable quand les nombres sont petits.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.