Das läuft denk ich auf das Rucksackproblem hinaus. Die Level sind die Gewichte und die Teams sind 2 Rucksäcke mit Fassungsvermögen N/2 (Summe aller Gewichte ist N). Den einen Rucksack musst du dann möglichst voll kriegen.

Da gibts glaub ich nen Algorithmus der auf jeden Fall schneller ist als durchprobieren.

€: Denke es ist doch ein bisschen komplizierter weil die Spieler anzahl ja auch ausgewogen sein muss.

Mit durchprobieren wären es N über N/2 Möglichkeiten, also N!/((N/2)!^2).

Früher auffm Bolzplatz gabs immer 2 Mannschafts-Führer, und die haben abwechselnd immer einen Spielwilligen aussuchen dürfen für ihre Mannschaft.
Ein genialer Algo, und könnte man bestimmt auch noch verfeinern

@ErfinderDesRades:: Jou, kenn ich auch noch.
@faxe1008:: Mach Dir 2 Arrays, eins mit Namen, eins mit Level, sortiere beide nach dem Level
(Array.Sort(arrLevel, arrName)) und verteile die Spieler abwechselnd.
Da hast Du zumindest eine belastbare Vor-Auswahl.
Nun kannst Du ja einzelne Spieler tauschen, wenn ihre Differenz nahe bei der Gesamtdifferenz liegt.

Ich würde ähnlich vorgehen, wie es EDR gesagt hat:
1.: Spieler nach Level absteigend sortieren
2.: Spieler nach folgendem Pattern verteilen: 1221122... (so kriegt Team 1 die Nummern 1, 4, 5, 8, 9, ... und Team 2 die Nummern 2, 3, 6, 7, 10, ...)
Hier noch ein kleiner Vergleich zwischen immer abwechselnd und meinem Ansatz:

Sagen wir, wir haben Spieler mit den Stärken 10, 9, 8, 7, 6, 5, 4, 3, 2, 1.
Machen wir nun immer abwechselnd ergibt sich folgendes:
Team 1: 10, 8, 6, 4, 2 => 30
Team 2: 9, 7, 5, 3, 1 => 25
Nehmen wir meine Methode, sieht es so aus:
Team 1: 10, 7, 6, 3, 2 => 28
Team 2: 9, 8, 5, 4, 1 => 27

Da aber die Verteilung nicht immer so gleichmäßig ist, wie in meinem Beispiel, sollte man erwägen, was besser passt.

Also ich würds so machen:

Auch erstmal alle absteigend sortieren, dannach alle nacheinander Team A zuweisen, bis das Team A den geringsten Wert Modulo 50% des Totallevels (alle Levels zusammenaddiert) hat und den Rest dann Team B zuweisen.

Beispiel:

Es sind 10 Spieler da mit jeweils folgendem Level: 1,6,2,7,2,8,3,9,14,4

erstmal absteigend sortieren -> 1,2,2,3,4,6,7,8,9,14

Anschliessend alles zusammenrechnen: 1+2+2+3+4+6+7+8+9+14 = 56
Die Hälfte ist 28, also weis ich Team A solange Spieler zu bis dessen Level zusammen Modulo 28 am geringsten ist

1+2+2+3+4+6+7+8+9+14 % 28 = 28
1+2+2+3+4+6+7+8+9 % 28 = 14
1+2+2+3+4+6+7+8 % 28 = 5
1+2+2+3+4+6+7 % 28 = 3 'Das hier ist Team A, rest ist Team B
1+2+2+3+4+6 % 28 = 10
1+2+2+3+4 % 28 = 16
1+2+2+3 % 28 = 20
1+2+2 % 28 = 23
1+2 % 28 = 25
1 % 28 = 27

Jo, mir scheinen alle gleicher Ansicht: Nach Spielstärke sortieren, und dann abwechselnd den Mannschaften zuordnen. nafets3646 hat da noch eine Variation, die vmtl. meist ausgewogenere Ergebnisse bringt als einfach abwechselnd zu teilen - aber halt nur meist.

Nun könnte man den 2. Schritt anschließen, nämlich das lustige Herum-Tauschen, was RFG vorschlägt. Und imo kann man sich da sehr verkünsteln, wenn man nicht nur Einzelspieler tauscht, sondern auch Spieler-Gruppen.
Da wäre also ein Algo zu coden, der pro Mannschaft alle möglichen Teilmengen permutiert, und deren Level-Summe vermerkt.

Alle möglichen Teilmengen - da gabs was inne Kombinatorik zu - glaub "Kombination ohne Beachtung der Reihenfolge" - glaub das wäre mit einer Fußballmannschaft noch machbar...

@RushDen:: Du hast glaub die Aufgabe abgewandelt, jdfs. wenn wir beim Bolzplatz bleiben, müssen beide Mannschaften gleiche Spieler-Anzahl haben.
Und es ließen sich in deim Beispiel auch perfekte Lösungen finden, etwa 6+8+14 = genau 28!

In der Aufgabenstellung hieß es ja nur, ihr Gesamt Level solle möglichst ausgewogen sein, nichts von gleicher Spieler-Anzahl.

Das muss @faxe1008: entscheiden - das Wörtlein "grade Anzahl" schien mir auf gleichgroße Mannschaften hinzudeuten.
Aber hast natürlich recht: Vlt. war es auch ich, der die Aufgabe geändert hat (eingeschränkt), mit meiner BoltzPlatz-Allegorie.

Ich finds ja interessant wie Leute hier Algorithmen entwerfen, die wahrscheinlich meistens ganz gute Lösungen bringen.
Meistens ganz gut kann auch katastrpohal daneben bedeuten. Es interessiert einen doch nur ein Algorithmus, der immer die beste Möglichkeit ausspuckt.

Wenn die Teams gleich viele Spieler haben sollen, dann wirds kompliziert wie ich oben schon geschrieben habe.

Diese Bedingung hat der Fragensteller aber nicht erwähnt (aber vermutlich gemeint). Somit wäre es das Rucksackproblem. Ein Gegenstand ist ein Spieler. Der Wert ist gleich dem Gewicht gleich dem Level. Man muss nun nur nen Rucksack der die Hälfte aller Gewichte fasst möglichst vollkriegen.

@ErfinderDesRades
Ich weiß nicht was dein 6+8+14 bedeutet.
Wenn man das ganze durch Durchprobieren lösen will und zwei Fussballmanschaften aufstellen will, dann gibts (22 über 11)/2 Möglichkeiten.
Begründung: Aus einem Pool von 22 unterscheidbaren Leuten gibt es 22 über 11 Möglichkeiten eine Menge von 11 Leuten zu bilden. Die übrigen Leute sind automatisch in der anderen Manschaft. Durch 2 musst du teilen, weil die beiden teams ja auch ununterscheidbar sind.

Beim Durchprobieren haste N!/((N/2)!)^2)/2 Möglichkeiten und damit ne verdammt schlechte Komplexitätsklasse.

Es gibt neben dem abwechselnd-wählen-Prinzip auf dem Bolzplatz noch die Methode, bei der ein Capitän 2 teams erstellt und der andere Capitän seine Mannschaft wählen darf.

Man könnte die Mitglieder auch nach der Stärke sortieren, und dann wird abwechselnd in das Team gewählt:


1, 2, 2, 2, 3, 4, 5, 6, 7, 8


Team1: 1, 2, 3, 5, 7,
Team2: 2, 2, 4, 6, 8,

Anstatt sich Beispiele zu überlegen, wo ein Algorithumus gut funktioniert, sollte man lieber versuchen Extremfälle zu suchen, in denen der Algorithmus total fehl schlägt.

So kann man zwar nicht beweisen, dass ein Algo fuktioniert (was im Allgemeinen ja recht schwierig ist), aber man sieht recht schnell ob er nicht funktioniert.

Natürlich, aber man kann bei der Spielerstärke kein absolutes Gleichgewicht schaffen. Mein Prinzip würde dem entsprechend, wie man früher Mannschaften gewählt hat - dies sollte so ziemlich das fairste sein.

markus.obi schrieb:

Ich weiß nicht was dein 6+8+14 bedeutet.

das bezieht sich auf post#7 - wenn du da guckst - Spielstärke 28 ist eine optimale Lösung für das dortige Beispiel

Beim Durchprobieren haste N!/((N/2)!)^2)/2 Möglichkeiten und damit ne verdammt schlechte Komplexitätsklasse.

Ich glaub, mein Ansatz des Durchprobierens ist wesentlich besser: Ich will ja nur alle möglichen Teilmengen einer (Fußball-)Mannschaft bilden: also alle 1er-Mengen(=11) + alle 2er-Mengen(=?viele, vermute ich) + alle 3er-Mengen + ... + alle 11er-Mengen(=1).

Ich glaub nicht, dass das eine Komplexität mit N! ist, aber weissen tu ichs nicht genau.

Edit:
also doch beliebige Mannschaftsstärken und Rucksack-Problem. Naja - da gugget halt bei Wiki...

Das Problem ist, dass die Stärke der Spieler i.A. nicht linear verteilt ist, deswegen kann man zunächst nur einen Startwurf machen und danach per gezieltem Tausch eine "Feinjustage" vornehmen.

Außerdem müsste man berücksichtigen, dass der Unterschied zwischen einem Level 10 und 11 größer sein kann als der zwischen einem Level 3 und 4.

nafets3646 schrieb:

zwischen einem Level 3 und 4.

Wenn man so anfängt, wird man nie fertig.
Die Differenzen sollten schon konstant sein.

Ich hab jetzt nochmal wiki geguckt: de.wikipedia.org/wiki/Abz%C3%A4hlende_Kombinatorik

Es ist durchaus leistbar, aus einer Menge von Mitspielern alle möglichen Teilmengen zu bilden.
Die Bildung aller möglichen Teilmengen mit festgelegter Mannschaftsstärke k berechnet sich als Kombination ohne Wiederholung ("Ziehen aus dem Sack, ohne zurücklegen" - das ist genau eine Mannschafts-Bildung).
Für die Anzahl gilt also die Formel (s.Wiki): (n!/(n-k)!)/k!
zB bei 11 Spielern gibts k von 1 - 11, macht die Gesamtsumme 2047 (hab ich mit Excel ausgerechnet ;)) - das ist locker zu handeln.
20 Spieler schlagen schon mit 1048575 Möglichkeiten zu Buche, aber das kriegt man immer noch in den Griff

Man kann ja so sortieren, dass die Teilmengen, die dem Ziellevel am nächsten kommen, vorrangig behandelt werden.

Aus dem Rest bildet man wieder alle möglichen Teilmengen usw..

Das wäre ein Algo, der glaub recht effizient alle besten Lösungen findet, sowohl für variable Mannschaftsstärken als auch variabel viele Mannschaften.
Weil sobald eine nur zweitbeste Lösung gefunden ist, kann er ja abbrechen.

Dann wärs also doch kein Rucksack-Problem.