贪心算法例题

一、货币选择问题
题目：别有1,5,10,50,100元，分别有a,b,c,d张纸币。问若要支付k元，求所需最少纸币数？
方法：先从面值大的开始开始计算，能用100的就尽量用100，再依次用50，10，5，1。
例如：187=1001+501+103+51+1*2
一共需要8张。
二、区间调度问题
题目：
有n项工作，每项工作分别在Si开始，Ti结束。对每项工作，你都可以选择与否，若选择参加，则必须至始至终参加全程参与，且参与工作的时间段不能有重叠。求所能参加的最大的完整的工作数。
方法：定义每项工作的结构体，将所有结构体按结束时间从小到大排序，若结束时间相同，则按照开始时间从大到小排序。然后从第一个开始选择得到的工作数最多的。
三、多机调度问题
题目：
n个作业组成的作业集，可由m台相同机器加工处理。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业；每个作业均可在任何一台机器上加工处理。
方法：
这个问题是NP完全问题，还没有有效的解法(求最优解)，但是可以用贪心选择策略设计出较好的近似算法(求次优解)。
当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。即按照时间从大到小依次处理所花费时间最短。
四、区间覆盖问题
题目 ：
假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。

方法：以每个小岛为中心，做半径为d的圆，计算出它在x轴上上覆盖的长度。对于第一个需要一个雷达，如果两个区间相交而不重合，我们什么都不需要做；如果一个区间完全包含于另外一个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。