递归与一维数组

Question

我一直盯着这个问题几个小时。出于某种原因，我理解洪水填充和二维阵列递归，但似乎无法开始在这个问题上：

你有三个助理为你工作。一个叫杰夫，另一个叫杰夫，第三个叫杰夫。它们都以每分钟一页的速度打印。你今天带着一大堆你需要尽快输入的文件来到你的办公室。你必须将这些文件分发给你的助手，以便他们尽早完成所有文件。 “杰夫做到了，”你大叫。 “杰夫那样做，”你说。 “杰夫，完成这项工作，”你警告。所以杰夫做到了。但你需要帮助他。所以你有这个APT。

你的任务是给定一个int []和每张纸的页数，返回你的助手键入所有这些纸张所需的最少分钟数。假设他们不能将一张纸分成几部分，即每张纸由一个人打印。例如，给定{1,2,3,4,5,6,7}，函数应返回10，因为7 + 3 = 10,6 + 2 + 1 = 9和5 + 4 = 9（还有这些数字的其他组合将产生相同的结果）。

Answer 1

你的任务基本上是解决分区问题。

https://en.wikipedia.org/wiki/Partition_problem

因为这个任务是NP完全问题，不能在多项式时间内解决（最佳）。解决方案只能近似。

最简单的apprach将是贪心算法：

首先，你在降序排序表。之后，您可以遍历它，将任务分配给目前为止分配工作量最少的Jeffs。

无需递归。