Алгоритм планирования наилучшего соответствия для размещения / проблемы с дневным пропуском?

Question

У меня проблема с расписанием. Я пытаюсь найти наилучший алгоритм подбора.

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

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

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

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

Нет, это не домашняя работа.:)

Заранее спасибо.

Answer 1

Можно использовать Очередь приоритетов (PQ).Каждый день вы помещаете клиентов в (PQ), вычисляя приоритет как p = 1/r, где r - это количество оставшихся дней для этого гостя в вашем отеле.Таким образом, каждый день, когда вы отдаете свои n пропуска n клиентам, у которых меньше дней на проживание в отеле (если клиенту остается всего 1 день, он / она должен иметь самый высокий приоритетполучить пропуск, потому что есть только одна возможность).Если у вас есть несколько клиентов с равным p, вы выбираете из них общее количество дней, проведенных в вашем отеле, и вы предпочитаете, чтобы клиенты оставались дольше.

Answer 2

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

Answer 3

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