java - Java 中的作业调度算法

Question

我需要为调度问题设计一个有效的算法，但我真的没有任何线索。

有一种机器可以按一定的速度生产药丸。例如，机器连续工作一天可以生产1粒，连续工作3天可以生产4粒，连续工作5天可以生产16粒，以此类推。如果我停止机器并取出所有药丸，那么机器将从第 1 天再次启动。我从机器中取出的所有药丸必须在同一天使用。

每天都有一定数量的病人来吃药。患者必须在同一天接受治疗，未接受治疗的患者不予理会。目标是决定在哪几天停止机器并在 n 天内治疗尽可能多的患者。

假设天数 n = 5，给定示例输入

int[] machineRate = {1,2,4,8,16};
int[] patients =    {1,2,3,0,2};

在这种情况下，如果我在第 3 天停止机器，我将有 4 粒药丸。我可以治疗3个病人，扔掉1个药丸。然后我在第 5 天再次停止机器，因为它在第 3 天停止，它已经工作了 2 天，因此我有 2 粒药来治疗 2 个患者。最后3+2=5，输出=5个病人。

如果我在第 2 天、第 3 天、第 5 天停止机器。那么输出将是(第 2 天 2 位患者 2 粒)+(第 3 天 3 位患者 1 粒)+(第 2 天 2 位患者) 5)。这也等于 5 名患者。
machineRate[]和 patients[]因输入而异。

找到最大治疗患者人数的算法是什么？

Answer 1

这是一个很好的动态规划问题。

思考动态规划的方法是问自己两个问题:

如果我将一个(或多个)变量减少到零(或类似)，是否有这个问题的简单版本？

是否有一种简单的方法可以计算大小 n+1 的问题的答案？如果我知道所有大小问题的答案 n ? (此处，“大小”是特定于问题的，您需要找到有助于解决手头问题的正确大小概念。)

对于这个问题，什么是微不足道的版本？好吧，假设天数是 1。那么这很容易:我停止机器，并尽可能多地治疗患者。做其他事情没有意义。

现在，如果我们将剩余天数视为我们的大小概念，我们也可以得到第二个问题的答案。假设我们知道所有问题的所有答案 n还剩几天。让我们写信 maxTreat(days, running)如果有 days，我们可以处理的最大数量还剩几天，如果机器最初运行了 running天。

现在有n+1还剩几天；并且机器到目前为止已经运行了 k天。我们有两个选择:(1)停止机器； (2) 不要停止。如果我们停止机器，我们今天可以治疗一些病人(我们可以根据k算出数字)，然后我们可以治疗maxTreat(n, 1)患者，因为那时有 n还剩几天，到明天机器将再次运行一天。如果我们不停止机器，我们今天不能治疗任何人，但以后我们可以治疗maxTreat(n,k+1)患者，因为到明天机器将运行 k+1天。

我会让你计算出精确的细节，但为了有效地解决它，我们创建了一个多维数组，基于剩余天数和机器到目前为止运行的天数。然后我们遍历数组，解决所有可能的问题，从琐碎的(还剩一天)开始，然后倒推(两天，然后是三天，以此类推)。在每个阶段，我们要解决的问题要么是微不足道的(所以我们可以只写答案)，要么是我们可以根据我们在上一步写入数组的条目进行计算的问题。

动态编程真正酷的地方在于，我们正在创建所有结果的缓存。因此，对于递归方法最终需要多次计算子问题答案的问题，使用动态规划，我们永远不会多次解决子问题。

现在我已经看到了您的实现的其他评论:

首先，当你达到 10,000 左右时它开始放缓，我并不感到惊讶。算法是O(n^2) ，因为在每次迭代中，您必须用最多 n 填充数组进入下一级别之前。我很确定 O(n^2)不过，这是您将要为这个谜题获得的最佳渐近复杂性。

如果你想进一步加快速度，你可以看看自上而下的方法。目前您正在做自底向上的动态规划:解决大小为 0 的情况，然后大小为 1，依此类推。但是你也可以反过来做。本质上，这与编写一个非常低效的递归解决方案是相同的算法，该解决方案动态计算子问题的解决方案，只是每次计算结果时都会缓存结果。所以它看起来像这样:

设置您的二维数组以保存子问题的解决方案。对于每种情况，用 -1 预填充它。值为 -1 表示您尚未解决该子问题。

写一个程序来解决 maxTreat(days, running)在下一级子问题的答案方面。当您想要子问题的答案时，请查看数组。如果那里有 -1，则您还没有解决该问题，因此您递归解决它，然后将答案放入数组中。如果有除 -1 以外的任何值，您可以使用在那里找到的值，因为您已经计算过它。 (您也可以使用 HashMap 代替多维数组。)

这在一方面更好，另一方面更糟。更糟糕的是因为您有与递归相关的开销，并且因为您最终会因递归调用而耗尽堆栈。您可能需要使用 JVM 的命令行参数来增加堆栈大小。

但在一个关键方面更好:您不必计算所有子问题的答案，而只计算您需要知道答案的那些。对于某些问题，这是一个巨大的差异，而对于某些问题，则不然。很难获得正确的直觉，但我认为这可能会产生很大的不同。毕竟，每个答案仅取决于前一行的两个子问题。

最终的解决方案(不要尝试这个，直到你先得到自顶向下的递归!)是自顶向下但没有递归。这将避免堆栈空间问题。为此，您创建了一堆需要解决的子问题(使用 ArrayDeque )，并不断将它们从队列的前面移开，直到没有剩下的为止。第一件事是将需要解决方案的大问题推到堆栈中。现在，您迭代地从堆栈中弹出问题，直到它为空。弹出一个，并称之为 P .然后:

查看您的数组或 HashMap看看是否P已经解决。如果是，请返回答案。

如果没有，查看 P 的子问题是否存在已经解决了。如果他们有，那么你可以解决P ，然后缓存答案。如果堆栈现在是空的，那么您已经解决了最后一个问题，并且您输出了 P 的答案。 .

如果子问题还没有全部解决，则推P回到堆栈上。然后按任意一个 P的子问题尚未解决到堆栈中。

随着您的进行，您的堆栈最初会随着您将主要问题及其子问题，然后是其子问题插入堆栈而增长。然后您将开始解决较小的实例并将结果放入缓存中，直到最终您拥有解决主要问题所需的一切。

与递归自顶向下方法相比，它使用的内存并没有显着减少，但它确实使用了堆空间而不是 JVM 堆栈空间，这意味着它可以更好地扩展，因为 JVM 堆栈比堆小得多。

不过，这相当困难。至少，在开始编写更困难的版本之前，请保留您的工作解决方案!