algorithm - 一个强 worker 或多个弱 worker 可以解决的工作的最优分配

Question

我正在寻找一种实现最佳工作/员工分配的有效方法。我会使用匈牙利算法，但有一个问题:一个 worker 一次只能分配一个工作，每个工作都有一个评级，每个 worker 都有自己的评级。评级为 4 的工作可以由评级为 4 的 worker 或多个 worker 解决，他们的综合评级等于工作评级，例如2+2 或 3+1 或 2+1+1 或 1+1+1+1。评级为 2 的工作可以由评级为 1 的两名 worker 或评级为 2 的 worker 解决。我希望尽可能使用一对一分配。

在这种情况下，是否有任何已知的算法或任何简单的方法来实现最佳分配？

Answer 1

你的问题显然至少和 Partition Problem 一样难，甚至只是为了知道是否存在可行的解决方案。为了展示这一点，让我们有一个分区实例。通过创建两个作业和与分区问题中的元素数量一样多的 worker ，它可以很容易地转化为您的问题。每个作品的评分等于分区问题中相应元素的值。当且仅当分区问题有解时，你的问题才有解，从而证明你的问题是 NP 难的。