安排 k 个任务的完成时间为 w(k) 和 N 个工作人员，单个工作人员中不会出现任何乱序的任务

Question

假设我有几项长度不均匀的任务。例如，令

k=8

和

w(k)=[4,5,3,10,1,1,1,3]

。我如何将这些分配给

N=3

工作人员，以便分配给给定工作人员的任何任务都是连续的，同时最大限度地减少分配给每个工作人员的权重差异？

例如在上面的例子中，如果我们分配类似

{0,1,2}, {3}, {4,5,6,7}

的任务，那么工人将不得不分别完成

4+5+3=12, 10=10, 1+1+1+3=6

单位的工作，最大不平衡为

12-6=6

。

我依稀记得算法类中有类似的东西（也许是背包问题？），但这里额外的问题是工人内部的顺序必须是连续的。是否存在找到该问题的最佳或相当好的解决方案的算法？

Answer 1

算法：

将任务按照权重递减的顺序进行排序。

以循环方式从权重排序列表中分配任务。

将分配给每个工人的任务重新排序为所需的顺序