Sto cercando un modo per ordinare le persone in classi di preferenza.Algoritmo per il raggruppamento basato sulle preferenze
Per esempio, dicono che ci sono 100 studenti che sono ogni intenzione di assegnare una delle cinque classi:
- Scienza - 40 posti
- matematica - 15 posti
- Storia - 15 posti
- Computers - 20 posti
- scrittura - 10 posti a sedere
Ogni studente ha tre classi preferite ordinate per preferenza. Qual è il modo migliore per avvicinarsi a dividere gli studenti in modo che il maggior numero di persone ottenga le loro classi di prima e seconda scelta il più possibile, mentre allo stesso tempo si assicura che nessuna classe abbia troppi studenti per la stanza.
Ci ho pensato si avvicina con il seguente metodo:
- Gruppo tutti gli studenti per la loro prima classe scelta
- Consiglio sulle classi hanno troppi studenti e che sono troppo pochi
- Controllare vedere se gli studenti nelle classi overbooked hanno classi di seconda scelta che sono sotto prenotazione
- Spostare gli studenti di conseguenza
- Ripetere 2-4 con 3 classi di scelta
Mentre sento che questa è un'implementazione ragionevole, mi chiedo se ci sono altri algoritmi che risolvono questo problema in un modo migliore. Ho provato a cercare dappertutto, ma non riesco a trovare nulla che possa risolvere questo tipo di problema.
Un 'problema' con questo genere di algoritmi è che è facile 'imbrogliare' selezionando corsi popolari (e piccole) come 2 ° e 3 ° scelta per forzare un posizionamento di 1 ° scelta .. Ho sarebbe molto interessato a una soluzione che risolva questo problema in qualche modo (anche se al momento non ho intuito di approcciarlo). – Joost