检查组合是否与给定的集合匹配
基本上，我正在寻找一个解决方案，如果给定的组合与给定的集合匹配，则返回该解决方案。
例如:我有一个数组，用来存储哪个机房和哪个工作场所有哪些设备。我需要找出有特定需求的给定数量的用户是否可以进入计算机室。在我的示例中，索引是工作场所编号。
$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");我需要回答以下问题:如果我有两个用户需要扫描仪，我有三个用户需要打印机，它们是否适合我的计算机房？
简单地将所有属性相加是行不通的，因为如果我让三个需要打印机的人在房间里，就没有任何工作空间留给需要扫描仪的可怜的人了。
我已经想过迭代所有可能的组合，但工作场所的数量越多，完成的时间就越长，而且可能永远都不会完成。
回答 3
Stack Overflow用户
发布于 2009-11-18 04:42:47
当我第一次读到这篇文章时，它闻起来像是一个NP-complete问题-而且它仍然有那种香味。
但我喜欢Ólafur Waage的答案。
如果你一次只处理一个用户，那么你就可以解决这个问题。例如，让第一个用户到达他们需要的工作站，或者如果没有合适的工作站-即下一个用户“需要一台打印机，但只剩下一个拥有打印机的工作站已经有了一台扫描仪”，然后继续并将它们与打印机和扫描仪放在工作站上。
如果这不是你想要的-如果你真的打算提前一天为使用房间的用户做计划，而你想知道的是“可行与否”-那么我建议你在花太多时间在这上面之前先看看http://en.wikipedia.org/wiki/NP-complete。
Stack Overflow用户
发布于 2009-11-18 04:40:44
如果您在之后添加他们需要的内容，那么当您将person 1添加到房间中时会怎么样。您看到他需要一台打印机，您将一台打印机添加到房间内的新人员阵列中，以及他们当前拥有的设备。
因此，当你添加一个新的人时，你会检查当前的状态，而不是人们的需求。
Stack Overflow用户
发布于 2009-11-18 04:50:57
你说的是多集，而不是普通集。无论如何，如果在您给出的唯一示例中，房间中的每个人都需要一个资源，并且只有两个资源重要，那么生活就非常简单:按丰富度对您的设备数组进行排序(仅限扫描仪、仅限打印机、两者都不重要！)，为每个资源分配与min(可用，已请求)一样多的一个资源(可用，已请求)(并删除相应的请求者)，如果剩余的“两个资源”设备的数量为>=剩余的请求者的数量，则最终的答案是“是”。
如果您能够更清楚地指定您想要解决的问题类别，答案就会相应地变得清晰(如果没有任何约束，它肯定会是NP完全问题，正如另一个答案所建议的那样--但是，足够的约束可以使它在计算上可行！)。
https://stackoverflow.com/questions/1753667
复制
腾讯云开发者
