Алгоритм составления билета

Question

Я пытаюсь написать программу для автоматизации оформления заявки.

У нас есть определенное количество абонементов и мы хотим разделить билеты на группы людей.Есть X количество игр, Y количество абонементов и Z количество людей.Каждый из Z людей оценил X игр.

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

Answer 1

Если у вас есть X игр и пропуски Y сезона, предположительно, есть билеты X * Y, которые можно раздать людям Z, верно?

Звучит так, что это можно рассматривать как проблему оптимизации, но длядля этого вы должны определить свои основные цели?Я предполагаю, что вы хотите, чтобы каждый человек получил билеты X * Y / Z (разделить их равномерно), но, возможно, нет.Я предполагаю, что вы также хотите максимизировать совокупное удовлетворение (определенное каким-то образом согласно рейтингу) в билетах.Возможно, вы захотите назначить крупный штраф за удовлетворение для человека, если он получит более 1 билета на одну и ту же игру.Я полагаю, что последний аспект может заключаться в том, что прямой подход не является лучшим, но я могу ошибаться.

Как только вы поймете, что вы пытаетесь оптимизировать (если это действительно проблема оптимизации),Тогда вы можете рассмотреть лучший подход к проблеме.Это может быть ваше собственное решение или вы можете попробовать существующую технику (генетический алгоритм и т. Д.).Прежде чем сделать это, важно, чтобы вы правильно сформулировали проблему.

Answer 2

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

Answer 3

Если бы не было никаких предпочтений, это было бы прямой проблемой максимального расхода с минимальным срезом.http://en.wikipedia.org/wiki/Maximum_flow_problem, следующим образом:

Создайте исходную вершину A. Из A создайте Z вершин, по одной для каждого человека.Емкость может быть бесконечной (или очень, очень большой).Создайте приемник B и создайте X вершин, по одной на каждую игру, связанных с B;вместимость должна быть Y (у вас есть Y билетов за игру).От каждого человека, ссылка на каждую игру, которую они оценили, с емкостью 1.

Если вы посмотрите на ссылку вики выше, есть около 10 алгоритмов для решения этой основной проблемы.Найдите тот, который вы понимаете и можете реализовать самостоятельно, потому что вам нужно будет немного его изменить.Я не знаком со всеми из них, но те, о которых я знаю, имеют шаг «выбери край» или «выбери путь».Вам следует изменить логику «как выбрать край», чтобы учесть приоритетность игр.Я не уверен, какой именно порядок должен быть (вам, вероятно, нужно будет поэкспериментировать), но если вы скажете, что игра с самым низким рейтингом - 1, следующая - от 2 до X, а затем оценка типа «ранжирование края- количество игр, на которые человек уже подписан, может сработать.