匈牙利算法多重分配

Question

匈牙利算法多重分配

algorithmoptimizationminimumhungarian-algorithm

7

假设我们有N个工作和K名工人来完成这些工作。但是对于某些工作，我们需要两名员工，而对于其他工作，我们只需要一名员工。此外，员工不能做所有的工作。例如，工人1可以做1、2和5号工作，但不能做3和4号工作。另外，如果我们雇用工人1来做工作1，则希望他也可以做2和5号工作，因为我们已经支付了他的报酬。

例如，假设我们有5个工作和6名工人。对于工作1、2和4，我们需要2个人，而对于工作3和5，我们只需要一名员工。以下是每个工人可以做的工作以及他所需的工资清单。

Worker 1 can do jobs 1,3,5 and he requires 1000 dollars. 
Worker 2 can do jobs 1,5 and he requires 2000 dollars. 
Worker 3 can do jobs 1,2 and he requires 1500 dollars. 
Worker 4 can do jobs 2,4 and he requires 2500 dollars. 
Worker 5 can do jobs 4,5 and he requires 1500 dollars. 
Worker 6 can do jobs 3,5 and he requires 1000 dollars.

经过简单的计算和逻辑思考，我们可以得出我们需要雇佣1、3、4、5号工人，这意味着我们需要支付的最低工资是：1000+1500+2500+1500=5500美元。

但是如何找到一个高效的算法来输出这个金额呢？这让我想起了匈牙利算法，但所有这些额外的限制条件使我无法应用它。

- Stefan4024

你真的需要解决这个问题吗？看起来像是一道作业题，而你正在尝试进行复杂的优化。如果是这样，请用缓慢/简单的方式完成并提交。我怀疑这个讨论会很复杂和/或耗时。 - Mooing Duck

如果我们雇佣工人1来做工作1，那么我们希望他做工作2和5，因为我们已经付过他钱了。难道你不是要分别为每份工作支付他的费用吗？还是说你是想让他以$1000完成所有三个工作？ - Yay295

N和K可以有多大？ - kraskevich

@kraskevich N <= 8，而K<= 60 - Stefan4024

说工人1能做3种不同的工作，是否意味着他也有时间完成所有这些工作？例如，如果一个人完成一项工作需要0.5天，那么工人1可以完成他能够做的任何2项工作，但你仍然需要雇用另一个工人来完成最后一项工作。 - H W

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kraskevich · Accepted Answer

我们可以将所有工作的状态表示为三进制系统中的数字（2-剩余两个人，1-剩余一个人，0-已完成）。现在我们可以计算f(mask, k)=在前k个人中以这种方式雇用一些工人的最小成本，使剩余工作的状态为mask。转换如下：我们要么转移到(mask, k+1)（不雇用当前工人），要么转移到(new_mask, k+1)（在这种情况下，我们支付该工人的薪水并让他做他能做的所有工作）。答案是f(0, K)。

时间复杂度为O(3^N * K * N)。

以下是进一步优化的想法（并消除N因素）。假设当前掩码为mask，人员可以从另一个mask'中执行作业。实际上，我们可以简单地将mask添加到mask'中，但有一个问题：mask中为2而mask'中为1的位置将被破坏。但我们可以修复：对于每个mask，让我们预先计算一个包含所有数字不为2的位置的二进制掩码allowed_mask。对于每个人和每个allowed_mask，我们都可以预先计算出mask'值。现在每个转换只需要进行一次加法。

for i = 0 ... k - 1
    for mask = 0 ... 3^n - 1
        allowed_mask = precomputed_allowed_mask[mask]
        // make a transition to (i + 1, mask + add_for_allowed_mask[i][allowed_mask])
        // make a transition to (i + 1, mask)

请注意，只有2^n个允许的掩码。因此，这个解决方案的时间复杂度为O(3^N * N + T * 2^N * K * N + T * 3^N * K)（第一个术语是为所有三进制掩码预先计算允许的掩码，第二个术语是为所有允许的掩码和人员预先计算mask'，最后一个术语是DP本身）。