algorithm - 产品可能的房间组合

Question

我有一个产品有多种可用和可定制的房间。例如:

• 1人间
• 可容纳 2 人的客房，配备一张特大号床
• 2 人间，配备两张分开的床
• 3人间

当客户订购产品(旅行)时，他会为我们提供一些参与者(例如:2 名成人和 2 名 child ......)

我必须让客户能够选择各种房间的组合。对于我们的例子，我们应该有:

• 1人4间
• 1人1间和3人1间
• 1 间 2 人房，带特大号床 + 1 间 2 人房，带独立床
• 2 间可容纳 2 人的特大号床
• 2 间 2 人间，带分开的床

此时，我不知道该怎么办!

Answer 1

这是 subset sum 的变体问题(具有 2 个维度，成人和 child )，其中您的总和是人数和 child 的数量，元素是房间。

看来，你的问题相当小(你不会有数百种房型，只有几种，而且每个旅行者为少数人预订房间)，所以显示所有可能性的蛮力是一个解决问题的可能性。

想法是以递归方式生成所有此类房间，并在向客户展示可能性之前 - 检查它是否满足要求。
递归算法将首先“猜测”您是否要使用当前房间类型，并且对于这两个选项 - 递归以解决较小的问题。

类 Java 伪代码:

private boolean matches(List<Room> rooms, int adults, int children) { 
    //check if the current list of rooms satisfies the demands
}
private int numPersons(List<Room> rooms) { 
    int res = 0;
    for (Room r : rooms) { 
        res += r.adults;
        res += r.children;
    }
    return res;
}

//wrapper function
public void generateAllPossibilities(List<Room> roomTypes, int adults, int children) { 
          generateAllPossibilities(roomTypes, adults, children, new ArrayList<>(), 0);
}

private void generateAllPossibilities(List<Room> roomTypes, int adults, int children, List<Room> soFar, int i) { 
    //check stop clauses, a "good" match, or out of bound:
    if (matches(soFar,adults,children)) {
         showOption(soFar); //succesful stop clause
         return;
    }
    if (i == roomTypes.size() || numPersons(rooms) > adults + children) {  
         return; //failing stop clause
    }
    //"guess" to add the current room type:
    soFar.add(roomTypes.get(i));
    //recurse with that guess:
    generateAllPossibilities(roomTypes, adults, children, soFar, i);
    //"guess" not to add the current room type
    soFar.remove(soFar.size()-1));
    generateAllPossibilities(roomTypes, adults, children, soFar, i+1);
}