Удаление элементов из неравномерно распределенного множества

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

У меня есть пул вопросов, которые игроки уже видели. Мне нужно удалять 30 вопросов из пула каждый месяц. Мне нужно выбрать вопросы для удаления таким образом, чтобы максимизировать количество доступных вопросов, оставшихся в пуле для игрока с наименьшим количеством доступных вопросов.

Пример с пулом из 5 вопросов (и нужно удалить 3):

  • игрок A видел вопросы 1, 3 и 5
  • игрок B видел вопросы 1 и 4
  • игрок C видел вопросы 2 и 4

Я подумал об удалении вопросов, которые видел лучший игрок, но положение изменится. Следуя приведенному выше примеру, игроку А осталось сыграть только 2 вопроса (2 и 4). Однако, если я уберу 1, 3 и 5, ситуация будет следующей:

  • игрок A может сыграть вопросы 2 и 4
  • игрок B может сыграть вопрос 2
  • игрок C не может ничего сыграть, потому что 1, 3, 5 удалены, а 2 и 4 он уже видел.

Оценка за это решение равна нулю, т.е. игрок с наименьшим количеством доступных вопросов имеет ноль доступных вопросов для игры.

В этом случае лучше удалить 1, 3 и 4, получив:

  • игрок A может сыграть вопрос 2
  • игрок B может сыграть вопросы 2 и 5
  • игрок C может сыграть вопрос 5

Оценка за это решение равна единице, так как у двух игроков с наименьшим количеством доступных вопросов для игры есть по одному доступному вопросу.

Если бы размер данных был небольшим, я бы смог найти решение методом грубой силы. Однако у меня сотни игроков и вопросов, поэтому я ищу какой-нибудь алгоритм для решения этой задачи.

9
задан Community 23 May 2017 в 11:55
поделиться