满足所有客户所需的最少饮料数量

我在线编码比较中发现此问题。我无法有效地解决这个问题。问题：在酒吧有N个顾客，他们最多可以喜欢M饮料。如果顾客至少喝了一杯他自己选择的饮料，顾客就会满意。我们需要找到准备满足所有客户的最低饮品数量。下面是一个例子满足所有客户所需的最少饮料数量

N = 3 # No of Customer 
M = 3 (Maximum Drinks available) 
customer 1 : [ 2,1,3] 
customer 2 : [1,1] 
customer 3 : [2,2,3]

注：一个客户也可以多次喜欢同样的饮料。答案：最少需要的饮料数量是2 说明：如果我们准备饮料编号1和2那么所有三个顾客都可以满意。

我的解决方案：我创建的饮料一个HashMap的关键和客户价值

Drink : Customer 
1 : [1 ,2] 
2 : [1,3] 
3 : [1,3]

所有在这种情况下相等，所以我将挑选饮料1的值[1,2]

globalList = [1,2] 
noOfDrinksRequired = 1

现在我会发现内部节与所有其他列表，无论哪个交点最大我将其添加到全局列表(globalList)并增加所需饮料的数量(noOfDrinksRequired)通过1。还要跟踪列表中的元素数量（“客户数量”）。如果列表长度等于客户数量，那么我就退出了。

globalList = globalList∩[1,3]＃喝2的或3的值
现在golbalList = [1,2,3]和 noOfDrinksRequired + = 1 由于golbalList.length == N＃的无客户3 如果不重复步骤2

我知道这是不是很优化的解决方案（空间复杂度m * n个和时间复杂不确定的）。任何人都可以告诉我这个问题的优化解决方案。此外，我不确定我的解决方案是否能100％工作。

2017-02-26 vivek

请阅读NP完整问题。你的问题是一个设置问题。特别是这意味着如果你认为你有一个O（n^2）算法，你可能需要再考虑一次。 –

那么我没有数学计算。这是近似猜测，也可能是错误的。 – vivek

那是错的。如果你想要一个近似的解决方案，那么我想你的解决方案与[贪婪算法]（https://en.wikipedia.org/wiki/Set_cover_problem#Greedy_algorithm）相同，尽管很难说清楚。 –

事实上，这是卡普的21个NP完全问题之一。有近似和贪婪的解决方案。

2017-02-26 08:10:54

很高兴提到这个问题的提法作为一套封面，是要把喜欢特定饮品的客户和宇宙中的所有顾客集合起来。如果你将问题的封面直接应用于问题中给出的集合，你将得到一组他们之间喜欢所有饮料的顾客。 –

回答