Наиболее эффективный алгоритм для бронирования?

Question

[DevilFox]

Нужно найти наиболее дешевые номера в отеле. Допустим, в отель хотят заселиться 6 человек. Мы берем список свободных номеров.
В одной категории свободны два номера для двоих людей. Стоимость 3500. 4 человека, 2 номера = 3500 * 2 = 7000.
В следующей категории есть номер за 4000. Туда можно поселить 1-го человека = 4000.
Дальше у нас есть номер за 5000 туда тоже можно заселить 1-го человека. Итого получается 16 000 общей стоимости. Я думаю решать задачу в лоб. Взять список самых дешевых номеров умножить на количество мест. Дальше распределять оставшиеся места в чуть более дорогие номера. Может существует какой-то более эффективный алгоритм для получения минимально низкой возможной суммы бронирования? Так как я знаю только тот вариант, который описал.

Comments

[Roman]

Пять двухместных по 3500
и
Три четырехместных за 6000

10 человек попадут в двухместные, а не в два четырёхместных и один двухместный.

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

Отбрасывая (не учитывавя) предпочтения, например кто-то хочет заселиться отдельно, а кто-то вдвоём втроём и т.п.

Answer 1

[Wataru]

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

Если у нас есть n людей, то заводим массив от 0 до n. Помечаем, что 0 человек можно размесить за 0 рублей, а все остальное за бесконечность. Потом для каждого свободного номера ()проходиммассив с конца в начало и, если (текущаяя цена + цена номера) для k человек лучще чем цена размещения (k+вместимость номера), то перезаписываем лучшую цену для k+вместимость. Так же сохраняем в вспомагательном массиве, какой номер мы сейчас взяли для данного количества человек (k+вместимость номера).

В конце смотрим на ячейку для n человек - там минимальная стоимость будет.

В итоге, время работы алгоритма O(n*m), где n человек и m свободных номеров.

Это решение динамическим программированием даже короче и легче полного перебора: буквально 2 вложенных цикла для расчета и один while для восстановления ответа.

Comments

[DevilFox]

Спасибо

Answer 2

[mayton2019]

Это похоже на Транспортную Задачу. Почитай описание.
Кроме того ты должен обозначить что ты понимаешь под эффективностью.
В некоторых случаях это может быть - заработать больше денег.
А в некоторых случаях - не оставить ни одного человека незаселенным.
Или просто уменьшить простой номера.

Comments

[DevilFox]

Спасибо за наводку. Обязательно все должны заселиться. В результате - наименьшая общая стоимость номеров для данной группы людей. Которых может быть и 10 человек и 5. Определения транспортной задачи мне вполне достаточно. Так что деталями надоедать не буду.