Комбинаторная задача, конфигурации помещений

Скажем, у меня есть куча гостиничных номеров, подходящих для 1, 2 или 3 человек.

Группа из 4 человек хочет забронировать, и я хочу представить им все возможные конфигурации, так как разные конфигурации имеют разные цены.

Возможные комбинации включают:

  • 4 * 1 местный номер
  • 2 * 2 местный номер
  • 1 * 3-местный номер + 1 * 1-местный номер
  • и так далее, и так далее

Как мне рассчитать различные группы?

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

Любые подсказки, советы или указатели?


algorithm math combinations
person gumuz    schedule 12.04.2011    source источник
comment
Это своего рода P(n), но не совсем. mathworld.wolfram.com/PartitionFunctionP.html (он возвращает только количество возможностей как таковых ..но возможно что-то найдете в этой статье)   -  person Ronny Brendel    schedule 12.04.2011
comment
спасибо, но я не думаю, что это все, так как размер комнаты может варьироваться, например, могут быть только комнаты для 2 и 4 человек.   -  person gumuz    schedule 12.04.2011
comment
Мх перебор наверное тогда. Рекурсия плюс ветвление каждый раз, когда вы добавляете одного человека в одну комнату. + избегание/удаление дубликатов.   -  person Ronny Brendel    schedule 12.04.2011

Ответы (1)


arrow_upward
1
arrow_downward

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

Имея это в виду, я бы использовал поиск в глубину с запоминанием. В Питоне:

@memoized
def search(n, room_types):
  ret = set()
  for t in room_types:
    if t >= n:
      ret.add((t,))
    else:
      for cfg in search(n - t, room_types):
        if sum(cfg) >= n:
          ret.add(cfg)
        else:
          ret.add(tuple(sorted(list(cfg) + [t])))
  return ret

print sorted(search(4, (1, 2, 3)))

Это производит:

[(1, 1, 1, 1), (1, 1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

@memoized взято из здесь.

person NPE    schedule 12.04.2011
comment
спасибо, я думаю, что это шаг в правильном направлении, но я подозреваю, что ограничение ребенка/взрослого довольно сложно применить к выходу этого, поскольку оно описывает фактические комбинации людей, а не только количество людей. - person gumuz; 12.04.2011