采药

来自计算思维百科
跳转至: 导航搜索
采药1.png

辰辰是个很有潜能、天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要不同的时间,每一株也有它自身不同的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”

解决方案

方案一-贪心法

我们可以根据药材价值与采药时间的比值对各株药材从高到低进行排序,从比值最高的开始采摘,从而使得采到的药材价值最大。

运用的计算思维

贪心法根据局部最优选择来采取行动,通过每一步最优从而得到全局问题的最优解。这体现了计算思维的优化思想。

方案二-动态规划法

我们可以不要一次性考虑所有的药材,可以一个一个地考虑是否要采摘该药,采摘之后是否还有时间剩余,并且药材价值是否会上升,也即我们要比较以下两个选择的草药价值大小:

①如果不采摘当前药材,结果草药的最大价值;

②如果采摘了当前草药,当前所拥有的价值+在剩余时间采到的草药价值。

可以发现,每一次求取子问题,问题的规模就被缩小。要么在药材数量上减少,要么在时间上减少。最后任一为0,再逆向反推过去,就能逐步得到问题的解了。

运用的计算思维

动态规划法提供了以下思想指导:一项复杂的任务通常包括多个子任务,并且这些子任务之间通常有一定的联系,按照规模从小到大逐步完成这些子任务,直至目标任务是一种容易接受的、以渐进方式解决问题的有效方法。这体现了分解、规划的计算思维。

参考链接

http://zhidao.baidu.com/link?url=vt3V79_Vgps6rlS1-ifC-tJEXhYV8OnOEc8O1F372_k5-fXMWQcVkiPmKri9hm8j8GZCSN2qC93EopMvap1Lqq