1
$\begingroup$

So in my school we have a day where everybody participates in different activities. Each projects can have like 10 members. The whole day is divided in 2 or 3 different blocks, in which the pupils assigned to the activity change.(So in block 1 pupil x takes part in activity a and in the second block in activity d). Before this day starts, we give make lists in which each pupil can tell us his 3 (or 4) favorite activities (he only takes part in two of them, these again are ordered from most "favorite" to least) in which he wants to take part. Now our job is to assign these pupils in a way that we have the best overall satisfaction among the pupils (so everybody did more or less did get his/her chosen activities).What would be a good algorithm to solve this ?(I'm quite familiar with programming (especially java), so the approach would be enough too (although some (pseudo-)code would be great too:) ) Is there any way to do this, apart from calculating such a "satisfaction" value for each possible solution?

An optional feature would be that if someone can't get in to his/her project, they would get into a similar on (also this sounds kind of sexist, you could for example rate how "female"/"male" this activity is and choose similar activities according to this scale)

I'm hope this question is fits into this platform, if it is totally off-topic I would be happy to tell me about a more suitable stack.

Looking forward to your suggestions, John

$\endgroup$
1
$\begingroup$

Although you could probably formulate and solve this problem using some sort of optimization algorithm (a mixed-integer formulation immediately comes to mind, and would be expensive), you might first try looking at algorithms for solving variants of the stable marriage problem. Your problem sounds close to something that might look like the hospitals/residents problem, but it would be difficult to know for sure without asking more questions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.