Partage équitable — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 2)

Partage équitable

Le sac de valeur maximum · niveau 2

Énoncé

Deux héritiers se partagent $n$ objets de valeurs entières $x_{0}, \dots, x_{n - 1}$ , de somme totale $Σ$ . On veut que l'écart entre les valeurs des deux lots soit le plus petit possible.

Montrer que le problème revient à trouver la plus grande somme $s \leq Σ/2$ atteignable par un sous-ensemble.
En déduire un algorithme qui utilise le tableau $E$ de la variante booléenne. Quelle est sa complexité ?
Application : $x = [8, 6, 5, 4, 2]$ .

Corrigé

Si l'un des lots a la valeur $s$ , l'autre a la valeur $Σ - s$ et l'écart est $∣ Σ - 2 s ∣$ . Quitte à échanger les lots, on peut supposer $s \leq Σ/2$ ; l'écart $Σ - 2 s$ est alors d'autant plus petit que $s$ est grand. On cherche donc la plus grande somme $s \leq Σ/2$ atteinte par un sous-ensemble.
On calcule $E [0 : n + 1] [0 : ⌊ Σ/2 ⌋ + 1]$ comme dans le cours, puis on cherche le plus grand $s$ tel que $E [n] [s]$ est vrai (il en existe : $E [n] [0]$ est vrai) ; la fonction d'affichage du cours donne le lot. Complexité $Θ (n Σ)$ .
$Σ = 25$ :


partage de [8, 6, 5, 4, 2] (total 25) : lot de valeur 12, l'autre 13, ecart 1 ; lot : 4 8

Un écart nul est impossible puisque $Σ$ est impair : le partage ${8, 4}$ / ${6, 5, 2}$ est optimal.


nom : E[5]
valeurs : V F V F V V V V V V V V V
colorier : 12
legende : V = vrai ; plus grand s ≤ 12 avec E[5][s] vrai : s = 12 (lot 8 + 4)