检查一个组合是否与给定的组匹配

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完全问题，因为提出了另一个答案 - 但是，可以使它计算上可行！）。