一、背景
在软考的准备中。遇到了算法。听过来人收。算法研究好了就非常easy，研究不好就认为非常难。于是想着对算法做个总结。由于算法不只在大题中占有15分，并且在选择题中相同也会出现。尤其是考复杂度和各种算法的适用情况，
贪心（目光短浅）：就像找男女朋友一样，不求最好。仅仅求合适（可行解）
二、怎样知道在某种情况下用贪心是合适的呢？
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上。贪心算法适用的情况非常少。一般，对一个问题分析是否适用于贪心算法，能够先选择该问题下的几个实际数据进行分析，就可做出推断。
三、贪心算法实现的基本步骤：
1、候选集合(C)
通过一个候选集合C作为问题的可能解。（终于解均取自于候选集合C）
比如。在找零钱问题中。各种面值的货币构成候选集合。
2、解集合(S)
每完毕一次贪心选择，将一个解放入S，终于获得一个完整解S
3、解决函数(solution)
检查解集合S是否构成问题的完整解。
比如，在找零钱问题中。解决函数是已付出的货币金额恰好等于应付款。
4、选择函数(select)
即贪心策略。这是贪心法的关键，选择出最有希望构成问题的解的对象。（这个选择函数通常和目标函数有关）
比如，在找零钱问题中，贪心策略就是在候选集合中选择面值最大的货币。
5、可行函数(feasible)
检查解集合中增加一个候选对象是否可行。（增加下一个对象后是不是满足约束条件）
比如，在找零钱问题中。可行函数是每一步选择的货币和已付出的货币相加不超过应付款。
四、贪心算法的实现框架
从问题的某一初始解出发；
while （能朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由全部解元素组合成问题的一个可行解；
用C解释例如以下：
<span style="font-size:14px;">Greedy(C) //C是问题的输入集合即候选集合
{
S={ }; //初始解集合为空集
while (not solution(S)) //集合S没有构成问题的一个解
{
x=select(C); //在候选集合C中做贪心选择
if feasible(S, x) //推断集合S中增加x后的解是否可行
S=S+{x};
C=C-{x};
}
return S;
}
</span>