懒惰的调酒师算法

Question

我在其中一次采访中发现了以下问题.请建议我这个算法.我不需要代码.

• 有N很多可能的饮料.(n1,n2 ..)
• 有C多少固定客户.
• 每个顾客都有固定喜欢的饮料.
• 调酒师必须创造尽可能少的饮料以满足所有顾客的需求

例:

Cust1: n3,n7,n5,n2,n9  
Cust2: n5  
Cust3: n2,n3  
Cust4: n4  
Cust5: n3,n4,n3,n5,n7,n4    

Output: 3(n3,n4,n5)  

Answer 1

让我们重新解决这个问题.我们有一个二分图G(Drinks, Customers, E).当饮料在顾客最喜欢的一套时,边缘e(i, j)就在哪里.我们希望找到涵盖所有集合的最小基数子集.EijDrinksCustomers

这个问题是Set cover问题的变化(看看Hitting set公式).众所周知NP-hard,因此没有已知的多项式算法.

根据特定问题的约束,可以使用简单的强力算法或动态编程/记忆方法来解决,但是您应该知道确切的约束.