Kein Problem, aber ich muss dich enttäuschen, wenn du etwas anderes erwartest, als dass ihr es in 10 Minuten nicht auch hin bekommen hättet
Ich habe zunächst abgewägt, wie viele Möglichkeiten es gibt. Nach den bisherigen Spieltagen und Erfahrungen hat man es mit durchschnittlich 22 über 11 Möglichkeiten zu tun, so dass ich wirklich erst mal den dümmsten/einfachsten Ansatz gewählt habe, indem ich mir alle möglichen Mannschaften mit itertools.combinations generieren lasse und jede Möglichkeit auf die Regeln überprüfe. Hält sie den Regeln stand, werden die Punkte berechnet und mit der bisher besten Punktzahl verglichen.
Hier der Auszug:
Code: Alles auswählen
def besteMannschaft_bruteforce(sptag,mannschaft,mitspieler):
besetzung_min = {'Torwart':1,'Abwehr':3,'Mittelfeld':3,'Sturm':2}
positionen = {'Torwart':0,'Abwehr':0,'Mittelfeld':0,'Sturm':0}
besteElf = []
punkte = -10000
# generiert ein liste mit allen Spielern, die gespielt haben:
eingesetzteSpieler=[]
for spieler in mannschaft:
spieler = alleSpieler[spielerConvert[spieler[0]]]
if sptag in spieler.bewertungen:
eingesetzteSpieler.append((spieler.name,
spieler.position,
spieler.spieltagPunkte[sptag],
spieler.verein))
# wenn eine Mannschaft nicht die erforderliche Mindestbesetzung hat, wird sie mit Dummy aufgefüllt
positionen_start = {'Torwart':0,'Abwehr':0,'Mittelfeld':0,'Sturm':0}
for spieler in eingesetzteSpieler:
positionen_start[spieler[1]] += 1
for position in positionen_start:
while positionen_start[position] < besetzung_min[position]:
eingesetzteSpieler.append(('Dummy',position,-25,'Dummy'))
positionen_start[position]+=1
for elf in itertools.combinations(eingesetzteSpieler,11):
if mannschaft_ok(elf):
summe = sum(spieler[2] for spieler in elf)
if summe > punkte:
besteElf = elf
punkte = summe
.... [Ausgabe der Mannschaft auf der Konsole]
def mannschaft_ok(mannschaft):
besetzung_min = {'Torwart':1,'Abwehr':3,'Mittelfeld':3,'Sturm':2}
besetzung_max = {'Torwart':1,'Abwehr':5,'Mittelfeld':5,'Sturm':3}
vereine = {}
positionen = {'Torwart':0,'Abwehr':0,'Mittelfeld':0,'Sturm':0}
# zähle positionen und vereine
for name, position, punkte, verein in mannschaft:
if verein in vereine:
vereine[verein] += 1
else:
vereine[verein] = 1
positionen[position] += 1
# checke Positionen
for position in positionen:
anzahl_plaetze = range(besetzung_min[position],besetzung_max[position]+1)
if positionen[position] not in anzahl_plaetze:
return False
# checke Vereinanzahl
for anzahl_verein in vereine.values():
if anzahl_verein > 3:
return False
# Mannschaft ok
return True
Es wäre jetzt evtl. zu überlegen, wie man das optimieren könnte. Da wären eure Vorschläge mit einem Baum besser, dass ich beim Befüllen des Baumes überprüfe, ob die Mannschaft durch Hinzufügen eines Spielers überhaupt noch zulässig ist. Für mein spezielles Problem reicht mir die Geschwindigkeit aus, allerdings will ich eigentlich auch noch eine Elf des Tages generieren, also aus allen Mannschaften, die gespielt haben die beste Elf. Das wären dann im Maximal-Fall 252 (18 Mannschaften * 14 (11+3) Spieler) über 11 Möglichkeiten (5225395795223303700) und minimal 198 über 11 (346204947854027808).
Mal gucken, ob ich das hinkriege...
Edit: Hab gerade mal abeschätzt, wenn er 100000 Mannschaften pro Sekunde testen kann, benötigt reines BruteForce wohl ca. 1,6 Mio. Jahre Rechenzeit.
