Algorithmus für konkretes Problem gesucht

[EmaNymton]

Ich habe ein algorithmisches Problem, bei dem ich Hilfe benötige.

Hintergrund: Ich nehme an einem privaten Fußballmanagerspiel teil, dass auf die Daten von kicker.de zurückgreift und die Spieler nach einem festgelegten Punktesystem bewertet. Da unser Spielleiter das alles per Hand auswertet, habe ich mir zu Kontroll- und Übungszwecken ein Skript geschrieben, dass die Spielerseiten automatisiert ausliest und die Gesamtpunktzahl berechnet. Soweit funktioniert das auch alles. Jeder Kader besteht aus 28 Spielern, von denen am Spieltag aber nur 14 (11+ 3 Ersatz) eingesetzt werden können.
Nun wollte ich ein nettes Gimmick hinzufügen und am Ende jedes Spieltages eine optimal Aufstellung bestimmen, d.h. wie viele Punkte hätte jeder Spieler erreichen können, wenn er die beste Aufstellung aus seinen 28 Spielern gewählt hätte.

Es gibt folgende Bedingungen, die bei einer Aufstellung erfüllt sein müssen:

• Man darf aus einem Verein maximal 3 Spieler aufstellen
• Es gibt folgende Minimalbesetzung der einzelnen Positionen: 'Torwart':1,'Abwehr':3,'Mittelfeld':3,'Sturm':2
• Es gibt folgende Maximalbesetzung der einzelnen Positionen:'Torwart':1,'Abwehr':5,'Mittelfeld':5,'Sturm':3

Ich habe bisher folgenden zwei Ansätze verfolgt, die allerdings nicht immer die optimale Aufstellung lieferen:

1) Zunächst werden alle Spieler bestimmt, die eingesetzt wurden und die Positionen mit der Mindestanzahl besetzt. Dabei wird bei jeder Position nach den Spielern mit der maximalen Punktzahl gesucht und diese dann in die optimale Elf gesetzt. Die letzten zwei Spieler werden dann unter der Berücksichtigung der Regeln aus dem verbleibenden Rest ausgewählt.
Problem bei dieser Methode: Ich muss mit einer Position anfangen. Im Extremfall habe ich drei Mittelfeldspieler eines Vereins mit hoher Punktzahl, aber einen Abwehrspieler desselben Vereins mit einer noch höheren. Dieser würde aber nicht mehr ausgewählt, weil bei den Mittelfeldspielern ja schon drei Spieler eines Vereins gewählt wurden.

2) Hier habe ich die Spieler nicht nach Positionen getrennt und wähle jeweils immer den Spieler mit der höchsten Punktzahl aus, prüfe, ob die Bedingung der Maximalbesetzung sowie 3 Spieler eines Vereins noch nicht erfüllt sind und setzte ihn in meine optimale Elf. Problem bei der Sache ist, dass ich nicht sicherstellen kann, dass die Minimalbesetzung erfüllt ist, d.h. es kann z.B. passieren, dass ich einen optimale Mannschaft mit 5 Abwehr-, 5 Mittelfeldspielern und einem Torwart habe, aber keinen Stürmer.

Ich hoffe, ich habe mich verständlich ausgedrückt. Ich denke jetzt schon ein wenig über das Problem nach und habe im Moment irgendwie ein Brett vor dem Kopf bzw. keine Idee, wie ich beide Ansätze verknüpfen kann. Vielleicht hat jemand von euch ja noch eine Idee oder einen Hinweis?

Gruß EmaNymton

[Hyperion]

Ich kapiere Eure Minimal- und Maximalbesetzungen nicht! Die Anzahl der Spieler ist da ja unterschiedlich.

Sehe ich das richtig, dass die beiden Summen über die Spielerwerte den Vergleichswert für zwei Zusammenstellungen sind? Dabei ist die größere Summe besser?

Wenn dem so ist, denke ich, dass Dein zweiter Ansatz schon ganz gut klingt. Ich würde so vorgehen:

Da Deine Punktewerte der Spieler eine totale Ordnung bilden, kannst Du die Spielerliste absteigend sortieren. Dann gehst Du sie der Reihe nach durch und fügst den aktuellen Spieler in seine Kategorie in das "Portfolio" ein, sofern das Maximum in dieser Kategorie noch nicht erreicht wurde.

Code: Alles auswählen

positions = {
    "T": 1,
    "A": 5,
    "M": 5,
    "S": 2
}
portfolio = defaultdict(list)
# players sortierte Liste der Spieler
for player in players:
    if len(portfolio[player.position]) < positions[player.position]:
        portfolio[player.position].append(player)

Mein Ansatz geht davon aus, dass es prinzipiell genügend Spieler gibt, um die minimale Konfiguration zu erfüllen.

[EmaNymton]

Ich kapiere Eure Minimal- und Maximalbesetzungen nicht! Die Anzahl der Spieler ist da ja unterschiedlich.

Ja, die sagen nur aus, wieviele Spieler man auf einer Position einsetzen muss bzw. maximal kann. Du kannst also z.b. ein 1-3-5-2 spielen, aber eben kein 1-5-4-1, da eben minimal zwei Stürmer eingesetzt werden müssen, aber eben maximal nur 3 eingesetzt werden dürfen.

Damit habe ich genau das Problem, was den zweiten Ansatz unvollständig macht. Ich kann nicht ausschließen, dass ich z.B. eben das oben beschriebene 1-5-4-1 erhalte, da ich ja nur auf die maximale Anzahl prüfe.

[Hyperion]

Ich kapiere Eure Minimal- und Maximalbesetzungen nicht! Die Anzahl der Spieler ist da ja unterschiedlich.

Ja, die sagen nur aus, wieviele Spieler man auf einer Position einsetzen muss bzw. maximal kann. Du kannst also z.b. ein 1-3-5-2 spielen, aber eben kein 1-5-4-1, da eben minimal zwei Stürmer eingesetzt werden müssen, aber eben maximal nur 3 eingesetzt werden dürfen.

Ok, ich dachte beim Fußball müssten es immer 11 Spieler sein

Damit habe ich genau das Problem, was den zweiten Ansatz unvollständig macht. Ich kann nicht ausschließen, dass ich z.B. eben das oben beschriebene 1-5-4-1 erhalte, da ich ja nur auf die maximale Anzahl prüfe.

Bei meinem Ansatz hast Du das nicht, da jeder Spieler berücksichtigt wird. Wenn in Deinem Kader eben nicht genügend Spieler für die minimale Konfiguration vorhanden sind, kannst Du Diese eben nicht erreichen. Das ist aber ja kein Problem des Algorithmus, sondern einer mangelden Voraussetzung.

[EmaNymton]

Bei meinem Ansatz hast Du das nicht, da jeder Spieler berücksichtigt wird. Wenn in Deinem Kader eben nicht genügend Spieler für die minimale Konfiguration vorhanden sind, kannst Du Diese eben nicht erreichen. Das ist aber ja kein Problem des Algorithmus, sondern einer mangelden Voraussetzung.

Ich kann aber genügend Spieler haben und bekomme trotzdem die Mindestbesetzung nicht hin:
Angenommen players ist eine nach Punkten absteigende Liste (A für Abwehr und M für Mittelfeld, T für Tor) und sieht in einem Fall so aus
[A1,A2,A3,A4,A5,M1,M2,M3,M4,M5,T1,....]

Dann würde doch dein Algorithmus mir ein 1-5-5-0 liefern, d.h. ich kann nicht sicherstellen, dass ich mindestens 2 Stürmer habe.

Aber du hast mich auf eine Idee gebracht 1 und 2 zu kombinieren: Es würde doch funktionieren, Spieler erstmal solange in das "portfolio" zu packen, bis die Minimalbesetzung erfüllt ist und Spieler, die über der Minimalbesetzung liegen in einer Liste "zu parken", die dann abgearbeitet wird, wenn die Minimalbesetzung erreicht wurde.
Das sollte doch gehen, oder mache ich hier einen Denkfehler?

[Hyperion]

Ich kann aber genügend Spieler haben und bekomme trotzdem die Mindestbesetzung nicht hin:
Angenommen players ist eine nach Punkten absteigende Liste (A für Abwehr und M für Mittelfeld, T für Tor) und sieht in einem Fall so aus
[A1,A2,A3,A4,A5,M1,M2,M3,M4,M5,T1,....]

Dann würde doch dein Algorithmus mir ein 1-5-5-0 liefern, d.h. ich kann nicht sicherstellen, dass ich mindestens 2 Stürmer habe.

Du machst da einen Denkfehler. Mein Algo würde die "..." ja weiter durchgehen bis zum Schluss. Wenn da nun keine zwei Stürmer drin auftreten, so ist doch mit der Ursprungsmenge gar keine gültige Lösung zu erzielen - egal welchen Algo ich verwende!

[EmaNymton]

Sie treten ja darin auf, aber dann wäre es ein 1-5-5-2, was mehr als 11 Spieler bedeuten würde

[Hyperion]

Sie treten ja darin auf, aber dann wäre es ein 1-5-5-2, was mehr als 11 Spieler bedeuten würde

Ich hatte diesbezüglich ja nachgefragt Das ist also ein wichtiges Constraint, dass die Summe der Spieler immer 11 am Schluss sein muss!

Ok, also Deine Idee ist dann wohl sinnvoll. Erstmal die Minimalbesetzung voll machen und während des Durchlaufs die nicht mehr aufnehmbaren Spieler in einer neuen Liste merken (die dann bereits richtig sortiert ist). In einem zweiten Durchlauf gehst Du dann diese neue Liste durch und füllst entsprechend der Maximalbesetzung auf und brichst die Schleife ab, sofern Du schon 11 Spieler verteilt hast.

[BlackJack]

Ähm, vielleicht eine dumme Frage, aber die Liste da sieht jetzt so aus, als wenn die Spielposition schon fest an den Spieler gebunden ist, man also keinen Torwart im Mittelfeld einsetzen kann, oder keinen aus dem Mittelfeld zum Stürmer machen kann!? Dann kann man die einzelnen Bereiche doch sowieso erst einmal getrennt betrachten, eben nur mit den Spielern, die für die Positionen überhaupt in Frage kommen!?

Ansonsten hätte ich wohl erst einmal versucht ob man da ausreichend schnell mit einem (fast) „brute force”—Ansatz zu einer Lösung kommt. Also alles durchprobieren, ausser halt Teilbelegungen die eine Regel verletzen nicht weiter verfolgen („branch and bound”).

[EmaNymton]

@Hyperion: Sorry, hatte ich wohl überlesen.
Ich probiere mich jetzt mal an dem Ansatz.

@BlackJack: Da kommt aber die Regel in die Quere, dass ich maximal 3 Spieler aus einem Verein aufstellen darf. Man muss ja mit einer Position anfangen und da kann es passieren, das in dieser Position drei Spieler eines Vereins gewählt werden, in einer anderen Position aber ein Spieler aus dem selben Verein mehr Punkte gemacht hat. Man hätte also nicht die optimale Aufstellungen bekommen.

[Hyperion]

@BlackJack: Da kommt aber die Regel in die Quere, dass ich maximal 3 Spieler aus einem Verein aufstellen darf. Man muss ja mit einer Position anfangen und da kann es passieren, das in dieser Position drei Spieler eines Vereins gewählt werden, in einer anderen Position aber ein Spieler aus dem selben Verein mehr Punkte gemacht hat. Man hätte also nicht die optimale Aufstellungen bekommen.

Ok, also noch ein Constraint

Damit wird alles ungleich schwieriger, da Du hier - analog zum TSP - durchaus bewusst einen Spieler mit einem schlechtem Wert auswählen müßtest, damit Du einen anderen mit Top-Wert aufnehmen kannst.

Ansonsten hätte BlackJack recht und man könnte 4 Listen, aufgeteilt in Positionen, entsprechend sortiert anlegen. Die ersten x-Spieler sind dann die Minimalkonfiguration. Den Rest fügt man eben so ein, wie ich es oben beschrieben habe.

Mit dem neuen Constraint fällt es mir schwer, das ganze auf ein bekanntes Problem der Informatik zurückzuführen. Solche Anzahl-Constraints erinnern an lineare Optimierung und dann das Simplexverfahren. Allerdings sehe ich hier keine "Variablen" für die Zielfunktion.

[EmaNymton]

Ok, also noch ein Constraint

Das wurde aber in meinem Eingangspost erwähnt

Komme ich denn dann mit meinem letzten Vorschlag auch nicht hin?

Ich wähle doch die Spieler bei der Minimalbesetzung nur nach Punkten aus und fülle dann am Schluss bis zur Maximalbesetzung und unter Berücksichtigung des Vereins auf.

Vielleicht läufts doch auf ein Brute Force hinaus

[EyDu]

Hallo.

Ich würde auch sagen, dass hier alles auf einen Brute-Force-Ansatz hinaus läuft. Ich würde das Problem einfach anders herum angehen: Ich würde mir zunächst die beste Manschaft generieren, die ich mit meinen Spielern erstellen kann. Wähle den besten Torwart, wähle die a besten Abwehrspieler, die m besten Mittelfeldspieler und die s besten Stürmer. a, m, s und die Anzahl des Torwarts sind durch deine Bedingungen gegeben. Jetzt prüfst du auf Konflikte und schmeißt den am schlechtesten bewerteten Spieler aus dem Kader und ersetzt ihn durch einen anderen der keinen Konflikt auslöst.

Die Auswahl des neuen Spielers ist natürlich ein wenig kritisch und es lassen sich mit Sicherheit Konflikte generieren, welche nicht auflösbar sind. Ob diese in der Praxis auftauchen muss man sehen. Ansonsten kann man randomisiert Spieler tauschen. Das alles garantiert natürlich nicht, dass der Algorithmus determiniert, vielleicht reicht es für dich in der Praxis aber schon aus.

Oder noch einmal aus der anderen Richtung: Füge immer den besten Spieler ein welcher keinen Konflikt verursacht. Hier ergeben sich natürlich die selben Probleme wie oben, aber es müsste einfach getestet werden.

Ich möchte auch Behaupten, dass die so erzeugten Lösungen relativ gut sein könnten. Das könntest du entweder ausrechnen oder mit einer "perfekten" Lösung für Einzelfälle testen.

Sebastian

[BlackJack]

@EyDu: Laut Ausgangsbeitrag wird die optimale Besetzung gesucht, also denke ich dass man mit Auswahl der Besten für eine Position oder zufälliges Einsetzen nicht weit kommt. Denn wie Hyperion anmerkte kann es sein, dass man irgendwo einen „Schlechteren” hinsetzen muss, damit man an anderer Stelle zwei (oder mehr) setzen kann, die den mehr als wieder aufwiegen. Solange man nicht alle Möglichkeiten durchprobiert hat, weiss man nicht sicher ob es nicht noch eine bessere Variante als die bisher gefundene(n) gibt.

[Hyperion]

Hui... Bruteforce bei der Anzahl an Fällen und Bedingungen? Das könnte schon unberechenbar sein...

[BlackJack]

@Hyperion: Denke ich nicht. Die Bedingungen schränken doch recht gut ein, so dass man viele Wege in dem Baum gar nicht weiterverfolgen muss.

[EyDu]

@BlackJack: Natürlich liefert mein Ansatz keinen optimalen Wert, aber je nach Anzahl der möglichen Spieler kann das finden einer optimalen Mannschaft, nach grobem Überschlag, relativ aufwändig sein. Da ich Bewertungen von Fußballspielen keine schlechten Eigenschaften ansehen kann (welche die gefundene Lösung unglaublich schlecht macht), scheint mir auf den ersten Blick eine Annäherung eine ausreichend gute Näherung zu liefern. Es hängt halt davon ab, was mit dem Resultat genau gemacht werden soll.

Ich würde vorher allerdings auch die perfekte Lösung ausprobieren, da sie einfach schnell zu implementieren ist. Mit geschickten Abschneiden von Ästen sieht die Sache, zumindest bei einer normalen Größe einer Fußballmannschaft, nicht mehr so dramatisch aus.

[BlackJack]

@EyDu: Ja, es kommt auf den Einsatzzweck an. Bei der Beschreibung würde ich aber tatsächlich erwarten, dass das Optimum gesucht ist, damit man zum Beispiel den Mitspielern sagen kann wie weit ihre Mannschaftsaufstellung vom Ideal entfernt war.

[EmaNymton]

Erstmal danke für die vielen Vorschläge und die Diskussion. Ich habe gestern nochmal meinen letzten Ansatz versucht und denke, dass er die optimale Aufstellung findet, ohne eine der Bedingungen zu verletzen. Ich hätte allerdings gerne nochmal eure Meinung dazu gehört:

• Finde alle Spieler die gespielt haben und schreibe sie in eine Liste.
• Wähle jeweils den Spieler der Liste mit der höchsten Punktzahl aus und schreibe ihn in eine Liste "besteElf". Wenn bei einer Position die Minimalanzahl der Besetzung erreicht ist oder schon 3 Spieler aus dem selben Verein in besteElf sind, schreibe den Spieler in eine Liste "bank".
• Wenn die beste Elf noch nicht aus 9 Spielern besteht (kann passieren, wenn für eine Position z.B. nicht genügend Spieler zur Verfügung standen), fülle die jeweilige Position mit Dummys auf (Punkte sind dann laut Regel -25), alternativ kann man auch einen Spieler nehmen, der nicht gespielt hat.
• Wähle jeweils den Spieler von der "bank" mit der höchsten Punktzahl aus und schreibe ihn in die "besteElf". Wenn bei einer Position die Maximalanzahl der Besetzung erreicht ist oder schon 3 Spieler aus dem selben Verein in besteElf sind, ignoriere den Spieler.

Damit sollte ich doch sowohl immer die drei besten Spieler aus einem Verein erhalten, als auch meine Besetzungsregeln (minimal/maximal) erfüllen, oder?

Ich hab mal zwei Beispiele vom letzten Spieltag angefügt, um das nochmal zu verdeutlichen:

Code: Alles auswählen

eingesetzte Spieler:
('Neuer', 'Torwart', 63, 'Bayern M\xc3\xbcnchen')
('Barth', 'Abwehr', -28, 'SC Freiburg')
('H\xc3\xb6wedes', 'Abwehr', 35, 'FC Schalke 04')
('Bender', 'Mittelfeld', -4, 'Borussia Dortmund')
('Ribery', 'Mittelfeld', 52, 'Bayern M\xc3\xbcnchen')
('Usami', 'Mittelfeld', 11, 'Bayern M\xc3\xbcnchen')
('Tiffert', 'Mittelfeld', -1, '1. FC Kaiserslautern')
('Traore', 'Mittelfeld', -12, 'VfB Stuttgart')
('Ochs', 'Mittelfeld', -40, 'VfL Wolfsburg')
('Kie\xc3\x9fling', 'Sturm', -5, 'Bayer Leverkusen')
('Eigler', 'Sturm', -20, '1. FC N\xc3\xbcrnberg')
('Dembel\xc3\xa9', 'Sturm', -40, 'SC Freiburg')
('Huntelaar', 'Sturm', 180, 'FC Schalke 04')
('Torun', 'Sturm', 77, 'Hertha BSC')
ersten 9 Spieler:
('Huntelaar', 'Sturm', 180, 'FC Schalke 04')
('Torun', 'Sturm', 77, 'Hertha BSC')
('Neuer', 'Torwart', 63, 'Bayern M\xc3\xbcnchen')
('Ribery', 'Mittelfeld', 52, 'Bayern M\xc3\xbcnchen')
('H\xc3\xb6wedes', 'Abwehr', 35, 'FC Schalke 04')
('Usami', 'Mittelfeld', 11, 'Bayern M\xc3\xbcnchen')
('Tiffert', 'Mittelfeld', -1, '1. FC Kaiserslautern')
('Barth', 'Abwehr', -28, 'SC Freiburg')
Bankspieler:
('Bender', 'Mittelfeld', -4, 'Borussia Dortmund')
('Kie\xc3\x9fling', 'Sturm', -5, 'Bayer Leverkusen')
('Traore', 'Mittelfeld', -12, 'VfB Stuttgart')
('Eigler', 'Sturm', -20, '1. FC N\xc3\xbcrnberg')
('Ochs', 'Mittelfeld', -40, 'VfL Wolfsburg')
('Dembel\xc3\xa9', 'Sturm', -40, 'SC Freiburg')

--------------------------
Beste Elf von X am 2. Spieltag:
Torwart:
  Neuer 		63 	Bayern München
Abwehr:
  Höwedes 	35 	FC Schalke 04
  Barth 		-28 	SC Freiburg
  Dummy 		-25 	Dummy
Mittelfeld:
  Ribery 		52 	Bayern München
  Usami 		11 	Bayern München
  Tiffert 		-1 	1. FC Kaiserslautern
  Bender 		-4 	Borussia Dortmund
Sturm:
  Huntelaar 	180 	FC Schalke 04
  Torun 		77 	Hertha BSC
  Kießling 		-5 	Bayer Leverkusen

Aufstellung im: 1 3 4 3

14 Spieler von 28 möglichen haben gespielt.

Bestmögliche Ausbeute am Spieltag: 355

Code: Alles auswählen

eingesetzte Spieler:
('Starke', 'Torwart', 94, '1899 Hoffenheim')
('Benaglio', 'Torwart', -26, 'VfL Wolfsburg')
('Reinartz', 'Abwehr', 48, 'Bayer Leverkusen')
('Boateng', 'Abwehr', 45, 'Bayern M\xc3\xbcnchen')
('Westermann', 'Abwehr', -2, 'Hamburger SV')
('Vorsah', 'Abwehr', 48, '1899 Hoffenheim')
('Tasci', 'Abwehr', 46, 'VfB Stuttgart')
('Lell', 'Abwehr', 24, 'Hertha BSC')
('Bellinghausen', 'Abwehr', 10, 'FC Augsburg')
('M\xc3\xbcller', 'Mittelfeld', -1, 'Bayern M\xc3\xbcnchen')
('Rudy', 'Mittelfeld', 71, '1899 Hoffenheim')
('Ekici', 'Mittelfeld', -29, 'Werder Bremen')
('Draxler', 'Mittelfeld', 37, 'FC Schalke 04')
('Dejagah', 'Mittelfeld', -48, 'VfL Wolfsburg')
('Salihamidzic', 'Mittelfeld', -50, 'VfL Wolfsburg')
('Ndjeng', 'Mittelfeld', 6, 'FC Augsburg')
('Gomez', 'Sturm', -2, 'Bayern M\xc3\xbcnchen')
('Podolski', 'Sturm', -1, '1. FC K\xc3\xb6ln')
('Obasi', 'Sturm', 20, '1899 Hoffenheim')
('Gogia', 'Mittelfeld', -15, 'FC Augsburg')
ersten 9 Spieler:
('Starke', 'Torwart', 94, '1899 Hoffenheim')
('Rudy', 'Mittelfeld', 71, '1899 Hoffenheim')
('Reinartz', 'Abwehr', 48, 'Bayer Leverkusen')
('Vorsah', 'Abwehr', 48, '1899 Hoffenheim')
('Tasci', 'Abwehr', 46, 'VfB Stuttgart')
('Draxler', 'Mittelfeld', 37, 'FC Schalke 04')
('Ndjeng', 'Mittelfeld', 6, 'FC Augsburg')
('Podolski', 'Sturm', -1, '1. FC K\xc3\xb6ln')
('Gomez', 'Sturm', -2, 'Bayern M\xc3\xbcnchen')
Bankspieler:
('Boateng', 'Abwehr', 45, 'Bayern M\xc3\xbcnchen')
('Lell', 'Abwehr', 24, 'Hertha BSC')
('Obasi', 'Sturm', 20, '1899 Hoffenheim')
('Bellinghausen', 'Abwehr', 10, 'FC Augsburg')
('M\xc3\xbcller', 'Mittelfeld', -1, 'Bayern M\xc3\xbcnchen')
('Westermann', 'Abwehr', -2, 'Hamburger SV')
('Gogia', 'Mittelfeld', -15, 'FC Augsburg')
('Benaglio', 'Torwart', -26, 'VfL Wolfsburg')
('Ekici', 'Mittelfeld', -29, 'Werder Bremen')
('Dejagah', 'Mittelfeld', -48, 'VfL Wolfsburg')
('Salihamidzic', 'Mittelfeld', -50, 'VfL Wolfsburg')
--------------------------
Beste Elf von XX am 2. Spieltag:
Torwart:
  Starke 		94 	1899 Hoffenheim
Abwehr:
  Reinartz 		48 	Bayer Leverkusen
  Vorsah 		48 	1899 Hoffenheim
  Tasci 		46 	VfB Stuttgart
  Boateng 		45 	Bayern München
  Lell 		24 	Hertha BSC
Mittelfeld:
  Rudy 		71 	1899 Hoffenheim
  Draxler 		37 	FC Schalke 04
  Ndjeng 		6 	FC Augsburg
Sturm:
  Podolski 		-1 	1. FC Köln
  Gomez 		-2 	Bayern München

Aufstellung im: 1 5 3 2

20 Spieler von 28 möglichen haben gespielt.

Bestmögliche Ausbeute am Spieltag: 416

Ich kann jetzt auch noch den Ansatz verfolgen, in dem ich alle Möglichkeiten durchprobiere, und beide laufen lassen aber ich bin der Meinung, dass ich damit schon meine optimale Aufstellung gefunden habe. Irgendwo ein Denkfehler/Sonderfall vergessen?

[BlackJack]

@EmaNymton: Du hast hier jetzt anscheinend wieder die Bedingung höchstens x Spieler von einem Verein nicht mehr erwähnt. Da könnte es wie schon gesagt zu Situationen kommen, bei denen man nicht ums durchprobieren der Kombinationen herum kommt, um die optimale Besetzung zu finden.

Edit: Okay, Du hast die Bedingung erwähnt. Sollte aber am Problem nichts ändern.

Edit2: Wieso Spieler die aus einem Verein kommen der schon x-mal vertreten ist, eigentlich noch auf die Bank setzen? Im letzten Schritt werden die dann ja wieder explizit ignoriert.