Создать все возможные комбинации не уникальных целых чисел в массиве C ++

Question

У меня есть приложение для управления отелем с модулем бронирования.Я хотел бы иметь возможность вычислять возможные комбинации номеров для больших групп.

У меня есть массив всех доступных номеров.Массив ниже будет отображать 10 свободных комнат: 2 односпальные кровати, 2 двуспальные кровати и т. Д.

int currenylyAvailableRooms [10] = { 1, 1, 2, 2, 3, 3, 4, 4, 5, 5 };

Я хотел бы запросить этот массив и выяснить, существует ли комбинация комнат для размещенияx гостей.Например, я хотел бы знать, существует ли комбинация, которая бы подходила 21 гостю.(Для приведенного выше примера он вернул бы true с, например, 5,5,4,4,2,1 - может быть более 1 комбинации.

Имейте в виду, что отель может бытьочень большие и имеют 20 одноместных номеров (20 х 1 в массиве) и 10 люксов, которые могут вместить 10 человек (10 х 10 в массиве) с массивом currenylyAvailableRooms, имеющим даже 100 элементов.

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

У меня такой вопрос: как мне найти возможные комбинации элементов в массиве, которые суммируются с указанным целым числом ИЛИ как рассчитать все возможные комбинации

Answer 1

Учтите, что для N доступных комнат данная комната либо является частью выбора, либо нет, следовательно, у вас есть 2 ^ N различных вариантов выбора.Они могут быть изображены в виде древовидной схемы

                                   x
                                  / \
                                 /   \
                                x     1
                               / \   / \
                              /  |   |  \
                             x   2   1   1+2

, где направление вправо означает «комната находится», а движение налево означает «комната не входит», а узлы помечены общим количеством гостей длявыбранные комнаты.Например, если вы не выбираете комнату 1 и не выбираете комнату 2, тогда общая сумма равна 0, когда вы выбираете комнату 1 и выбираете комнату 2, вы добавляете вместимость первой комнаты с вместимостью комнаты 2 (помеченнойкак 1+2).

Хитрость в том, чтобы теперь не обходить все ветви до конца, а только до

a) сумма - это желаемое количество гостей => у вас есть решение.Не нужно углубляться в дерево.

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

c) вы достигли конца ветви и все еще недостаточно места.

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

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

С другой стороны,массив из 10 элементов относительно мал.Даже с учетом комбинаторики, где факториал обычно является убийцей, 10! = 3628800 все еще находится в разумных пределах, и, возможно, достаточно простого алгоритма грубой силы.Однако 100! - это уже совсем другая история;).