我在在线编码软件中发现了这个问题我无法有效地解决这个问题。
问题：
酒吧里有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号饮料，三位顾客都会满意。
我的解决方案：
我创建了一个饮料的散列图作为关键和客户价值
Drink : Customer
1 : [1 ,2]
2 : [1,3]
3 : [1,3]
我将从Hashmap中获取最大的值列表（因为所有客户都是唯一的）。
在这种情况下，所有的值都是相等的，所以我将选择drink 1的值[1,2]
globalList = [1,2]
noOfDrinksRequired = 1
现在我会找到所有其他列表的inter-section，无论哪个交叉点最大，我都会将它添加到global list
(globalList)中，并将所需饮料的数量增加1。并跟踪列表中元素的数量（“客户数量”）。如果列表长度等于客户数量，则我退出。globallist=globallist[1,3]喝2或3的值
现在高尔夫球手=[1,2,3]
不需要任何饮料
因为高尔夫球手。长度==N#顾客3的数量
如果没有重复步骤2
我知道这不是非常优化的解决方案（空间复杂度M*N和时间复杂度不确定）。有人能告诉我这个问题的最佳解决方案吗我也不确定我的解决方案是否能100%奏效。
最佳答案
这是一个典型的集封面问题--https://en.m.wikipedia.org/wiki/Set_cover_problem
它实际上是karp的21个np完全问题之一。有近似和贪婪的解决方案。
关于algorithm - 满足所有客户所需的最低饮料数量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42465685/