满足所有顾客所需的最低饮品数量
Minimum Number of Drinks required to Satisfy all Customomer
我在 Online Coding Comp 中找到了这个问题。而且我无法有效地解决它。
题 ：
酒吧里有 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 中选取最大的值列表（因为所有客户都是唯一的）。
在这种情况下都是平等的，所以我会选择饮料 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
我知道这不是很优化的解决方案（Space 复杂度 m*n 和时间复杂度不确定）。谁能告诉我这个问题的优化解决方案。我也不确定我的解决方案是否会 100% 有效。
这是一道经典的布景题 -- https://en.m.wikipedia.org/wiki/Set_cover_problem
它实际上是卡普的 21 个 NP 完全问题之一。对此有近似和贪婪的解决方案。
我在 Online Coding Comp 中找到了这个问题。而且我无法有效地解决它。 题 ： 酒吧里有 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 中选取最大的值列表（因为所有客户都是唯一的）。
在这种情况下都是平等的，所以我会选择饮料 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
我知道这不是很优化的解决方案（Space 复杂度 m*n 和时间复杂度不确定）。谁能告诉我这个问题的优化解决方案。我也不确定我的解决方案是否会 100% 有效。
这是一道经典的布景题 -- https://en.m.wikipedia.org/wiki/Set_cover_problem
它实际上是卡普的 21 个 NP 完全问题之一。对此有近似和贪婪的解决方案。