Auf der Suche nach einem cleveren Weg, um eine Reihe von Daten zu sortieren

Question

Ich habe eine Gruppe von 80 Studenten und ich muss sie in 20 Gruppen von 4 sortieren. Ich habe ihre früheren Prüfungsergebnisse von einem vorausgesetzten Modul und ich möchte sicherstellen, dass Der Durchschnitt der Ergebnisse der sortierten Gruppenmitglieder liegt so nahe wie möglich am Gesamtdurchschnitt der vorherigen Prüfungsnoten.

Sorry, wenn das nicht besonders klar ist.

Hier ist eine Momentaufnahme des Problems:

Student Score 
AA   50 
AB   45 
AC   80 
AD   70 
AE   45 
AF   55 
AG   65 
AH   90 

So ist der Durchschnitt der hier Partituren 62,5. Wie würde ich am besten diese acht Schüler in zwei Vierergruppen sortieren, so dass für beide Gruppen der Durchschnitt ihrer kombinierten Prüfungsnoten so nahe wie möglich bei 62,5 liegt.

Mein Problem ist genau das, aber mit 80 Datenpunkten (20 Gruppen) statt 8 (2 Gruppen).

Je mehr ich über dieses Problem nachdenke, desto schwieriger scheint es.

Hat jemand irgendwelche Ideen?

Dank

Answer 1

zuerst sortieren die goup nach Punkten. So wird es:

AH 90 
AC 80 
..... 
AB 45 
AE 45 

Dann starten combinning die erste mit dem letzten:

(AE, AH, 67.5) 
(AB, AC, 62.5) 
(AD, AA, 60) 
(AG, AF, 60) 

Und so weiter in dem anderen Fall werden Sie die beiden von zwei kombinieren. Die ersten beiden mit den letzten zwei.

Ein anderer Weg:

1. Find all the possible groups by 4 students. 
2. Then for every combination of groups find the abs deviation from the average score and SUM it up for the combination of groups. 
3. Choose the combination of groups with the lowest sum. 

Answer 2

Anfangs dachte ich über die Oben-Unten-Spiel-Option. jedoch, wie John hervorgehoben hat, sind die Ergebnisse sicherlich nicht optimal:

Scores    Students       Avg. 
40 94 40 94  'AE' 'DA' 'AI' 'AR'  67 
40 90 40 88  'AK' 'CI' 'AM' 'BP'  64.5 
40 85 40 80  'AQ' 'AW' 'AT' 'BD'  61.25 
40 79 40 77  'AU' 'BC' 'AV' 'AB'  59 
40 76 40 75  'AX' 'CG' 'AZ' 'CQ'  57.75 
40 75 40 75  'BF' 'CB' 'BN' 'BQ'  57.5 
40 75 40 74  'BR' 'BI' 'CF' 'CZ'  57.25 
40 74 40 74  'CK' 'CO' 'CP' 'AL'  57 
40 72 41 71  'DB' 'CN' 'AG' 'BO'  56 
41 71 42 70  'CD' 'BM' 'AH' 'BS'  56 
42 70 42 69  'BG' 'BL' 'CU' 'CX'  55.75 
43 68 44 67  'BK' 'CY' 'AD' 'CE'  55.5 
44 64 44 64  'BJ' 'CR' 'BZ' 'BY'  54 
45 64 45 63  'BW' 'BV' 'CS' 'BE'  54.25 
45 62 47 60  'CV' 'CH' 'AC' 'CM'  53.5 
47 59 47 58  'BT' 'AY' 'CL' 'AP'  52.75 
47 57 48 57  'CT' 'BA' 'BX' 'AS'  52.25 
48 56 49 56  'CA' 'AJ' 'AN' 'AA'  52.25 
50 55 50 54  'BB' 'AF' 'CJ' 'AO'  52.25 
51 52 51 52  'CC' 'BU' 'CW' 'BH'  51.5 

Answer 3

Eine mögliche Lösung:

ich versuchen würde, mit einem Greedy-Algorithmus geht, die mit einem anderen Studenten durch Paarung jeden Schüler beginnt Das bringt Sie Ihrem Zieldurchschnitt am nächsten. Nach der anfänglichen Paarung sollten Sie dann in der Lage sein, aus den ersten Paaren mit dem gleichen Ansatz nachfolgende Paare zu bilden.

Nach der ersten Paarungsrunde nutzt dieser Ansatz den Durchschnitt zweier Durchschnittswerte und vergleicht diesen mit dem Zielmittel, um nachfolgende Gruppen zu erstellen. Sie können mehr über lesen, warum die here.

jedoch für dieses Problem umgehen wird,

Dies wird nicht unbedingt geben Ihnen die optimale Lösung, aber es ist eher eine heuristische Technik, um das Problem zu lösen. Ein bekanntes Beispiel unten ist, wenn ein niedriger Wert um drei hohe Werte versetzt werden muss, um den Zielmittelwert zu erreichen. Diese Arten von Gruppierungen werden von dieser Technik nicht berücksichtigt. Wenn Sie jedoch wissen, dass Sie eine relativ normale Verteilung haben, die auf Ihr Zielmittel ausgerichtet ist, dann sollte dieser Ansatz meiner Ansicht nach eine angemessene Annäherung liefern.