我正在尝试找到一种“调酒师算法”。 [英] I'm trying to find a "bartender algorithm"

问题描述

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

I was solving some example questions from an old programming contest. In this question we get an input of how many bartender we have, and which recipe's they know. Each cocktail takes 1 minute to make and we need to calculate if the order can be finished within 5 minutes, using all bartenders.

解决此问题的关键是分配鸡尾酒尽可能高效。多数民众赞成在这里，我目前的算法是将订单分配给了解最少其他食谱的调酒师。但是，当然这还不是100％正确的。谁能指出我的正确方向（或给我一个Google的算法名称）来解决此侍酒者问题？

The key to solving this problem is assigning cocktails as efficient as possible. And thats where I'm stuck, my current algorithm gives the order to the bartender who knows the least other recipes. But of course this isn't 100% correct yet. Could anyone point me in the right direction (or give me an algorithm name to google) which solves this "bartender problem"?

推荐答案

可以用流动网络解决。

• 源对每个调酒师都有边，容量为5。


• 每个调酒师对他/她可以调制的每种饮料都具有边缘，容量为5。


• 每种饮料对水槽都有边缘，其容量对应于其数量

计算最大流量从源到接收器。如果任何订单仍未履行，则没有解决方案。

Compute the maximum flow from the source to the sink. If any order remains unfulfilled, there is no solution.

这篇关于我正在尝试找到一种“调酒师算法”。的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！