具有多个赋值的匈牙利算法

Question

假设我们有N个工作岗位和K工人做这些工作.但对于一些工作,我们需要2名员工,而对于一些人,我们只需要一名.员工也无法完成所有工作.例如,工人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美元.

但是我们如何才能找到一个可以输出该数量的高效算法呢？这让我想起了匈牙利算法,但所有这些额外的约束使我无法应用它.

Answer 1

我们可以将所有工作的状态表示为三元系统中的一个数字（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到，但是有一个问题：和in中mask'的位置将会被破坏。但我们可以修复：对于每个掩码，让我们预先计算一个二进制掩码，其中包含该数字不是 的所有位置。对于每个人和每个人，我们都可以预先计算该值。现在每个转换都只是一个补充：2mask1mask'allowed_mask2allowed_maskmask'

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)（第一项是预计算所有三元掩码的 allowed_masks，第二项是预计算mask'所有 allowed_masks 和人员，最后一项是预计算 dp 本身）。