滿足所有客戶所需的最少飲料數量

我在線編碼比較中發現此問題。我無法有效地解決這個問題。問題：在酒吧有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

很高興提到這個問題的提法作爲一套封面，是要把喜歡特定飲品的客戶和宇宙中的所有顧客集合起來。如果你將問題的封面直接應用於問題中給出的集合，你將得到一組他們之間喜歡所有飲料的顧客。 –

回答