algorithm - 具有多项分配的匈牙利算法

Question

假设我们有 N 个工作岗位和 K 个工作人员来完成这些工作。但对于某些工作，我们需要 2 名员工，而对于某些工作，我们只需要一名员工。员工也不能做所有的工作。例如， worker 1 可以做工作 1,2 和 5，而不能做工作 3 和 4。另外，如果我们雇用 worker 1 做工作 1，那么我们希望他做工作 2 和 5，因为我们已经付给他钱了。

例如，假设我们有 5 个职位和 6 个 worker 。对于工作 1,2 和 4，我们需要 2 个男人，而对于工作 3 和 5，我们只需要一个人。这里列出了每个 worker 可以做的工作以及他需要的工资。

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. 

经过一些计算和逻辑思考我们可以得出结论，我们要雇用 worker 1,3,4和5，这意味着我们需要支付的最低工资是:1000+1500+2500+1500=5500美元。

但是我们如何才能找到一种能够输出该数量的高效算法呢？这让我想起了匈牙利算法，但所有这些额外的限制使我无法应用它。

Answer 1

我们可以将所有工作的状态表示为三元系统中的一个数字(2-剩下两个人，1-剩下一个人，如果已经完成则为 0)。现在我们可以计算 f(mask, k) = 在前 k 个中雇用一些 worker 的最小成本，使得剩余工作的状态为 mask。转换如下:我们要么去 (mask, k + 1)(不雇用当前 worker )，要么我们去 (new_mask, k + 1)(在这种情况下，我们付给这个 worker 他的工资，让他做所有的工作他可以的工作)。答案是 f(0, K)。

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

这是一个如何进一步优化它的想法(并摆脱 N 因素)。假设当前面具是 mask 并且该人可以从另一个 mask' 开始工作。我们实际上可以简单地将 mask 添加到 mask'，但是有一个问题:mask< 中 2 的位置 和 mask' 中的 1 将被破坏。但我们可以修复:对于每个掩码，让我们预先计算一个二进制掩码 allowed_mask，其中包含数字不是 2 的所有位置。对于每个人和每个 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)(第一项用于预计算allowed_masks for所有三元掩码，第二个用于为所有 allowed_masks 和人员预计算 mask'，最后一个用于 dp 本身)。