Проблема комбинаторики, конфигурации помещений - PullRequest
Новая
       10

Проблема комбинаторики, конфигурации помещений

2 голосов
/ 12 апреля 2011

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

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

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

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

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

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

Есть подсказки, советы или указатели?

1 Ответ

2 голосов
/ 12 апреля 2011

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

Учитывая это, я бы использовал поиск в глубину с памяткой.В Python: 

@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 происходит от здесь .

...