Rya*_*yan 7 java algorithm scheduling dynamic-programming
我需要为调度问题设计一个有效的算法,我真的没有线索.
有一台机器以一定的速度生产药丸.例如,如果允许连续工作一天,机器可能能够生产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[]根据输入而变化.
找到最大治疗患者数的算法是什么？
这是一个很好的动态编程问题.
思考动态编程的方法是问自己两个问题:
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的情况,依此类推.但你也可以反过来做.本质上,这是一个相同的算法,就像你编写一个非常低效的递归解决方案一样,计算动态子问题的解决方案,除了你每次计算它时都缓存一个结果.所以它看起来像这样:
maxTreat(days, running)下一级子问题的答案.如果需要子问题的答案,请查看数组.如果那里有一个-1,你还没有解决那个,所以你递归解决它,然后把答案放到数组中.如果除了-1以外的任何东西,你可以使用你在那里找到的值,因为你已经计算过了.(您也可以使用a HashMap而不是多维数组.)这在某种程度上更好,在另一种情况下更糟.它更糟糕,因为你有与递归相关的开销,并且因为你最终会用递归调用耗尽堆栈.您可能需要使用命令行参数将堆栈大小提升到JVM.
但是在一个关键方面它更好:你不计算所有子问题的答案,而只计算你需要知道答案的答案.对于某些问题,这是一个巨大的差异,对某些人来说,事实并非如此.获得正确的直觉很难,但我认为这可能会产生很大的不同.毕竟,每个答案仅取决于前一行中的两个子问题.
最终的解决方案(不要尝试这个,直到你自上而下的递归递归!)是自上而下但没有递归.这样可以避免堆栈空间问题.要做到这一点,你需要创建一堆ArrayDeque需要解决的子问题(使用一个),然后继续将它们从队列的前面取下,直到没有剩下的为止.第一件事就是将需要解决方案的大问题推到堆栈上.现在,您迭代地从堆栈中弹出问题,直到它为空.弹出一个,然后打电话给它P.然后:
HashMap查看是否P已解决.如果是,请返回答案.P已经解决了子问题.如果他们有,那么你可以解决P,并缓存答案.如果堆栈现在为空,那么你已经解决了最后的问题,并输出了答案P.P回堆栈.然后将P尚未解决的任何子问题也推送到堆栈中.当您将主要问题及其子问题及其子问题推送到堆栈时,您的堆栈将最初增长.然后,您将开始解决较小的实例并将结果放入缓存中,直到最终您拥有解决主要问题所需的一切.
它不会使用比递归自顶向下方法少得多的内存,但它确实使用堆空间而不是JVM堆栈空间,这意味着它可以更好地扩展,因为JVM堆栈比堆小得多.
但这很困难.至少,在开始编写更难的版本之前,请保留您的工作解决方案!