Juliette veut la moyenne partout — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 4)

Juliette veut la moyenne partout

Répartition optimale d'une ressource · niveau 3 (difficile)

Énoncé

On reprend Juliette et ses trois unités (coefficients $C = [4, 3, 4]$ , notes estimées du chapitre). Juliette refuse toute note inférieure à $10$ .

Modifier la récurrence pour n'autoriser que les nombres d'heures $h$ tels que $e (i, h) \geq 10$ . Indication : un choix interdit rapporte $- \infty$ .
Quel est le nombre minimum d'heures de révision qui garantit au moins $10$ dans chaque unité ? Quelle somme pondérée obtient-elle alors ?
Avec $10$ heures, la contrainte change-t-elle la répartition optimale du chapitre ?

Corrigé

On pose $c_{i} e (i, h) = - \infty$ lorsque $e (i, h) < 10$ . La base reste $m (0, t) = 0$ , et l'hérédité devient, $\forall k, 1 \leq k < n + 1$ , $\forall t, 0 \leq t < H + 1$ :

$m (k, t) = 0 \leq h < t + 1 e (k - 1, h) \geq 10 max {c_{k - 1} e (k - 1, h) + m (k - 1, t - h)},$

avec $max \emptyset = - \infty$ . Dans le programme, on saute les choix interdits et les restes impossibles :


for (int h = 0; h < t + 1; h++) {
    if (E[k - 1][h] < 10 || M[k - 1][t - h] <= MOINS_INFINI / 2) continue;
    int v = C[k - 1] * E[k - 1][h] + M[k - 1][t - h];
    if (v > M[k][t]) { M[k][t] = v; A[k][t] = h; }
}

Le plus petit $t$ tel que $m (3, t) > - \infty$ est le nombre minimum d'heures. L'unité $0$ demande une heure (note $10$ ), l'unité $1$ aucune (note $16$ ), l'unité $2$ une heure (note $12$ ) :


Nombre minimum d'heures : 2, somme pondérée 136
  unité 0 : 1 h, note 10, pondérée 40
  unité 1 : 0 h, note 16, pondérée 48
  unité 2 : 1 h, note 12, pondérée 48

Non : avec $10$ heures, la répartition optimale du chapitre ( $3$ , $2$ et $5$ heures, somme pondérée $174$ ) donne déjà des notes $12$ , $18$ et $18$ , toutes supérieures à $10$ . La contrainte est inactive.


Avec 10 heures : somme pondérée 174
  unité 0 : 3 h, note 12, pondérée 48
  unité 1 : 2 h, note 18, pondérée 54
  unité 2 : 5 h, note 18, pondérée 72