检查组合一组给定匹配

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完全问题---，它仍然具有香气。

但我喜欢奥拉维尔Waage的答案。

如果你把用户一次一个，则可以解决这个问题。即把第一用户在拥有其所需要的内容，或者工作站到达，如果没有合适的---即。下一个用户“需要一台打印机，但留下了一个打印机的唯一工作站已经有一台扫描仪”，然后继续前进，把他们在与打印机和扫描仪的工作站。

如果这不是你想要的东西---如果确实，你打算提前一天对于那些要使用的房间一整天的用户，你想知道什么是“可行与否” --- - 然后我建议你看一看 http://en.wikipedia.org/wiki / NP完全花太多时间在这之前。

Answer 2

怎么样，如果你加他们需要什么之后，因此当您增加1人进了房间。你看，他需要一台打印机，您添加打印机进入房间内的人一个新的数组，但当前拥有的东西。

所以，当你添加一个新的人，你检查当前状态，而不是人民的需要。

Answer 3

你说的多集，而不是普通的套。通过丰富的排序阵列设备（扫描仪只，打印机只，两者 - ：无论如何，如果，在你给唯一的例子，每个人都在房间里需要一个单一的资源，只有两种资源的问题，生活是非常容易提供既条目并不重要！），分配尽可能多的一个资源，只分（适用，请求）为每个资源（并删除相应的请求者），答案终于“是”如果“数量磁盘后资源”左设备是> =请求者的数量左

如果你能更清楚你想要什么的问题类别来解决，答案可以相应削尖指定（没有任何限制，它肯定会是一个NP完全问题，作为另一个答案建议 - 而是，足以约束可以使其计算上是可行！）。