algorithm - 我试图找到一个 "bartender algorithm"

Question

我正在解决旧编程竞赛中的一些示例问题。在这个问题中，我们得到了我们有多少调酒师以及他们知道哪些食谱的信息。制作每杯鸡尾酒需要 1 分钟，我们需要使用所有调酒师计算是否可以在 5 分钟内完成订单。

解决这个问题的关键是尽可能高效地分配鸡尾酒。这就是我被困的地方，我目前的算法将订单交给最不了解其他食谱的调酒师。但当然这还不是 100% 正确。谁能指出我正确的方向(或给我一个算法名称到谷歌)来解决这个“调酒师问题”？

Answer 1

这可以通过流网络来解决。

• 源对每个酒保都有边，容量为 5。
• 每个调酒师对他/她可以调制的每一种饮品都有优势，容量为 5。
• 每种饮料都有水槽边缘，容量与订购的数量相对应。

计算maximum flow从源头到汇点。如果任何订单仍未完成，则没有解决方案。