面试题:简单讲一下贪心算法


解析:

贪心算法总是做出在当前看来最优的选择,并希望最后整体也是最优的。

使用贪心算法可以解决的问题必须具有如下两种特性:
1.最优子结构
2.问题的最优解包含其子问题的最优解

贪心选择:每一步的贪心选择可以得到问题的整体最优解。

实例-硬币选择问题

给定期望的硬币总和为 V 分,以及 n 种硬币,即类型是 i 的硬币共有 coinValue[i] 分,i的范围是 [0…n – 1]。

问:假设每种类型的硬币都有无限个,求解为使和为 V 分最少需要多少硬币?
硬币:便士(1美分),镍(5美分),一角(10美分),四分之一(25美分)。

假设总和 V 为41,我们可以使用贪心算法查找小于或者等于 V 的面值最大的硬币,然后从 V 中减掉该硬币的值,如此重复进行。

V = 41 | 使用了0个硬币
V = 16 | 使用了1个硬币(41–25=16)
V = 6 | 使用了2个硬币(16–10=6)
V = 1 | 使用了3个硬币(6–5=1)
V = 0 | 使用了4个硬币(1 –1=0)

66.png


课程链接:http://www.julyedu.com/weekend/train9?v=m1

大量学员拿到30-40万年薪

多位名校博士+BAT专家手把手教学

现在报名

送18VIP会员

[包2018全年在线课程和全年GPU]

前80人可享特惠价

0 个评论

要回复文章请先登录注册