Angesichts einer Liste von Bewertungen von Spielern muss ich die Spieler (dh Bewertungen) so fair wie möglich in zwei Gruppen aufteilen. Ziel ist es, den Unterschied zwischen der kumulierten Bewertung der Teams zu minimieren. Es gibt keine Einschränkungen, wie ich die Spieler in die Teams aufteilen kann (ein Team kann 2 Spieler haben und das andere Team kann 10 Spieler haben).
Zum Beispiel: [5, 6, 2, 10, 2, 3, 4]
sollte zurückkehren([6, 5, 3, 2], [10, 4, 2])
Ich würde gerne den Algorithmus kennen, um dieses Problem zu lösen. Bitte beachten Sie, dass ich an einem Online-Programmier-Einführungskurs teilnehme, daher wären einfache Algorithmen willkommen.
Ich verwende den folgenden Code, aber aus irgendeinem Grund sagt der Online-Codeprüfer, dass er falsch ist.
def partition(ratings):
set1 = []
set2 =[]
sum_1 = 0
sum_2 = 0
for n in sorted(ratings, reverse=True):
if sum_1 < sum_2:
set1.append(n)
sum_1 = sum_1 + n
else:
set2.append(n)
sum_2 = sum_2 + n
return(set1, set2)
Update: Ich habe die Instruktoren kontaktiert und mir wurde gesagt, ich sollte eine andere "Hilfs" -Funktion innerhalb der Funktion definieren, um alle verschiedenen Kombinationen zu überprüfen, dann muss ich nach dem minimalen Unterschied suchen.
Antworten:
Hinweis: Bearbeitet, um den Fall besser zu behandeln, wenn die Summe aller Zahlen ungerade ist.
Backtracking ist eine Möglichkeit für dieses Problem.
Es ermöglicht die rekursive Prüfung aller Möglichkeiten, ohne dass viel Speicher benötigt wird.
Es stoppt, sobald eine optimale Lösung gefunden wurde:
sum = 0
Wosum
ist die Differenz zwischen der Summe der Elemente von Satz A und der Summe der Elemente von Satz B. BEARBEITEN: Es stoppt, sobaldsum < 2
der Fall behandelt wird, wenn die Summe aller Zahlen ist ungerade, dh entspricht einer minimalen Differenz von 1. Wenn diese globale Summe gerade ist, kann die minimale Differenz nicht gleich 1 sein.Es ermöglicht die Implementierung eines einfachen Verfahrens der vorzeitigen Aufgabe :
Wenn zu einem bestimmten Zeitpunkt
sum
die Summe aller verbleibenden Elemente (dh nicht in A oder B platziert) plus dem absoluten Wert des erhaltenen aktuellen Minimums höher ist, können wir die Prüfung aufgeben den aktuellen Pfad, ohne die verbleibenden Elemente zu untersuchen. Dieses Verfahren wird optimiert mit:Hier ist ein Pseudocode
Initialisierung:
a[]
sum_back[i] = sum_back[i+1] + a[i];
min_diff = sum_back[0];
a[0]
A -> ein. Der Indexi
des untersuchten Elements wird auf 1 gesetztup_down = true;
: Dieser Boolesche Wert gibt an, ob wir gerade vorwärts (wahr) oder rückwärts (falsch) gehen.While-Schleife:
If (up_down): vorwärts
sum_back
sum
entsprechend dieser Auswahl anif (i == n-1)
: LEAF -> Test, ob der optimale Wert verbessert wurde, und Rückgabe, wenn der neue Wert gleich 0 ist (EDIT :)if (... < 2)
; Gehe zurückIf (! Updown): rückwärts
i == 0
: zurücksum
Wert neuHier ist ein Code in C ++ (Entschuldigung, ich kenne Python nicht)
quelle
if I == 0
. Ich habe es getestet, indem ich in Ihrem Beispiel 10 durch 11 ersetzt habeIch denke, du solltest die nächste Übung alleine machen, sonst lernst du nicht viel. Hier ist eine Lösung, die versucht, den Rat Ihres Lehrers umzusetzen:
Ausgabe:
Beachten Sie, dass sich diese Ausgabe von der gewünschten unterscheidet, aber beide korrekt sind.
Dieser Algorithmus basiert auf der Tatsache, dass Sie zum Auswählen aller möglichen Teilmengen einer gegebenen Menge mit N Elementen alle ganzen Zahlen mit N Bits generieren und das I-te Element abhängig vom Wert des I-ten Bits auswählen können. Ich überlasse es Ihnen, ein paar Zeilen hinzuzufügen, um anzuhalten, sobald der
best_distance
Wert Null ist (weil es natürlich nicht besser werden kann).Bit für Bit (beachten Sie, dass dies
0b
das Präfix für eine Binärzahl in Python ist):Eine Binärzahl:
0b0111001 == 0·2⁶+1·2⁵+1·2⁴+1·2³+0·2²+0·2¹+1·2⁰ == 57
Rechts um 1 verschoben:
0b0111001 >> 1 == 0b011100 == 28
Links um 1 verschoben:
0b0111001 << 1 == 0b01110010 == 114
Rechts um 4 verschoben:
0b0111001 >> 4 == 0b011 == 3
Bitweise
&
(und):0b00110 & 0b10101 == 0b00100
So prüfen Sie, ob das 5. Bit (Index 4) 1 ist:
(0b0111001 >> 4) & 1 == 0b011 & 1 == 1
Eine Eins gefolgt von 7 Nullen:
1 << 7 == 0b10000000
7 Einsen:
(1 << 7) - 1 == 0b10000000 - 1 == 0b1111111
Alle 3-Bit - Kombinationen:
0b000==0
,0b001==1
,0b010==2
,0b011==3
,0b100==4
,0b101==5
,0b110==6
,0b111==7
(Hinweis :0b111 + 1 == 0b1000 == 1 << 3
)quelle
Der folgende Algorithmus macht das:
a
, ungerade in die Listeb
, um zu beginnena
undb
wenn die Änderung zum Besseren istIch habe Druckanweisungen hinzugefügt, um den Fortschritt in Ihrer Beispielliste anzuzeigen:
Ausgabe:
quelle
Da ich weiß, dass ich alle möglichen Listen generieren muss, muss ich eine "Hilfs" -Funktion erstellen, um alle Möglichkeiten zu generieren. Danach überprüfe ich den minimalen Unterschied, und die Kombination von Listen mit diesem minimalen Unterschied ist die gewünschte Lösung.
Die Hilfsfunktion ist rekursiv und prüft auf alle Möglichkeiten von Listenkombinationen.
Beispiele:
r = [1, 2, 2, 3, 5, 4, 2, 4, 5, 5, 2]
Die optimale Partition wäre:([1, 2, 2, 3, 5, 4], [2, 4, 5, 5, 2])
mit einem Unterschied von1
.r = [73, 7, 44, 21, 43, 42, 92, 88, 82, 70]
wäre die optimale Partition:([73, 7, 21, 92, 88], [44, 43, 42, 82, 70])
mit einem Unterschied von0
.quelle
Hier ist ein ziemlich ausführliches Beispiel, das eher für Bildungszwecke als für Aufführungszwecke gedacht ist. Es werden einige interessante Python-Konzepte wie Listenverständnis und Generatoren sowie ein gutes Beispiel für eine Rekursion vorgestellt, bei der Randfälle angemessen überprüft werden müssen. Erweiterungen, zB nur Teams mit gleicher Anzahl von Spielern, sind in den entsprechenden Einzelfunktionen einfach zu implementieren.
Ausgabe:
quelle
Wenn Sie sogar Teams wollen, kennen Sie die Zielpunktzahl der Bewertungen jedes Teams. Dies ist die Summe der Bewertungen geteilt durch 2.
Der folgende Code sollte also tun, was Sie wollen.
Ausgabe
Es gibt andere Splits, die die gleichen haben, die
fairness
alle im Tupel strong_ratings verfügbar sind. Ich schaue mir nur den ersten an, da dieser für jede Bewertungsliste, die Sie übergeben (vorausgesetztlen(ratings) > 1
), immer vorhanden ist .quelle
Eine gierige Lösung kann zu einer suboptimalen Lösung führen. Hier ist eine ziemlich einfache gierige Lösung. Die Idee ist, die Liste in absteigender Reihenfolge zu sortieren, um den Effekt des Hinzufügens von Bewertungen im Bucket zu verringern. Die Bewertung wird dem Eimer hinzugefügt, dessen Gesamtbewertungssumme geringer ist
Ausgabe :
Bearbeiten:
Ein anderer Ansatz besteht darin, alle möglichen Teilmengen der Liste zu generieren. Angenommen, Sie haben l1, eine der Teilmengen der Liste, dann können Sie die Liste l2 leicht so abrufen, dass l2 = Liste (Original) - l1. Die Nummer aller möglichen Teilmengen der Liste der Größe n ist 2 ^ n. Wir können sie als Folge einer ganzen Zahl von 0 bis 2 ^ n -1 bezeichnen. Nehmen Sie ein Beispiel, sagen Sie, Sie haben list = [1, 3, 5], dann ist keine der möglichen Kombinationen 2 ^ 3, dh 8. Jetzt können wir alle Kombinationen wie folgt schreiben:
Lösung:
Ausgabe :
quelle