Мне нужно назначить n человек на m курсов, где каждый человек указал свое первое и второе предпочтения, и каждый курс посещает максимальное количество человек. Каждый человек может посетить только один курс. Алгоритм должен найти одно решение, при котором
- максимальное количество людей, которым назначен один курс из их предпочтений,
- максимальное количество людей, которым назначен их первый выбор (с учетом 1, который имеет более высокий приоритет).
Я догадался, что это не редкость, но поиск не дал ничего особо полезного, поэтому решил откатить свою. Вот что я придумал до сих пор:
- Для курсов, которые имеют меньше первых предпочтений, чем максимальное количество людей, посещающих курс, назначьте всех этих людей на курс
- Для других курсов: добавьте случайных людей в курс, которые выбрали это курс в качестве первого выбора, пока курс не будет заполнен
- Для курсов, у которых меньше вторых предпочтений, чем свободных мест, назначьте всех этих людей на курс
- Для других курсов: поместите случайных людей в курс, который выбрал этот курс в качестве второго выбор до тех пор, пока курс не будет заполнен
- Для каждого человека без курса: При первом (а затем втором) предпочтении ищите человека, который выбрал другой курс, на котором места все еще свободны (если найдено более одного курса, выберите тот, который выбрал курс с наибольшим количеством свободных мест), переместите этого человека ко второму варианту и назначьте пропавшего человека
Я все еще не думаю, что этот алгоритм найдет оптимальное решение проблемы из-за последнего шага. Есть идеи, как сделать это лучше? Есть ли другой алгоритм, который решает эту проблему?
задан neo 10 June 2011 в 15:04
поделиться