Szukam sposobu sortowania ludzi na klasy według preferencji.Algorytmy dla grupowania według preferencji
Załóżmy, że istnieje 100 studentów, z których każdy będzie przypisany jeden z pięciu klasach:
- nauka - 40 miejsc
- Math - 15 miejsc
- Historia - 15 miejsc
- Computers - 20 miejsc
- piśmie - 10 miejsc
Każdy uczeń ma trzy preferowane klasy uporządkowane według preferencji. Jaki jest najlepszy sposób podejścia do dzielenia się uczniami tak, aby jak najwięcej osób miało możliwość wyboru pierwszego i drugiego wyboru, jednocześnie upewniając się, że żadna klasa nie ma zbyt wielu uczniów do tego pokoju.
myślałem o zbliżającym się go w następujący sposób:
- Grupa wszyscy uczniowie pierwszej klasy według ich wyboru
- zobaczyć, które klasy mają zbyt wielu uczniów, a które mają zbyt mało
- wyboru, aby zobacz, czy któryś z uczniów w zajęciach z rezerwowaniem ma zajęcia z drugiego wyboru, które są objęte rezerwacją:
- Przenieś odpowiednio tych uczniów
- Powtórz 2-4 z klasami trzeciego wyboru
Chociaż wydaje mi się, że jest to rozsądna implementacja, zastanawiam się, czy istnieją inne algorytmy, które rozwiązują ten problem w lepszy sposób. Próbowałem już poszukać, ale nie mogę znaleźć niczego, co rozwiązałoby ten problem.
Jeden „problem” z tymi rodzaju algorytmów jest to, że jest łatwy do „oszukać” wybierając popularne (i małych) kursy w 2. i 3. wyboru, aby wymusić od 1 wybór umieszczenie .. I byłby bardzo zainteresowany rozwiązaniem, które w jakikolwiek sposób to rozwiązuje (chociaż obecnie nie mam do tego intuicji). – Joost