简介
贪心算法(greedy algorithm)，是用计算机来模拟一个“贪心”的人做出决策的过程。这个人很贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。
贪心算法只有在通过局部最优解可以得到全局最优解时才可以使用
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
贪心策略一旦经过证明成立后，它就是一种高效的算法。
基本思路
- 建立数学模型来描述问题；
- 把求解的问题分成若干个子问题；
- 对每一子问题求解，得到子问题的局部最优解；
- 把子问题的解局部最优解合成原来解问题的一个解
证明方法
贪心算法有两种证明方法：反证法和归纳法。一般情况下，一道题只会用到其中的一种方法来证明。
- 反证法：如果交换方案中任意两个元素/相邻的两个元素后，答案不会变得更好，那么可以推定目前的解已经是最优解了。
-
常见题型及解题方法
- “我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择。”
- “我们每次都取 XXX 中最大/小的东西，并更新 XXX。”（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）
二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择。
排序解法
用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值。
后悔解法
思路时无论当前的选项是否是最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃这个选项，否则就正式接受，如此往复。
与动态规划的区别
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
例题
分配场地问题
设有N个活动时间集合，每个活动都要使用同一个资源，比如说会议场，而且同一时间内只能有一个活动使用，每个活动都有一个使用活动的开始si和结束时间fi，即他的使用区间为（si,fi）,现在要求你分配活动占用时间表，即哪些活动占用该会议室，哪些不占用，使得他们不冲突，要求是尽可能多的使参加的活动最大化，即所占时间区间最大化！
这个就是最基本可贪心的题目，我们每次都找能让场地利用时间最大的解，然后整体就是最优解
先
排序
，按照开始时间从早到晚排序
然后从第二个开始，记录前一次结束的时间和当前开始时间，每次找开始时间大于或者等于上次结束时间的情况，记录下来就是结果
国王游戏
（排序法）
题目：
恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
分析
假设获得奖赏最多的大臣就是A、B中的某个人，A、B两人在中间某个位置，我们知道交换他们的位置既不影响他们前面的人也不影响后面人所得的金币，所以我们考虑两种情况，A在前或者B在前，并且其两个人前面的人左手乘积为
pro
那么A在前时：
A所得：
pro/RA
①
B所得：
pro*LA/RB
②
B在前时：
A所得：
pro*LB/RA
③
B所得：
pro/RB
④
规定A在B前面时，获得奖赏最多的大臣所获奖赏尽最少
则max(①，②)<=max(③，④)，又因为明显 ①<=③，②>=④
所以必定②<=③ 则有
LA*RA<=LB*RB
由于题目要求高精，本人目前太渣不会所以AC代码就不贴
(百度)
了
部分背包问题
首先介绍一下背包问题。
假设一共有N件物品，第 i 件物品的价值为 Vi ，重量为Wi，一个小偷有一个最多只能装下重量为W的背包，他希望带走的物品越有价值越好，请问：他应该选择哪些物品？
贪心策略是什么呢？将物品按单位重量 所具有的价值排序。总是优先选择单位重量下价值最大的物品。
单位重量所具有的价值：Vi / Wi
举个例子：假设背包可容纳50Kg的重量，物品信息如下：
| 物品 i | 重量(Kg) | 价值 | 单位重量的价值 |
|---|---|---|---|
| 1 | 10 | 60 | 6 |
| 2 | 20 | 100 | 5 |
| 3 | 30 | 120 | 4 |
按照我们的贪心策略，单位重量的价值排序： 物品1 > 物品2 > 物品3
因此，我们尽可能地多拿物品1，直到将物品1拿完之后，才去拿物品2…
最终贪心选择的结果是这样的：物品1全部拿完，物品2也全部拿完
物品3拿走10Kg（只拿走了物品3的一部分！！！）
这种情况下获得的价值是最大的
证明思路：先考察一个全局最优解，然后对该解加以修改(一般是采用“剪枝”技巧)，使其采用贪心选择，这个选择将原问题变成一个相似的、但是更小的问题。
对于0-1背包问题， 一件物品要么拿，要么不拿，不能只拿一部分，
这时如果我们还利用贪心去操作，物品三无法装下，得到的总价值160，但是如果拿物品2或者物品3，得到总价值220
_
这说明，该贪心策略对0-1背包问题，不能求得最优解。
待更。。。