Leuk Wiskundevraagstuk

[Martijn van Berkel]

Beste forumleden,

Ik heb een wiskundig vraagstuk en hopelijk kunnen jullie mij daar mee helpen.
Stel je hebt een lijst met spelers, team, positie en behaald aantal punten
Voorbeeld :
Pietje Pietersen – Fc Knudde 1 – Aanvaller - 30
Frank Franken – Fc Knudde 3 – Keeper – 29
Johan Janssen – Fc Knudde 4 – Middenvelder – 29
Bart vd Ven – Fc Knudde 3 – Middenvelder – 28
Hanneke Dekkers – Fc Knudde 5 – Verdediger – 26
Enz.
Nu wil ik op basis van bovenstaande lijst het “dreamteam” samenstellen. Het “dreamteam” is een team van 15 spelers ( 4 aanvallers, 4 middenvelders, 5 verdedigers en 2 keepers) waarmee je het hoogste aantal punten behaald zou hebben.
Dat zou mij nog wel lukken, maar er is één grote MAAR. De 15 spelers moeten evenredig verdeeld zijn over het aantal teams. Stel je hebt 10 teams (FC Knudde 1 t/m FC Knudde 10), dan moet je minimaal 1 speler per team selecteren en maximaal 2 spelers per team ( dus uit 5 teams 1 speler en uit 5 teams 2 spelers).

Wat is nu de werkwijze om het “dreamteam” te bepalen ?

Alvast bedankt voor jullie hulp!

Martijn van Berkel

[sarah222]

Ik weet niet of ik je vraag volledig juist heb begrepen, maar ik zou iets als volgt doen:

groepeer de spelers volgens hun type, en noteer deze gesorteerd in een tabel. E.g. : kolom 1 bevat alle middenvelders, kolom 2 bevat alle keepers, etc. In iedere kolom verwijderen we de slechtste spelers, zodat we juist voldoende mensen overhouden om de ploegen samen te stellen (de slechtste spelers zijn sowieso overbodig als we de beste ploegen willen hebben.)
Een samenstelling van een ploeg kunnen we voorstellen door de spelers in een bepaalde kolom te permuteren. In de laatste kolom maken we de som van alle spelers van 1 ploeg (de laatste kolom bevat dus 10 waarden als we 10 ploegen willen samenstellen). Een verdeling in een aantal ploegen is dus equivalent aan een bepaalde permutatie van de tabel.

Met een computer proberen we nu brute-force alle permutaties van de tabel uit (dit is jammer genoeg ), en bij iedere schikking houden we de absolute waarde van het verschil tussen de minimale en maximale waarde uit de laatste kolom bij. De permutatie die dit verschil zo laag mogelijk krijgt, vormt de beste verdeling om een zo evenredig mogelijke verdeling in ploegen te hebben.