algorithm - 调度:将一组整数划分为 K 个子集

Question

我正在处理任务调度程序并遇到以下问题(处理器之间的任务分配):

有一组 N 个整数。如何将它们分成 K 个不相交的子集，它们的总和相差很小？

我正在寻找一种简单的启发式算法，该算法对于 N=100-500 和 K=10-20 具有合理的计算复杂度。不需要最优解(即和的最小可能差异)，粗略的近似就足够了。

提前致谢。

Answer 1

构造启发式 First Fit或 First Fit Decreasing工作顺利。

对于 First fit Decreasing，首先将零件按尺寸递减排序(在下面的示例中:A、B、C、D)，然后将它们一个一个地放在最佳剩余位置(X 或 Y)中。在下面的示例中，忽略 2 个维度中的 1 个(例如，忽略 CPU)。