目录
- 一）概念
- 二）找出全局最优解的要求
- 三）求解时应考虑的问题
- 四）基本步骤
- 五）贪心策略选择
- 六）实际应用
- 1.零钱找回问题
- 2.背包问题
- 3.哈夫曼编码
- 4.单源路径中的Djikstra算法
- 5.最小生成树Prim算法
一）概念
贪心算法（Greedy Alogorithm）又叫登山算法，它的根本思想是逐步到达山顶，即逐步获得最优解，是解决最优化问题时的一种简单但是适用范围有限的策略。
贪心算法没有固定的框架，算法设计的关键是贪婪策略的选择。贪心策略要无后向性，也就是说某状态以后的过程不会影响以前的状态，至于当前状态有关。
贪心算法是对某些求解最优解问题的最简单、最迅速的技术。某些问题的最优解可以通过一系列的最优的选择即贪心选择来达到。但局部最优并不总能获得整体最优解，但通常能获得近似最优解。
在每一步贪心选择中，只考虑当前对自己最有利的选择，而不去考虑在后面看来这种选择是否合理。
二）找出全局最优解的要求
在遇见问题时如何确定是否可以使用贪心算法解决问题，那么决定一个贪心算法是否能找到全局最优解的条件是什么呢？其实就是以下两点：
- 最优子结构（optimal subproblem structure,和动态规划中的是一个概念）
- 最优贪心选择属性（optimal greedy choice property）
三）求解时应考虑的问题
1.候选集合S
为了构造问题的解决方案，有一个候选集合C作为问题的可能解，问题的最终解均取自于候选集合C。
2.解集合S
随着贪心选择的进行，解集合不断扩展，直到构成一个满足问题的完整解。
3.解决函数solution
检查解集合是否构成问题的完整解。
4.选择函数select
即贪心策略，这是贪心算法的关键，它指出哪个候选对象有希望构成成问题的解。
5.可行函数feasible
检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。
四）基本步骤
贪心算法使用基本步骤：
1.从问题的某个初始解出发
2.采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个不分解，缩小问题的范围或规模。
3.将所有的部分解综合起来，得到问题的最终解。
五）贪心策略选择
贪心算法的原理是通过局部最优来达到全局最优，采用的是逐步构造最优解的方法。在每个阶段，都做出一个看上去最优的，决策一旦做出，就不再更改。
要选出最优解可不是一件容易的事，要证明局部最优为全局最优，要进行数学证明，否则就不能说明为全局最优。
很多问题表面上看来用贪心算法可以找到最优解，实际上却把最优解给漏掉了。这就像现实生活中的“贪小便宜吃大亏”。所以我们在解决问题的时候，一定要谨慎使用贪心算法，一定要注意这个问题适不适合采用贪心算法。
贪心算法很多时候并不能达到全局最优，为什么我们还要使用它呢？
因为在很多大规模问题中，寻找最优解是一件相当费时耗力的事情，有时候付出大量人力物力财力后，回报并不与投入成正比。在这个时候选择相对最优的贪心算法就比较经济可行了。有的问题对最优的要求不是很高，在充分衡量付出和回报后，选择贪心算法未尝不是一种不错的选择呢。
六）实际应用
1.零钱找回问题
这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？用贪心算法的思想，很显然，每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。
下面展示一些 内联代码片。
#include #include using namespace std; const int N=7; int Count[N]={3,0,2,1,0,3,5}; int Value[N]={1,2,5,10,20,50,100}; int solve(int money) { int num=0; for(int i=N-1;i>=0;i--) { int c=min(money/Value[i],Count[i]); money=money-c*Value[i]; num+=c; } if(money>0) num=-1; return num; } int main() { int money; cin>>money; int res=solve(money); if(res!=-1) cout float M=50; //背包所能容纳的重量 float w[]={0,10,30,20,5}; //每种物品的重量 float v[]={0,200,400,100,10}; //每种物品的价值 float x[N+1]={0}; //记录结果的数组 knapsack(M,v,w,x); cout int i; //物品整件被装下 for(i=1;i if(w[i]M) break; x[i]=1; M-=w[i]; } //物品部分被装下 if(i
