Lengteverschillen

Oplossing

Let op: de getallen in deze oplossing komen niet noodzakelijk overeen met die in de opgave.

Door de grootste jongen te laten dansen met het grootste meisje, de tweede grootste jongen met het tweede grootste meisje, enzovoort, krijg je de beste uitkomst.

Een zeer efficiënte manier om deze paren te maken, bestaat erin dat je de jongens rangschikt van groot naar klein, en de meisjes ook. Dit levert automatisch paren op waarvan de som van de verschillen het kleinst is.

Andere manieren van werken kunnen leiden tot dezelfde som van verschillen, maar de hierboven geschetste aanpak laat toe de opgave met zekerheid snel en eenvoudig op te lossen.

Dit is informatica!

Deze opgave vraagt dat we een bepaalde grootheid optimaliseren door elementen (hier: deelnemers aan een bal) te herschikken.

Optimalisatieproblemen zijn in het algemeen zeer moeilijk op te lossen. Het probleem van de opgave valt echter in een speciale categorie, waarvoor wel efficiënte oplossingsmethoden bestaan. Het is immers een probleem waarvoor zogenaamde gulzige aanpakken correct zullen werken. Een gulzig algoritme neemt telkens een kleine stap in de oplossingsruimte die leidt tot een betere uitkomst. Als er geen dergelijke stap gevonden wordt in de onmiddellijke buurt van de huidige kandidaat-oplossing, rapporteert het algoritme de huidige kandidaat-oplossing als optimale oplossing. Dit is correct, op voorwaarde dat elk lokaal optimum ook een globaal optimum is. Dat is niet altijd het geval, maar voor deze opgave wel.