Veronderstel dat drie personen de boeken op een boekenplank moeten doorkijken om een bepaald stuk informatie op te zoeken. De boeken worden zo eerlijk mogelijk verdeeld over de personen, maar wel zodanig dat elke persoon een stuk van de boekenplank toegewezen krijgt (zodat geen herschikken van de boeken nodig is). Gevraagd is om een goede verdeling van de boekenplank te bepalen.

Wanneer alle boeken evenveel pagina’s bevatten, dan kan de boekenplank in gelijke delen worden opgesplitst. Bijvoorbeeld,

100 100 100 - 100 100 100 - 100 100 100

en iedereen heeft 300 pagina’s te verwerken. Deze benadering werkt uiteraard niet als de boeken verschillende dikte hebben. Bijvoorbeeld, in de volgende verdeling

100 200 300 - 400 500 600 - 700 800 900

heeft de eerste persoon slechts 600 pagina’s te bekijken, terwijl de derde persoon er 2400 moet verwerken. Voor deze boekenplank is de volgende verdeling

100 200 300 400 500 - 600 700 - 800 900

uiteindelijk de eerlijkste.

Algemeen wordt het partitieprobleem als volgt geformuleerd. Gegeven een rij \(S\) van niet-negatieve getallen en een positief geheel getal \(k\). Gevraagd is om \(S\) te partitioneren in \(k\) deelrijen, zodanig dat de maximale som over alle deelrijen geminimaliseerd wordt.

1. Ontwerp een gretig algoritme voor het partitieprobleem. Geef een voorbeeldrij waarvoor deze gretige benadering niet de beste oplossing geeft.
2. Ontwerp en implementeer een algoritme met dynamisch programmeren dat het partitieprobleem oplost.

Opgave

Schrijf een Python-functie partitioneer(rij:list, k:int) die dit probleem oplost met dynamisch programmeren. Deze functie krijgt een rij aan gewichten binnen en een getal \(k\) dat aangeeft in hoeveel delen de rij gesplitst moet worden.

Voorbeelden

>>> partitioneer([100,200,300,200,100,400,200],3)
[[100, 200], [300, 200, 100], [400, 200]]