贪心算法是从问题的初始状态出发，通过若干次的贪心选择而得出最优值（或较优值）的一种方法。
贪心策略并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
贪心算法的特点
- 1.贪心选择性质：所谓贪心选择性质是指应用同一规划，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未做的选择。
- 2.最优子结构性质：算法中每一次都取得了最优解(即局部最优解)，要保证最后的结果最优，则必须满足全局最优解包含局部最优解。
几个简单的贪心例子
- 1.最优装载问题：
给n个物体，第i个物体重量为wi，选择尽量多的物体，使得总重量不超过C。
【问题分析】
贪心策略：先装最轻的。- 2.部分背包问题：
有n个物体，第i个物体的重量为wi，价值为vi，在总重量不超过C的情况下让总价值尽量高。每一个物体可以只取走一部分，价值和重量按比例计算。
【问题分析】
贪心策略：先拿性价比高的。
- 3.乘船问题：
有n个人，第i个人重量为wi。每艘船的载重量均为C，最多乘两个人。用最少的船装载所有人。
【问题分析】
贪心策略：最轻的人和最重的人配对。
贪心的经典应用：
- 1.选择不相交区间问题：给定n个开区间(ai,bi)，选择尽量多个区间，使得这些区间两两没有公共点。
【算法】
首先按照结束时间b1<=b2<=…<=bn的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。
【正确性】
假设bj<bi且(aj,bj)(ai,bi)分别与之前的活动不冲突，如果当前选(aj,bj)，若(aj,bj)(ai,bi)不冲突则还可以选择(ai,bi)，答案加一；若(aj,bj)(ai,bi)冲突，因为bj<bi，所以(aj,bj)对以后的影响更小。
- 2、区间选点问题：给定n个闭区间[ai, bi]，在数轴上选尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。
【算法】
首先按照结束位置从小到大排序。然后从区间1到区间n进行选择：对于当前区间，若集合中的数不能覆盖它，则将区间末尾的数加入集合。
贪心策略是：取最后一个。
如下图，如果选灰色点，则移动到黑色点会更优。
- 3、区间覆盖问题：给n个闭区间[ai,bi]，选择尽量少的区间覆盖一条指定线段[s,t]。
【算法】
将所有的区间按左端点从小到大排序，依次处理每个区间。每次选择覆盖点s的区间中右端点坐标最大的一个，并将s更新为该区间的右端点坐标，直到选择的区间已包含了t为止。
贪心思想：在某个时刻s，找一个满足a[i]<=s的b[i]最大值即可。
- 4、流水作业调度问题：问题描述 某工厂收到了n个产品的订单,这n个产品分别在A、B两个车间加工,并且必须先在A车间加工后才可以到B车间加工。 某个产品i在A、B两车间加工的时间分别为ai、bi。怎样安排这n个产品的加工顺序,才能使总的加工时间最短。这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在A、B两车间加工完毕的时间。
【算法分析】
要使时间最短，则就是让机器的空闲时间最短。
B机器在加工过程中，有可能要等待A机器。
最后一个部件在B机器上加工，A机器也在等待B机器的完工。
要使总的空闲时间最少，就要把在A机器上加工时间最短的部件最先加工，这样使得B机器能以最快的速度开始加工；把在B机器上加工时间最短的部件放在最后加工。这样使得A机器能尽快的等待B机器完工。
于是我们可以设计出这样的贪心法：
设Mi=min{ai, bi}
将M按照从小到大的顺序排序。然后从第1个开始处理，若Mi=ai，则将它排在从头开始的作业后面，若Mi=bi，则将它排在从尾开始的作业前面。
- 5、带限期和罚款的单位时间任务调度 问题：有n个任务，每个任务都需要1个时间单位执行，任务i的截止时间di(1<=di<=n)表示要求任务i在时间di结束时必须完成，误时惩罚wi表示若任务i未在时间di结束之前完成，将导致wi的罚款。 确定所有任务的执行顺序，使得惩罚最小。
【贪心方法】
要使罚款最少，我们显然应尽量完成w[i]值较大的工作。
此时，我们可以将工作按w[i]从大到小进行排序，然后按照排好的顺序依次对工作进行安排，安排的规则为：使处理工作i的时间既在d[i]之内，又尽量靠后；如果d[i]之内的时间都已经排满，就放弃处理此项工作。