0

基本上我正在寻找一个解决方案，如果给定的组合与给定的集合匹配，则该解决方案会返回。

示例：我有一个数组，其中存储了哪个机房以及哪个工作场所拥有哪些设备。我需要确定给定数量的具有特定需求的用户是否可以进入计算机房。在我的示例中，索引是工作场所编号。

$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");

我需要回答以下问题：如果我有两个用户需要扫描仪，而我有三个用户需要打印机，他们是否适合我的机房？

所有属性的简单总和是行不通的，因为如果我将三个需要打印机的人放在房间里，那么需要扫描仪的可怜人就没有工作场所了。

我已经考虑过迭代所有可能的组合，但是工作场所的数量越多，完成所需的时间就越长，甚至可能需要永远完成。

4

3 回答 3

0

如果您之后添加他们需要的东西怎么样，那么当您将第 1 个人添加到房间时。您看到他需要一台打印机，您将一台打印机添加到房间内的一组新人员中以及他们当前拥有的人员中。

因此，当您添加新人员时，您检查的是当前状态，而不是人员的需要。

于 2009-11-18T04:40:44.200 回答
0

当我第一次读到这篇文章时，它闻起来像是一个 NP 完全问题——而且它仍然有那种香味。

但我喜欢 Ólafur Waage 的回答。

如果您一次只带一个用户，那么您可以解决问题。即让第一个用户到达正好有他们需要的工作站，或者如果没有合适的话——即下一个用户“需要一台打印机，但剩下的唯一一台带有打印机的工作站已经有一台扫描仪”，然后去将它们放在带有打印机和扫描仪的工作站上。

如果这不是您想要的——如果确实，您计划提前一天为将要使用该房间一整天的用户，而您想知道的是“是否可行”——那么我'd 建议您在花费太多时间之前先 查看http://en.wikipedia.org/wiki/NP-complete 。

于 2009-11-18T04:42:46.883 回答
0

您说的是多组，而不是普通组。无论如何，如果，就像您给出的唯一示例一样，房间里的每个人都需要一个资源，而只有两个资源很重要，那么生活就非常容易：按丰富程度对您的设备阵列进行排序（仅扫描仪，仅打印机，两者兼而有之-提供两者都无关紧要的条目！），为每个资源分配尽可能多的单一资源（可用，请求）（并删除相应的请求者），如果“两者-”的数量，答案最终是“是” resource" 剩余设备数 >= 剩余请求者数。

如果您可以更清楚地指定要解决的问题类别，则可以相应地锐化答案（没有任何约束，这肯定是一个 NP 完全问题，正如另一个答案所建议的那样——但是，足够的约束可以使其在计算上可行的！）。

于 2009-11-18T04:50:56.603 回答