我只是想让某人验证以下问题是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是护士.

厄秀拉也在A队工作.

现在,根据我们试图适应账单的顺序,我们最终可能会推断出我们是否拥有合适的人,除非我们开始尝试不同的组合.

例如,如果在列表中首先选择Ursula,我们可以将她与“1医生”标准相匹配.然后我们到达詹姆斯,我们注意到,由于他不在A队工作,所以关于“1位医生,需要在A队工作”的其他标准,不能用他来填补.由于另外两个人是护士,他们也不符合这个标准.

因此,我们首先回溯并尝试詹姆斯,他也可以符合第一个标准,然后厄秀拉可以满足需要该团队的标准.

因此我们需要尝试不同的组合来解决问题,直到我们要么全部尝试,在这种情况下我们有一些尚未填充的标准,即使工作头的总数与总数相同需要的头数,或者我们找到了一个有效的组合.

这是唯一的解决方案,任何人都可以想到更好的解决方案吗？

编辑：一些澄清.

对这个问题的评论提到,对于这几个人,我们应该蛮力,我同意,这可能是我们可以做的,我们甚至可以做到这一点,在某些优化看待大小的同一条道路上如果数据量很小,数据并选择不同的排序算法,初始开销较小.

但问题是,这是一个名册计划系统的一部分,你可能会涉及很多人,“我们在白天需要X人”以及“我们有这个Y人群”这将是“,以及一个大的潜力”我们有这些X人的Z标准列表,将不得不以某种方式与这些Y人匹配“,然后你添加到我们将有的事实几天后,当领导者调整名册时,实时进行相同的计算,然后出现了对快速解决方案的需求.

基本上,领导者会在屏幕上看到一个实时信息,说明有多少人仍在失踪,无论是在整个白班,还是有多少人符合各种标准,以及我们实际有多少人除了我们拥有的那些之外.这个显示器必须更新半实时,而领导者调整名单“如果詹姆斯采取白天而不是厄秀拉,而厄秀拉需要夜班”.

但是非常感谢到目前为止已经回答过这个问题的人,约束满足问题听起来像我们需要的方式,但我们肯定会在这里仔细查看所有的链接和算法名称.

这就是为什么我喜欢StackOverflow