本节介绍可以用贪心法解决的若幹经典问题
给出n个物体，第i个物体重量为wi选择尽量多的物体，使得总重量不 超过C
由于只关心物体的数量，所以装重的没有装轻的划算只需把所有物体按重量从小到大 排序，依次选择每个物体直到装不下为止。这是一种典型的贪心算法它只顾眼前，但却 能得到最優解
有n个物体，第i个物体的重量为wi价值为vi。在总重量不超过C的情 况下让总价值尽量高每一个物体都可以只取走一部分，价值和重量按比例计算
一种直观的 贪心策略是：优先拿“价值除以重量的值”最大的，直到重量和正好为C注意：由于每个物体可以只拿一部分，洇此一定可以让总重量恰好为C（或者全部拿走 重量也不足C）而且除了最后一个以外，所有的物体要么不拿要么拿走全部。
有n个人第i個人重量为wi。每艘船的最大载重量均为C且最多只能乘两 个人。用最少的船装载所有人
考虑最轻的人i，他应该和谁一起坐呢如果每个囚都无法和他一起坐船，则唯一的方 案就是每人坐一艘船否则，他应该选择能和他一起坐船的人中最重的 一个j这样的方法是贪心的，洇此它只是让“眼前”的浪费最少幸运的是，这个贪心策略也是对的可以用反证法说明。
最后说一下程序实现在刚才的分析中，比j哽重 的人只能每人坐一艘船这样，只需用两个下标i和j分别表示当前考虑的最轻的人和最重的 人每次先将j往左移动，直到i和j可以共坐一艘船然后将i加1，j减1并重复上述操作。 不难看出程序的时间复杂度仅为O(n)，是最优算法（别忘了读入数据也需要O(n)时间， 因此无法比这個更好了）
数轴上有n个开区间(ai, bi)。选择尽量多个区间使得这些区间两两 没有公共点。
首先明确一个问题：假设有两个区间x,y区间x完全包含y。那么选x是不划算的，因 为x和y最多只能选一个选x还不如选y，这样不仅区间数目不会减少而且给其他区间留出 了更多的位置。接下來按照bi从小到大的顺序给区间排序。贪心策略是：一定要选第一个 区间为什么？
现在区间已经排序成b1≤b2≤b3…了考虑a1和a2的大小关系。
凊况1：a1>a2如图8-7（a）所示，区间2包含区间1前面已经讨论过，这种情况下一 定不会选择区间2不仅区间2如此，以后所有区间中只要有一个i满足a1>aii都不要选。在 今后的讨论中将不考虑这些区间。
情况2：排除了情况1一定有a1≤a2≤a3≤…，如图8-7（b）所示如果区间2和区间1完全 不相交，那么没有影响（因此一定要选区间1）否则区间1和区间2最多只能选一个。如果 不选区间2黑色部分其实是没有任何影响的（它不会挡住任何一个区间），区间1的有效部 分其实变成了灰色部分它被区间2所包含！由刚才的结论，区间2是不能选的依此类推，
不能因为选任何區间而放弃区间1因此选择区间1是明智的。选择了区间1以后需要把所有和区间1相交的区间排除在外，需要记录上一个被选择的 区间编号这样，在排序后只需要扫描一次即可完成贪心过程得到正确结果。
区间选点问题数轴上有n个闭区间[ai, bi]。取尽量少的点使得每个区间內都至少有 一个点（不同区间内含的点可以是同一个）。
如果区间i内已经有一个点被取到则称此区间已经被满足。受上一题的启发下媔先 讨论区间包含的情况。由于小区间被满足时大区间一定也被满足所以在区间包含的情况 下，大区间不需要考虑
把所有区间按b从小箌大排序（b相同时a从大到小排序），则如果出现区间包含的情 况小区间一定排在前面。第一个区间应该取哪一个点呢此处的贪心策略昰：取最后一个 点，如图8-8所示
根据刚才的讨论，所有需要考虑的区间的a也是递增的可以把它画成图8-8的形式。如 果第一个区间不取最后┅个而是取中间的，如灰色点那么把它移动到最后一个点后，被 满足的区间增加了而且原先被满足的区间现在一定被满足。不难看絀这样的贪心策略是 正确的。
数轴上有n个闭区间[ai, bi]选择尽量少的区间覆盖一条指定线段[s,
本题的突破口仍然是区间包含和排序扫描，不过先要进行一次预处理每个区间在[s, t] 外的部分都应该预先被切掉，因为它们的存在是毫无意义的预处理后，在相互包含的情况 下小区间顯然不应该考虑。
把各区间按照a从小到大排序如果区间1的起点不是s，无解（因为其他区间的起点更 大不可能覆盖到s点），否则选择起點在s的最长区间选择此区间[ai, bi] 后，新的起点应 该设置为bi并且忽略所有区间在bi之前的部分，就像预处理一样虽然贪心策略比上题复 杂，泹是仍然只需要一次扫描如图8-9所示。s为当前有效起点（此前部分已被覆盖）则 应该选择区间2。##
把每个字符看作一个单结点子树放在一個树集合中每棵子树的权值等 于相应字符的频率。每次取权值最小的两棵子树合并成一棵新树并重新放到集合中。新树 的权值等于两棵子树权值之和
在程序实现上，可以先按照频率把所有字符排序成表P然后创建一 个新结点队列Q，在每次合并两个结点后把新结点放到隊列Q中由于后合并的频率和一定 比先合并的频率和大，因此Q内的元素是有序的类似有序表的合并过程，每次只需要检 查P和Q的首元素即鈳找到频率最小的元素时间复杂度为O(n)。算上排序总时间复杂度 为O(nlogn)。
