贪心算法
在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。
1.区间调度问题
假设有如下课程,希望尽可能多的将课程安排在一间教室里:
|课程|开始时间 |结束时间
|–|–|–|
| 美术 | 9AM |10AM|
英语|9:30AM|10:30AM|
数学|10AM|11AM|
计算机|10:30AM|11:30AM|
音乐|11AM|12AM|
算法设计:
- 1.选择结束最早的课,便是要在这教室上课的第一节课
- 2.接下来,选择第一堂课结束后才开始的课,并且结束最早的课,这将是第二节在教室上的课。
代码:
1 | import java.util.*; |
相同问题:2019届爱奇艺校招笔试题第三题_库特君的面条: https://blog.csdn.net/qq_17556191/article/details/95003363
2.背包问题
见:https://blog.csdn.net/qq_17556191/article/details/94764606
3.集合覆盖问题
假设存在如下表的需要付费的广播台,以及广播台信号可以覆盖的地区。 如何选择最少的广播台,让所有的地区都可以接收到信号。
|广播台|覆盖地区 |
|–|–|
| K1 |ID,NV,UT |
K2|WA,ID,MT|
K3|OR,NV,CA|
K4|NV,UT|
K5|CA,AZ|
…|…|
算法设计:
(1) 选出一个广播台,即它覆盖了最多未覆盖的地区即便包含一些已覆盖的地区也没关系
(2) 重复第一步直到覆盖了全部的地区
1 | import java.util.*; |
4.旅行商问题
给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。
算法设计:
随机选一个城市开始,以寻找离该城市最近点作为下一个城市旅行城市,此后寻找离最后加入路线的城市最近的城市,直到最后。【类似于广度优先遍历】
1 | //旅行商问题 |
5.哈夫曼构造价值树
哈夫曼见: https://blog.csdn.net/likunkun__/article/details/80258515
相同题型:切金条: https://blog.csdn.net/qq_34115899/article/details/79723970
参考:图解贪婪算法 https://blog.csdn.net/a8082649/article/details/82079779