用大体相同的"sum“将一列数字划分为较小的列表

Question

我在网格上执行了大约2000个测试，每个测试在网格上作为单独的任务运行。测试确实有相当长的启动时间。总执行时间为500小时，在60节点SunGridEngine上不到10小时即可完成。测试的运行时间从5分钟到90分钟不等。在没有太多智能的情况下组合测试可以获得一些性能增益。我想创建大小大致相等的“任务”。我如何做到这一点呢？

(我们现在做的是:对所有测试进行排序，并不断添加，直到执行时间总和约为5小时。寻找更好的东西)

Answer 1

以最佳方式进行此操作是NP完全的。这是partition problem的一个变体，它是subset sum problem的一个特例，它本身也是knapsack problem的一个特例。

在您的情况下，您可能不需要确切的解决方案，因此您可能可以使用一些启发式方法在合理的时间内获得“足够好”的结果。有关一些方法的描述，请参阅分区问题页面的Methods部分。

Answer 2

你要找的是k集的划分问题。

有一些关于k=3的文献，称为3-分区问题。这是强意义上的NP完全。

有许多启发式方法可以快速给出近似结果。

我建议你从这里开始：http://en.wikipedia.org/wiki/Partition_problem

希望这能有所帮助。

Answer 3

这是子集和问题的a version，并且是NP-完全的。你最好的办法就是雇佣一些subset-sum heuristics。