Combien de répartitions ? — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 4)

Combien de répartitions ?

Répartition optimale d'une ressource · niveau 2

Énoncé

On note $N (k, s)$ le nombre de répartitions d'un stock $s$ sur $k$ entrepôts, c'est-à-dire de suites $(s_{0}, \dots, s_{k - 1})$ d'entiers positifs ou nuls de somme inférieure ou égale à $s$ .

Supposer le problème résolu et établir la récurrence des valeurs $N (k, s)$ (base et hérédité).
Calculer $N (4, 5)$ à l'aide d'un programme, et comparer avec $(4 9)$ .
Calculer $N (20, 100)$ . Conclure sur l'énumération exhaustive.

Corrigé

Supposons connues toutes les répartitions sur $k$ entrepôts. Le $k$ -ème entrepôt reçoit $s^{'}$ unités, $0 \leq s^{'} \leq s$ , et les $k - 1$ premiers reçoivent une répartition de somme au plus $s - s^{'}$ . Ces cas sont disjoints.

Base. $N (0, s) = 1$ pour tout $s$ (la seule répartition est la suite vide).

Hérédité. $\forall k \geq 1$ , $\forall s$ : $N (k, s) = s^{'} = 0 \sum s N (k - 1, s - s^{'})$ .

Le calcul est le même que celui des gains maximum, en remplaçant $max$ par une somme (et des entiers longs, car les nombres deviennent vite énormes) :


BigInteger[][] N = new BigInteger[n + 1][S + 1];
for (int s = 0; s < S + 1; s++) N[0][s] = BigInteger.ONE;   // base
for (int k = 1; k < n + 1; k++)
    for (int s = 0; s < S + 1; s++) {
        N[k][s] = BigInteger.ZERO;
        for (int sp = 0; sp < s + 1; sp++) N[k][s] = N[k][s].add(N[k - 1][s - sp]);
    }

On obtient $N (4, 5) = 126 = (4 9)$ . De façon générale $N (n, S) = (n S + n)$ : une répartition de somme au plus $S$ correspond à une répartition de somme exactement $S$ sur $n + 1$ entrepôts (le dernier recevant le reliquat).

$N (20, 100) = 29462227291176635718126 \approx 2, 9 \times 1 0^{22}$ . Même à un milliard de répartitions par seconde, l'énumération demanderait près d'un million d'années, alors que la programmation dynamique fait $n S^{2} /2 \approx 1 0^{5}$ opérations.


N(4,5) = 126
N(20,100) = 29462227291176635718126