主讲人：孙权
在对问题求解时，总是作出在当前看来是最
好的选择。也就是说，不从整体上加以考虑，
主讲人：孙权在对问题求解时，总是作出在当前看来是最
好的选择。也就是说，不从整体上加以考虑，
它所作出的仅仅是在某种意义上的局部最优
解（是否是全局最优，需要证明）。
[常见应用] 区间问题，最短路径，背包问题，最小生成树 特别注意
若要用贪心算法求解某问题的整体最优解，
必须首先证明贪心思想在该问题的应用结果
就是最优解！！ (eg:hdu2037)
设有n个活动E={1,2,…,n}要举办,设活动i的起止时
间区间[si, fi )。但只有一间会议室，so同一时间内只
允许一个活动使用该会议室. 求最多能举办的活动
数。 做法
将n个活动按结束时间非减序排列,依次考虑活动
i,若活动i与之前的活动不冲突，则更新结束时间，
并统计结果。
贪心思路
就是在尽量短的时间完成更多的活动。以便腾出
更多的时间来完成后面的活动。
有1元，5元，10元，50元，100元，500元的硬币
各有C1，C5，C10…C500枚，现在要用这些硬币支
付A元，求最小需要多少枚硬币？假定本题至少存
在一种支付方案。
这个题目想必大家都知道，尽量选择面值大的支付
即可。 上面的题目如果硬币面值为1，4，5，如果
支付8元，那么是否还可以用贪心！
这种问题就要用 动态规划了! 后面的专题会
讲到，这里暂时不讲！
一个长度为N（N<=1000）的字符串，每次可以
从队尾或队首拿出一个字符加入到新字符串队尾，
求字典序最小的新字符串.
贪心思路：每次从字符串两端同时搜索，将较小的
输入即可（如果相等继续比较下一个）！ HDU 1052 田忌赛马
-200
92 95 92 +200 95
-200
83 87 83 +200 87
-200
71 74 71 -200 74
谈谈自己的想法~~ Problem Title Difficulty Notes
1009 FatMouse' Trade Difficulty: 1
1045 Fire Net Difficulty:
贪心算法 来自淘豆网m.daumloan.com转载请标明出处.
