7

假设我们有 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 美元。

但是我们怎样才能找到一个有效的算法来输出这个数量呢？这不知何故让我想起了匈牙利算法，但所有这些额外的约束让我无法应用它。

4

1 回答 1

2

我们可以将所有工作的状态表示为三元系统中的一个数字（2-2 人剩余，1-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'，但有一个问题：存在2于mask和1中的位置mask'会被破坏。但是我们可以修复：对于每个掩码，让我们预先计算一个二进制掩码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，第二项是为mask'所有 allowed_masks 和人员预计算，最后一项是 dp 本身）。

于 2015-04-09T23:49:12.140 回答