Я пишу программу, которая будет имитировать, как члены определенного таймшера будут запрашивать свои квартиры. Квартиры доступны только для определенных «событий» в течение года, и каждое событие имеет разную продолжительность (учитывается в днях). Для каждого мероприятия доступно несколько квартир, которые разделены на группы по стоимости (баллы в сутки).
У нас также может возникнуть ситуация, когда некоторые квартиры уже сданы в аренду, поэтому возможно, что определенные события не могут принять определенный тип квартир.
Теперь я хочу, чтобы участник запрашивал квартиры в соответствии с этой стратегией:
- Первоочередной задачей является максимальное количество дней проведения мероприятий.
- Максимальное количество потраченных баллов является вторым приоритетом (поэтому пользователь запрашивает наилучшую возможную квартиру, которую он/она может себе позволить, и при этом иметь как можно больше дней).
- Общая стоимость запрошенных квартир не может превышать общее количество доступных баллов для данного пользователя.
- Очевидно, что если для определенного события больше нет квартир данного типа, пользователь не должен запрашивать эту конкретную комбинацию квартира/событие.
Мне интересно, похожа ли проблема на проблему, описанную здесь:
http://en.wikipedia.org/wiki/Hungarian_algorithm
в том, что (я полагаю) можно сформулировать это как матричную проблему, где каждая запись имеет связанную с ней стоимость.
Однако разница в том, что для моей проблемы мне разрешено использовать одну и ту же квартиру для нескольких мероприятий — она не «потрачена» после того, как она была использована для одного мероприятия. Кроме того, стоимость входа на самом деле не является одномерной, поскольку с каждой комбинацией мероприятия/апартаментов связано как количество дней, и количество баллов, оба из которых должны быть максимальными (но с приоритет отдается количеству дней).
Например, допустим, есть три типа квартир стоимостью 75, 100 и 125 баллов в сутки и три события продолжительностью 2, 10 и 4 дня. Предположим далее, что многие квартиры заняты, поэтому матрица доступности выглядит так:
cost
75 100 125
2 True False True
days 10 False False True
4 True False True
Допустим также, что пользователю доступно 1250 баллов. Решение в этом случае будет заключаться в том, что пользователь запрашивает 10-дневное событие с квартирой на 125 баллов и ничего больше.
Грубый способ сделать это, возможно, будет рекурсивным алгоритмом:
- Пусть n будет количеством событий, которые вы сейчас пытаетесь
- Найдите все комбинации событий и квартир и рассчитайте комбинацию, которая максимизирует количество дней, а затем количество потраченных баллов (это будет включать все перестановки n событий, а также количество способов, которыми 3 типа квартир могут быть назначены n События).
- Пусть n=n-1
Я думаю, что это быстро станет непосильным, когда количество событий возрастет, поэтому мне интересно, существуют ли какие-либо алгоритмы, которые могут решить эту проблему менее затратным способом?
