檢查一個組合是否與給定的組匹配

Question

基本上我正在尋找一個解決方案，如果一個給定的組合匹配一個給定的組合。

例：I具有存儲其中的計算機室和其工作場所具有設備的陣列。我需要找出是否有特定數量的具有特定需求的用戶可以放入電腦室。索引是我的例子中的工作場所編號。

$aComputerRoomEquipment = array(); 
$aComputerRoomEquipment[1] = array("PC"); 
$aComputerRoomEquipment[2] = array("PC"); 
$aComputerRoomEquipment[3] = array("PC", "Scanner"); 
$aComputerRoomEquipment[4] = array("PC", "Printer"); 
$aComputerRoomEquipment[5] = array("PC", "Scanner", "Printer"); 
$aComputerRoomEquipment[6] = array("PC"); 
$aComputerRoomEquipment[7] = array("PC", "Scanner", "Printer"); 
$aComputerRoomEquipment[8] = array("PC"); 

我需要回答以下問題：如果我有誰需要掃描儀的兩個用戶，我有誰需要一臺打印機三個用戶，他們是否適合我的計算機房或沒有？

所有屬性的簡單相加是不行的，因爲如果我把三個人誰需要一臺打印機的房間，不會有任何工作場所留給可憐的傢伙誰需要掃描儀。

我已經想通過所有可能的組合迭代的，但是工作場所的更大的數量，時間越長，將採取和可能採取永遠完成。

Answer 1

當我第一次讀到這，它聞起來像一個NP完全問題---它仍然有香氣。

但我喜歡ÓlafurWaage的回答。

如果你一次帶一個用戶，那麼你可以解決這個問題。即讓第一個用戶到達正好他們需要的工作站，或者如果沒有合適的話 - 即，下一個用戶「需要一臺打印機，但唯一帶有打印機的工作站已經有一臺掃描儀」，然後繼續使用打印機和掃描儀將它們放在工作站上。

如果這不是你想要的東西---如果確實，你打算提前一天對於那些要使用的房間一整天的用戶，你想知道什麼是「可行與否」 - - 那麼我建議你先看看http://en.wikipedia.org/wiki/NP-complete，然後再花太多時間。

Answer 2

如果你以後添加了他們需要的東西，那麼當你將人員1加入房間時如何。你看到他需要一臺打印機，將打印機添加到房間內的新人陣列以及他們目前擁有的東西。

所以，當你添加一個新的人，你檢查當前狀態，而不是需要的人。

Answer 3

你在說multisets，而不是普通的集合。無論如何，如果您只給出一個例子，房間裏的每個人都需要一個資源，而只有兩個資源很重要，生活是非常簡單的：按豐富程度對您的設備陣列進行分類（僅限掃描儀，僅打印機，提供的條目都不重要！），爲每個資源分配儘可能多的單一資源（最多可用，請求）（並刪除相應的請求者），如果「both-資源「剩下的設備> =剩餘的請求者數量。

如果您可以更清楚地指定要解決的問題類別，可以相應地對答案進行銳化（沒有任何限制，它肯定會是一個NP完全問題，因爲提出了另一個答案 - 但是，可以使它計算上可行！）。