Нужен алгоритм для распределения ниже

Question

Мне нужен алгоритм для проблемы ниже.

У меня есть учителя, и у каждого учителя есть свой любимый предмет. Например,

Учитель 1, возможно, предпочли science, maths and computers
Учитель 2, возможно, предпочли english and maths
Учитель 3, возможно, предпочли science, english and maths
как так .....

И у меня есть N количество листов ответов , Каждый из них попадает под любой предмет (english, science, maths and computers). Мне нужно назначить эти листы ответов каждому учителю, исходя из их предпочтений. Но максимум мы можем назначить 50 работ учителю. И если у нас будет 1000 листов ответов, у нас будет минимум 20 преподавателей (1000/50).

И если у нас есть 112 листов ответов в maths, и если у нас есть два преподавателя с предпочтением maths, мы можем назначить им 100, а остальные 12 мы можем назначить любому учителю (который относится к категории, не относящейся к категории).

Успех этого алгоритма будет определяться тем, насколько эффективно он распределяет листы ответов преподавателям по их предпочтениям и насколько они менее предпочтительны.

Может ли кто-нибудь сказать мне, какой алгоритм подходит для него?

Answer 1

Эта задача может быть сформулирована в виде простого assignment problem (присваивающей n рабочих мест для n работников):

Каждый учитель появляется в 50 раз, как рабочий, и каждый лист появляются один раз в качестве задания.

Учитель подключен к листу весом 0, если это один из его любимых предметов и вес 1, если нет. Если есть больше рабочих (50 * number of teachers), чем заданий, добавьте фиктивные задания (пока число работников не будет равным количеству заданий), которые связаны со всеми работниками с весом 0, эти задания могут быть проигнорированы в решении.

С этого момента обратитесь к любому алгоритму, который решает проблему присвоения (см. Ссылку на wiki). вы хотите найти задание с минимальным весом.