組合問題，房間配置

Question

說我有一堆酒店房間，適合1,2或3人。

一羣4人想預訂，我想給他們提供所有可能的配置，因爲不同的配置有不同的價格。

可能的組合包括：

• 4 * 1人房
• 2 * 2人房間
• 1 * 3人房+ 1 * 1人房
• 等等，等等

我將如何去計算不同的分組？

增加的複雜性是這些人中的一些人可能是兒童，這應該總是與房間裏的成年人合併。我想我應該只計算所有組合，並篩選出不滿足這個約束條件的組合。

任何提示，提示或指針？

Answer 1

問題的表述方式表明房間類型的數量很少，所需的最大組大小也是如此。

考慮到這一點，我會在記憶中使用深度優先搜索。在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來自here。