In 2018 werd er te Gent een drama ontketend: met behulp van digitale wachtrijen probeerde men het scholentoekenningsprobleem algoritmisch op te lossen. Zo voorkomt men dat ouders beginnen kamperen voor de schoolpoort om hun zoon/dochter in de meest populaire scholen in te schrijven. Het algoritme ging eerlijk aan het werk, maar toch was er zeer veel ontevredenheid. Er waren namelijk nog problemen met “wissels” (twee of meer studenten die hun voorkeur wel zouden krijgen moesten ze gewoon onderling wisselen) en dergelijke.

De vraag die vanzelf in je opkomt is natuurlijk, “hoe moeilijk kan het zijn om met een computer de perfecte oplossing te vinden?” In deze opgave kunnen jullie zelf het antwoord op deze vraag vinden, want we proberen het scholentoekenningsprobleem op te lossen met een branch-and-bound-algoritme. Een correct branch-and-bound-algoritme zal voor gegeven invoer de optimale oplossing geven door elk deel van de zoekruimte te bekijken waar mogelijks nog verbetering in schuilt.

Merk op dat we het probleem lichtelijk wijzigen van de werkelijke situatie: zo houden we geen rekening met de aparte verdeling voor indicatorleerlingen en laten we de ouders maximaal 5 scholen in volgorde opgeven.

Opgave

Een school heeft een naam en een capaciteit. Deze scholen worden voorgesteld door een map met als keys de schoolnamen en als values capaciteiten. De capaciteit geeft aan hoeveel studenten aan deze school kunnen inschrijven. Een student wordt voorgesteld door een tuple(naam, [school1, ..., school5 ]) en heeft maximaal 5 voorkeurscholen. Een oplossing (van de vorm [(naam student, naam school), ...]) kent aan elke student een school (of None) toe. Komt een student in zijn eerste voorkeursschool terecht, verdient de oplossing 32 punten. Komt hij in zijn tweede voorkeursschool terecht, verdient de oplossing 16 punten (enzovoort). Merk op dat met een student met slechts twee voorkeursscholen (None voor de andere drie) dan 8 punten te verdienen zijn door hem geen school te geven. De totale score van een oplossing is de som van de scores voor elke toekenning.

Schrijf hiervoor een Python-functie assign(schools: list, students: list) die de één van de hoogst scorende oplossingen teruggeeft, door elke student in students te mappen op een school in schools of None. Je mag uiteraard de capaciteit van de scholen niet overschrijden. Maak gebruik van een branch-and-bound-algoritme met minstens 1 bound.

Voorbeelden

>>> assign({}, [])
[]
>>> assign({'Wingerd': 1}, [('Tobiah', ['Wingerd'])])
[('Tobiah', 'Wingerd')]
>>> assign({'Wingerd' : 2, 'Voskenslaan': 2}, [('Tobiah', ['Wingerd', 'Voskenslaan']), ('Ciel', ['Voskenslaan', 'Wingerd'])])
[('Tobiah', 'Wingerd'), ('Ciel', 'Voskenslaan')]
>>> assign({'Wingerd' : 2, 'Voskenslaan': 2}, [('Tobiah', ['Wingerd', 'Voskenslaan']), ('Ciel', ['Voskenslaan', 'Wingerd']), ('Maëli', ['Voskenslaan', 'Wingerd'])])
[('Tobiah', 'Wingerd'), ('Ciel', 'Voskenslaan'), ('Maëli', 'Voskenslaan')]
>>> assign({'Wingerd' : 2, 'Voskenslaan': 1}, [('Tobiah', ['Wingerd', 'Voskenslaan']), ('Ciel', ['Voskenslaan', 'Wingerd']), ('Maëli', ['Voskenslaan', 'Wingerd'])])
[('Tobiah', 'Wingerd'), ('Ciel', 'Voskenslaan'), ('Maëli', 'Wingerd')]
>>> assign({'Wingerd' : 2, 'Voskenslaan': 1}, [('Tobiah', ['Wingerd', 'Voskenslaan']), ('Ciel', ['Voskenslaan', 'Wingerd']), ('Maëli', ['Voskenslaan', 'Wingerd']), ('Sebastijn', ['Wingerd', 'Voskenslaan'])])
[('Tobiah', 'Wingerd'), ('Ciel', 'Voskenslaan'), ('Maëli', None), ('Sebastijn', 'Wingerd')]