Solution
Remarque : les données de la correction ne correspondent pas forcément à
celles de votre sujet.
En associant le plus grand garçon avec la plus grande fille, puis le second plus grand garçon avec la seconde
plus grande fille,
etc... jusqu'au plus petit garçon avec la plus petite fille, on obtient la meilleure configuration.
Une manière très efficace d'associer les danseurs et danseuses de cette manière est de trier tous les garçons
par taille, puis toutes les filles de la même manière. On obtient alors automatiquement des associations qui
donnent
le meilleur résultat possible.
D'autres configurations permettent d'obtenir le même total des différences, mais celle qui consiste à trier les
danseurs permet de résoudre à coup sûr le sujet de manière très simple.
C'est de l'informatique !
On essaie ici d'optimiser une certaine mesure, calculée selon la manière dont on range des
éléments (ici, des danseurs et danseuses).
Dans ce sujet, à chaque fois que l'on voit qu'on a deux paires de danseurs (deux garçons associés à deux
filles), et qu'on pourrait diminuer
la somme des différences en recomposant les deux paires
(en mettant le premier garçon avec la seconde fille, et le second garçon avec la première fille), on a intérêt
à faire ce changement.
Lorsqu'il n'y a plus aucune possibilité pour recomposer une paire de la sorte en améliorant le résultat, alors
on a forcément obtenu une configuration optimale (c'est-à-dire la meilleure possible).
Comme dans ce sujet, il existe de nombreuses situations en informatique où l'on peut partir d'une configuration
arbitraire, et ensuite l'améliorer petit à petit, jusqu'à converger vers une configuration
optimale. Autrement dit, on peut converger vers le maximum global en effectuant une succession de petites
améliorations locales.
