algorithm - 懒惰酒保算法

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) 在 E 中，当饮料 i 在客户 j 的最喜欢的集合中时>。我们想要找到 Drinks 的最小基数子集以覆盖所有 Customers 集。

此问题是 Set cover problem 的变体(查看 Hitting set formulation )。已知它是 NP-hard，因此没有已知的多项式算法。

根据特定问题的约束，可以使用简单的蛮力算法或动态编程/内存方法来解决，但您应该知道确切的约束。