寻找最大的幸福总和
Finding maximal sum of happiness
我有一个问题要解决，但没有看到任何最佳解决方案：/问题是：
我有 n 个工人和 k 个工作。每项工作都由指定数量的工人完成，每个工人对每项工作都有自己的幸福水平。我必须制定一个工作时间表，让工人们尽可能开心。
所以，我有 int[n,k] (k >= n) 的数组 a1。第 i 行的第 k 列包含第 i 个工人对第 k 个工作的偏好（从 0 到 10 的数字）。我还有 int[k] 数组 a2，其中第 i 个元素包含将从事该工作的人数。每个工人要完成相同数量的工作。我必须找到最大可能的幸福总和，知道 n >= max(a2)。
我的解决方案是使用递归。 Select 第一个工作组合的第一个工人，将偏好添加到总和，检查总和是否高于已经找到的最大值，如果是，则转到下一个工人。返回时，检查第一个工人的下一个组合等。这适用于少量工人，但必须具有高计算复杂性才能解决更大的问题。您有更好的解决方案吗？
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
使用匈牙利算法的方法是为作业 i 创建 a2[i] 个顶点。希望 a2 数组总和为 n。如果 k << n，那么您最好将其表述为最小成本循环问题。
在我看来这像是交通问题。不过，它可以使用匈牙利算法来解决。首先让我们为匈牙利算法设置矩阵。
匈牙利算法用于寻找最小和。要使其解决最大和问题，您首先必须反转所有幸福值。
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 个。
我有一个问题要解决，但没有看到任何最佳解决方案：/问题是：
我有 n 个工人和 k 个工作。每项工作都由指定数量的工人完成，每个工人对每项工作都有自己的幸福水平。我必须制定一个工作时间表，让工人们尽可能开心。 所以，我有 int[n,k] (k >= n) 的数组 a1。第 i 行的第 k 列包含第 i 个工人对第 k 个工作的偏好（从 0 到 10 的数字）。我还有 int[k] 数组 a2，其中第 i 个元素包含将从事该工作的人数。每个工人要完成相同数量的工作。我必须找到最大可能的幸福总和，知道 n >= max(a2)。 我的解决方案是使用递归。 Select 第一个工作组合的第一个工人，将偏好添加到总和，检查总和是否高于已经找到的最大值，如果是，则转到下一个工人。返回时，检查第一个工人的下一个组合等。这适用于少量工人，但必须具有高计算复杂性才能解决更大的问题。您有更好的解决方案吗？
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
使用匈牙利算法的方法是为作业 i 创建 a2[i] 个顶点。希望 a2 数组总和为 n。如果 k << n，那么您最好将其表述为最小成本循环问题。
在我看来这像是交通问题。不过，它可以使用匈牙利算法来解决。首先让我们为匈牙利算法设置矩阵。
匈牙利算法用于寻找最小和。要使其解决最大和问题，您首先必须反转所有幸福值。
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 个。