Справедливо распределить ограниченное количество вещей по тому, сколько они хотят

Question

Итак, у меня есть набор пользователей, которые хотят получить 1 товар, но они могут сделать 3 желания, отсортированные по их желанию. Но количество раз, которое можно отдать одному предмету, ограничено для всех пользователей. В конце концов, каждый должен (возможно) получить предмет, который он желает больше всего.

Я уже пытался добавить каждого пользователя, который желает элемент X, в список «желающих», если этот список меньше доступного числа, его получают все. Проблема в том, что это не учитывает, насколько кому-то нравится этот предмет, если количество доступных предметов больше.

Я полагаю, что уже может быть математическая проблема, которая пытается решить эту проблему.

Answer 1

скажем, у вас есть 100 яблок, бананов и моркови

и скажем, у вас есть 300 человек, которые оценили свои три варианта выбора.

простой алгоритм состоит в том, чтобы попытаться выполнить всепервый выбор первый.Итак, скажем, первый выбор из 300 человек: 150 яблок, 120 бананов, 30 морковей.если количество доступных предметов меньше желаемого количества товара, каждый получает один.в противном случае случайным образом распределяйте.

, поэтому в приведенном выше примере вы можете выполнить первый выбор из 230 человек.

, затем пройти второй (и затем третий) выбор оставшихся людей и повторить.