有一台机器以一定的速度生产药丸.例如,如果允许连续工作一天,机器可能能够生产1个药丸,如果允许连续工作3天,则可以生产4个药丸,如果它可以工作5天,则可以生产16个药丸,等等.如果我停止机器并取出所有药丸,那么机器将从第1天开始.我从机器取出的所有药丸必须在同一天使用.
每天有一定数量的患者来吃药.患者必须在同一天进行治疗,未经治疗的患者将被忽略.目标是确定停止机器的天数并在n天内尽可能多地治疗患者.
假设示例输入的天数n = 5
int[] machineRate = {1,2,4,8,16};
int[] patients = {1,3,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名患者2粒) .这相当于5名患者.
machineRate []和患者[]根据输入而变化.
找到最大治疗患者数的算法是什么？
解决方法
思考动态编程的方法是问自己两个问题：
>如果我将一个(或多个)变量减少到零(或类似),是否存在这个问题的简单版本？
>如果我知道大小为n的所有问题的答案,是否有一种简单的方法来计算大小为n 1的问题的答案？ (这里,“大小”是特定于问题的,您需要找到有助于解决问题的大小的正确概念.)
对于这个问题,什么是一个简单的版本？好吧,假设天数为1.那么这很容易：我停止机器,尽可能多地治疗病人.做其他事情毫无意义.
现在,如果我们考虑剩下的天数作为我们的大小概念,我们也会得到第二个问题的答案.假设我们知道剩下n天的所有问题的所有答案.让我们写出maxTreat(天数,运行),如果还有几天的话,我们可以处理的最大数量,以及机器最初是否已经运行了几天.
现在还剩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(天,运行)问题.如果需要子问题的答案,请查看数组.如果那里有一个-1,你还没有解决那个,所以你递归地解决它,然后把答案放到数组中.如果除了-1以外的任何东西,你可以使用你在那里找到的值,因为你已经计算过了. (您也可以使用HashMap而不是多维数组.)
这在某种程度上更好,在另一种情况下更糟.它更糟糕,因为你有与递归相关的开销,并且因为你最终会用递归调用耗尽堆栈.您可能需要使用命令行参数将堆栈大小提升到JVM.
但是在一个关键方面它更好：你不计算所有子问题的答案,而只计算你需要知道答案的答案.对于一些问题,这是一个巨大的差异,对某些人来说,事实并非如此.获得正确的直觉很难,但我认为这可能会产生很大的不同.毕竟,每个答案仅取决于前一行中的两个子问题.
最终的解决方案(不要尝试这个,直到你自上而下的递归递归！)是自上而下但没有递归.这样可以避免堆栈空间问题.要做到这一点,你需要创建一堆需要解决的子问题(使用ArrayDeque),然后继续将它们从队列的前面取下,直到没有剩下的为止.第一件事就是将需要解决方案的大问题推到堆栈上.现在,您迭代地从堆栈中弹出问题,直到它为空.弹出一个,然后称之为P.然后：
>查看数组或HashMap以查看P是否已解决.如果是,请返回答案.
>如果不是,请查看P的子问题是否已经解决.如果有,则可以解决P,并缓存答案.如果堆栈现在为空,那么您已经解决了最后的问题,并输出了P的答案.
>如果子问题尚未全部解决,则将P推回堆栈.然后将P中尚未解决的任何子问题也推送到堆栈中.
当你将主要问题及其子问题及其子问题推入堆栈时,你的堆栈最初会发生什么变化.然后,您将开始解决较小的实例并将结果放入缓存中,直到最终您拥有解决主要问题所需的一切.
它不会使用比递归自顶向下方法少得多的内存,但它确实使用堆空间而不是JVM堆栈空间,这意味着它可以更好地扩展,因为JVM堆栈比堆小得多.
但这很难.至少,在开始编写更难的版本之前,请保留您的工作解决方案！
