我希望有人能验证以下问题是否是NP完全的，或者比简单的蛮力组合检查是否确实有更好/更轻松的解决方案。
我们的软件中存在一个资源分配问题，我将通过一个示例进行说明。
假设我们需要4个人在上类时间上类。这个数字以及它是“日间类”的事实都记录在我们的数据库中。
但是，我们并不仅要求任何人填补这些空白，还需要满足一些要求才能满足要求。
假设这4个对象中有2个必须是护士，而其中1个必须是医生。
其中一位医生还必须作为特定团队的一部分工作。
因此，我们有以下信息:
Day-shift: 4
1 doctor
1 doctor, need to work in team A
1 nurse
以上不是问题。问题就出在我们开始选择要上类的人，并试图弄清到目前为止我们选择的人是否真的可以满足标准。
例如，假设我们选择James，John，Ursula和Mary上类，而James和Ursula是医生，John和Mary是护士。
Ursula也在A队工作。
现在，根据我们尝试满足要求的顺序，除非我们开始尝试不同的组合，否则我们最终可能会推断出我们是否拥有合适的人员。
例如，如果从列表中移走并首先选择Ursula，我们可以将她与“1位医生”条件匹配。然后我们去看詹姆斯，我们注意到，由于他不在A队工作，因此“1名医生，需要在A队工作”的其他标准无法满足他的要求。由于另外两个人是护士，他们也不符合该标准。
因此，我们先回溯并尝试James，他也可以符合第一个条件，然后Ursula可以符合需要该团队的条件。
因此，问题出现在我们看来，因为我们需要尝试不同的组合，直到我们尝试了所有组合为止，在这种情况下，即使某些工作的总负责人数量与总工作人数相同，我们仍需要满足一些条件所需的头数，或者我们找到了一个可行的组合。
这是唯一的解决方案，谁能想到更好的解决方案？
编辑:进行一些澄清。
对这个问题的评论提到，对于这少数几个人，我们应该精打细算，我同意，这也许是我们可以做的，甚至可以做到这一点，就像在某种程度上优化某些产品的大小一样。如果数据量较小，则选择数据类型较小的初始排序方法，并选择不同的排序算法。
但是问题是这是名册计划系统的一部分，其中可能涉及很多人，既有“我们每天需要X人”，又有“我们有这么多Y人” ”，还有很大的潜力，“对于那些必须以某种方式与这些Y人相匹配的X人，我们拥有Z条标准 list ”，然后您添加一个事实，即我们将拥有领导者调整花名册后，需要几天的时间来实时进行相同的计算，然后就需要快速解决方案。
基本上，领导者会在屏幕上看到实时总和信息，该信息表明在整个白类中仍有多少人失踪，以及有多少人符合各种标准，以及我们实际上有多少人除了我们拥有的以外，还有ned。领导者调整名单时，必须用“如果詹姆斯不使用厄休拉(Ursula)而不是厄休拉(Ursula)进行白日类，而厄休拉(Ursula)进行夜类，该怎么办？”时，该显示将不得不半实时更新。
但是非常感谢到目前为止已经回答了这个问题的人们，约束满足问题听起来像是我们需要走的路，但是我们肯定会在这里仔细研究所有链接和算法名称。
这就是为什么我喜欢StackOverflow :)
最佳答案
你有一个constraint satisfaction problem;它们与NP的关系很有趣，因为它们通常是NP，但通常不是NP完全的，即它们对于多项式时间解是易处理的。
正如ebo在评论中指出的那样，您的情况听起来像可以将其表达为exact cover problem，您可以将Knuth's Algorithm X应用于该位置。如果您采取这种做法，请告诉我们如何解决。
关于algorithm - 可能是NP完全问题？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/956699/