我需要为调度问题设计一种有效的算法，但我确实没有任何线索。
有一种机器可以一定速度生产药丸。例如，如果允许该机器连续工作一天，则该机器可能能够生产1颗药丸；如果允许其连续工作3天，则可能产生4颗药丸；如果允许其连续工作5天，则可能产生16颗药丸，依此类推。如果我停止机器并取出所有药丸，那么机器将从第一天开始重新启动。我从机器中取出的所有药丸必须在同一天使用。
每天都有一定数量的患者来吃药。患者必须在同一天接受治疗，未治疗的患者将被忽略。目的是决定在哪几天停止机器并在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[]根据输入而变化。
找到最大治疗人数的算法是什么？
参考方案
这是一个很好的动态编程问题。
考虑动态编程的方法是问自己两个问题：
如果我将一个（或多个）变量减小为零（或类似值），是否会出现此问题的琐碎版本？
如果我知道所有大小为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堆栈比堆小得多。
但是，这非常困难。至少，在开始编写更困难的版本之前，请保留您可用的解决方案！
Java:线程池如何将线程映射到可运行对象 - java试图绕过Java并发问题，并且很难理解线程池，线程以及它们正在执行的可运行“任务”之间的关系。如果我创建一个有10个线程的线程池，那么我是否必须将相同的任务传递给池中的每个线程，或者池化的线程实际上只是与任务无关的“工人无人机”可用于执行任何任务？无论哪种方式，Executor / ExecutorService如何将正确的任务分配给正确的线程？ 参考方案 …
JAVA:字节码和二进制有什么区别？ - javajava字节代码（已编译的语言，也称为目标代码）与机器代码（当前计算机的本机代码）之间有什么区别？我读过一些书，他们将字节码称为二进制指令，但我不知道为什么。 参考方案 字节码是独立于平台的，在Windows中运行的编译器编译的字节码仍将在linux / unix / mac中运行。机器代码是特定于平台的，如果在Windows x86中编译，则它将仅在Win…
java:继承 - java有哪些替代继承的方法？ java大神给出的解决方案 有效的Java：偏重于继承而不是继承。 （这实际上也来自“四人帮”）。他提出的理由是，如果扩展类未明确设计为继承，则继承会引起很多不正常的副作用。例如，对super.someMethod()的任何调用都可以引导您通过未知代码的意外路径。取而代之的是，持有对本来应该扩展的类的引用，然后委托给它。这是与Eric…
Java:BigInteger，如何通过OutputStream编写它 - java我想将BigInteger写入文件。做这个的最好方式是什么。当然，我想从输入流中读取（使用程序，而不是人工）。我必须使用ObjectOutputStream还是有更好的方法？目的是使用尽可能少的字节。谢谢马丁 参考方案 Java序列化（ObjectOutputStream / ObjectInputStream）是将对象序列化为八位字节序列的一种通用方法。但…
Java DefaultSslContextFactory密钥库动态更新 - java我有一个使用org.restlet.engine.ssl.DefaultSslContextFactory的现有应用程序和一个在服务器启动时加载的密钥库文件。我有另一个应用程序，该应用程序创建必须添加的证书服务器运行时动态地更新到密钥库文件。为此，我在代码中创建了证书和私钥，然后将其写入到目录。该目录由bash脚本监视，该脚本检查是否有新文件，如果出现，它将…