Надежный алгоритм назначения учеников сопровождающим

Question

Вот проблема: учитывая 4 группы учеников с размерами A, B, C и D и всего k шаперонов, разработайте алгоритм для назначения шаперонов студентам в почти равных пропорциях.

Вы не можете просто дать группам k * A / N, k * B / N, k * C / N, k * D / N шаперонов, потому что число шаперонов должно быть положительным целым числом,И вы не можете просто округлить, потому что тогда вы можете не получить нужное количество шаперонов.Так что моя идея состоит в том, что вы отбрасываете дробную часть и даете целую часть каждой группе, так что делайте целочисленное деление.Тогда у вас могут остаться некоторые сопровождающие, но не более 3, поэтому раздайте их группам с самыми большими остатками.

Затем интервьюер указал, что с этим есть проблема.Если вы добавите еще один шаперон, поэтому увеличьте k до k + 1, тогда может случиться, что одна из групп фактически потеряет шаперон таким образом.Она привела мне пример, но я этого не помню.

Может кто-нибудь придумать алгоритм, который позволит избежать этой проблемы?

Answer 1

Проблема, которую вы пытаетесь решить, обычно называется проблемой распределения или распределения голосов.Это та же проблема, что и при назначении количества мест в Палате представителей США для каждого штата.

Проблема устойчивости, которой не удается достичь в вашем подходе (известном как метод Гамильтона или метод наибольшего остатка),известный как Алабамский парадокс .Из статьи в Википедии: «Парадокс Алабамы был обнаружен в 1880 году, когда было обнаружено, что увеличение общего количества мест уменьшит долю Алабамы с 8 до 7».

Исторически сложилось так, что по крайней мере четыре различных методаиспользуемый в США: метод Джефферсона, метод Гамильтона, метод Вебстера и текущий метод Хантингтона-Хилла , используемый с 1941 года.

Идея этих последних методов заключается в следующем.Пусть D = N/k, общая численность населения, деленная на количество мест / шаперонов.Затем позвольте d = D и изменяйте d до тех пор, пока округление k_i = round(G_i/d) не составит правильное количество мест, то есть

раунд (G_1 / d) + раунд (G_2 / d) + ...+ round (G_m / d) = k

Подвох в том, как работает функция round.Обходы Вебстера обходятся в обычном смысле: слабо выше .5 идут вверх и строго ниже .5 идут вниз, что очень похоже на использование среднего арифметического.Метод Хантингтона-Хилла основан на идее использования среднего геометрического вместо.Вот краткое изложение этих методов здесь .Обратите внимание, что все эти алгоритмы делителей имеют недостатки в том, что они нарушают правило квоты: государство не может получить по крайней мере floor(G_m/D) представителей.

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

Answer 2

Учитывая 4 группы учеников с размерами A, B, C и D и в общей сложности k шаперонов, разработать алгоритм назначения шаперонов студентам в почти равных пропорциях.

Вот алгоритм, который решит вопрос очень просто:

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

2. Если общее количество назначенных шаперонов равно k,тогда мы закончим.

3. Назначьте одного шаперона одной группе.Группа, которая должна получить шаперона, является группой с самым низким соотношением шаперонов на одного студента.В случае ничьей выберите группу с наибольшим количеством учеников среди тех, у кого наименьшее соотношение шаперонов на одного учащегося.Если еще есть связь, то из числа выбранных выберите группу в алфавитном порядке первой.

4. Перейдите к шагу 2.

Это делает однозначные детерминированные назначения.Пропорции будут настолько близки, насколько позволяют значения.Увеличение k не приведет к уменьшению назначений какой-либо группе, поскольку фактически оно просто вызывает дополнительную итерацию, и никакие итерации не уменьшают назначения какой-либо группы.

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

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