0

我有一个问题要解决，但没有看到任何最佳解决方案：/问题是：

我有 n 个工人和 k 个工作。每项工作都由指定数量的工人完成，每个工人对每项工作都有自己的幸福程度。我必须制定一个工作时间表，以便工人尽可能快乐。所以，我有 int[n,k] (k >= n) 的数组 a1。第 i 行的第 k 列包含第 i 个工人对第 k 个工作的偏好（数字从 0 到 10）。我还有 int[k] 的数组 a2，其中第 i 个元素包含将从事这项工作的人数。每个工人要做相同数量的工作。我必须找到最大可能的快乐总和，知道 n >= max(a2)。我的解决方案是使用递归。为第一个工作组合选择第一个工人，将偏好添加到总和中，检查总和是否高于已找到的最大值，如果是，则转到下一个工人。回来时，检查第一个工人等的下一个组合。这适用于少量工人，但必须有很高的计算复杂度才能解决更大的问题。您对更好的解决方案有任何想法吗？

PS。另一个站点的人推荐我使用匈牙利算法，但它假设 n == k，我不知道如何使它与 n <= k 一起使用

PS2 一个例子：

a1:
         job1 job2 job3 job4
wokrer1    1    3    4    2
worker2    9    8    1    2        
worker3    6    7    8    9

a2:
       job1 job2 job3 job4
count    1    2    2    1

example solution:
worker1: job2, job3 (7)
worker2: job1, job2 (17)
worker3: job3, job4 (17)

sum: 41
4

2 回答 2

1

这对我来说就像运输问题。不过可以使用匈牙利算法来解决。首先让我们为匈牙利算法设置矩阵。

匈牙利算法用于找到最小和。要使其解决最大和问题，您首先必须反转所有幸福值。

    J1  J2  J3  J4
W1   1   3   4   2
W2   9   8   1   2
W3   6   7   8   9

用矩阵中的最大值减去每个值。
这个矩阵的最大值是 9。

      J1    J2    J3    J4
W1   9-1   9-3   9-4   9-2
W2   9-9   9-8   9-1   9-2
W3   9-6   9-7   9-8   9-9

    J1  J2  J3  J4
W1   8   6   5   7
W2   0   1   8   7
W3   3   2   1   0

现在，正如您所指出的，匈牙利算法仅适用于方阵。为了使它在矩形矩阵上工作，我们必须使它成为正方形。我们可以通过添加用零填充的虚拟行或列来做到这一点。

    J1  J2  J3  J4
W1   8   6   5   7
W2   0   1   8   7
W3   3   2   1   0
WD   0   0   0   0

现在我们有了可用的形式，我们可以求解最小总和。我将跳到解决方案，因为有关如何使用匈牙利算法的说明在其他地方很容易获得。

W1 -> J3
W2 -> J1
W3 -> J4
WD -> J2 (Except this is a dummy row so it doesn't count.)

我们现在为每个工人分配了一份工作。这是您的第二个阵列发挥作用的地方。

J1  J2  J3  J4
 1   2   2   1

我们已经为工作 1、3 和 4 分配了一个工人，因此我们将从它们各自的值中减去 1。

J1  J2  J3  J4
 0   2   1   0

由于我们不再需要任何人来完成工作 1 或 4，我们也可以从幸福矩阵中删除他们的列。

    J2  J3
W1   6   5
W2   1   8
W3   2   1

不过我们还有工作要做，所以我们再次经历这个过程。

添加虚拟列以使矩阵成为正方形。

    J2  J3  JD
W1   6   5   0
W2   1   8   0
W3   2   1   0

并解决。请记住，这些列是针对作业 2 和 3，而不是针对 1 和 2。

W1 -> JD
W2 -> J2
W3 -> J3

我们现在已经完成了两次算法，并分配了五个工作。

W1 -> J3
W2 -> J1, J2
W3 -> J4, J3

我们现在将再次经历整个过程。由于只有一个工作要分配，而且要分配给一个人（W1 只分配了一个工作，但它们都必须分配相同的编号。），我们可以直接去我们的最终解决方案。

W1 -> J3, J2
W2 -> J1, J2
W3 -> J4, J3

幸福值是：

W1 -> 4 + 3 =  7
W2 -> 9 + 8 = 17
W3 -> 9 + 8 = 17

总共41个。

于 2015-03-15T04:27:46.930 回答
0

使用匈牙利算法的方法是a2[i]为 job 制作顶点i。希望a2数组总和为n. 如果k << n，那么您最好将其表述为最小成本流通问题。

于 2015-03-14T14:54:55.507 回答