将正整数列表划分为 K 个子集，想要最小化子集和的最大值？

Question

问题陈述：
给定一个正整数列表，目标是将列表划分为

K

子集，以使这些子集之间的最大和最小化。

这个问题可以在任务调度领域中具体化。想象一下有

K

相同的工人和

n

任务。每项任务都需要特定的正整数时间才能完成。目标是找到工作人员之间任务的最佳调度，以最大限度地减少任何工作人员在分配的任务上花费的最大时间。

示例：
例如，考虑列表

[1, 2, 3, 4, 5]

和

K = 2

。最小可能的最大子集和是

8

。这可以通过优化划分为两个子集

[1, 2, 5]

和

[3, 4]

来实现。

背景：
今天面试的时候就遇到了这个问题。虽然我最初考虑使用回溯方法来解决这个问题，但面试官正在寻找更有效的解决方案。我现在想知道是否有更有效的算法，可能涉及动态编程或贪婪方法。

Answer 1

调度并行相同机器以最小化完工时间 (P||C_max) 的问题是 NP 完全问题。这意味着不存在已知的有效算法来准确解决问题的大型实例。 因此，您能想到的任何可能的实现可能看起来都不会太高效（MIP 公式或 SAT 求解器是解决一般 MIP 问题的可能方法）。 有大量关于解决此类问题的方法的文献。您可以使用近似算法或启发式方法来寻找解决方案，但不能保证具有实际的最小值。我认为没有明显有效的实现来解决这个问题。您可以查看此参考资料了解更多详细信息。