贪心算法（greedy algorithm，又称贪婪算法）详解（附例题）

一）概念

贪心算法（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<iostream>
#include<algorithm>
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<<res<<endl;
	else cout<<"NO"<<endl;
}

2.背包问题

在 从零开始学动态规划中我们已经谈过三种最基本的背包问题：零一背包，部分背包，完全背包。很容易证明，背包问题不能使用贪心算法。然而我们考虑这样一种背包问题：在选择物品i装入背包时，可以选择物品的一部分，而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为贪心选择的依据指标，选择单位重量价值最高的物品，将尽可能多的该物品装入背包，依此策略一直地进行下去，直到背包装满为止。在零一背包问题中贪心选择之所以不能得到最优解原因是贪心选择无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。在程序中已经事先将单位重量价值按照从大到小的顺序排好。

#include<iostream>   
using namespace std;   
const int N=4;  
void knapsack(float M,float v[],float w[],float x[]);  
  
int main()  
{  
    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<<"选择装下的物品比例："<<endl;  
    for(int i=1;i<=N;i++) cout<<"["<<i<<"]:"<<x[i]<<endl;  
}  
  
void knapsack(float M,float v[],float w[],float x[])  
{  
    int i;  
    //物品整件被装下  
    for(i=1;i<=N;i++)
    {  
        if(w[i]>M) break;   
        x[i]=1;  
        M-=w[i];  
    }   
    //物品部分被装下  
    if(i<=N) x[i]=M/w[i];   
} 

3.哈夫曼编码

假设有一系列的字符，我们希望用一些二进制码来代替这些字符以进行数据压缩，使得压缩后的总比特数最小。哈夫曼编码正是这样一样压缩数据的方式。

如果我们已知各字符在文本中的出现频率，考虑到为了让压缩后的数据更小，我们直觉是让出现频率高的字符用尽可能短的编码，而出现频率高的则可以用更长的编码。

哈夫曼编码的解决方案是这样的：不断找到当前出现频率最小的两个结点（字符或频率），将它们结合，作为一个新生成的结点的左右子结点，并将新生成的结点继续放入比较，直到没有落单的字符。

过程演示

该贪心算法针对这个问题得到的解是最优的。

4.单源路径中的Djikstra算法

求A到其他节点的最短路径：

维护三个东西，从A到其他节点的路径长度队列Queue，数组visited用于记录已保存最短路径的节点，数组res用于记录节点A到其他节点的最短路径。
开始时，Queue中只有A节点自己，三组数据如下：
Queue：[(A, 0)] 起始节点为A，A到A的距离为0
visited：[true, false,false,false,false] A节点是已经访问过的节点，是true，其他节点是false
res：[0，∞，∞，∞，∞] A到自己的距离是0，到其他节点的距离目前是∞

将以A为起点的路径加入到Queue中，2和4是节点D和B的路径权重：
Queue：[(D, 2), (B, 4)]
visited：[true, false,false,false,false]
res：[0，∞，∞，∞，∞]
在Queue中，路径最短的是D，取出D，更新三组数据：
Queue：[(B, 3), (C, 3), (E, 9)]

因为A-D-B的路径权重为3小于A-B的路径权重4，所以更新一下B的路径权重。
visited:[true,false,false,true,false]
res: [0,∞, ∞,2,∞]

取出B，更新三组数据：
Queue: [(C,3), (E, 9)]
visited: [true,true,false,true,false]
res: [0,3, ∞,2, ∞]

取出C，更新三组数据：
Queue：[(E, 6)]
visited: [true,true,true,true,false]
res: [0,3, 3,2, ∞]

取出E，更新三组数据：
Queue：[]
visited: [true,true,true,true,true]
res: [0,3, 3,2, 6]

至此，Queue队列空，计算过程结束。

5.最小生成树Prim算法

prim算法（读者可以将其读作“普里姆算法”）用来解决最小生成树问题，其基本思想是对图G(V,E)设置集合S，存放已被访问的顶点，然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点（记为u），访问并加入集合S。之后，令顶点u为中介点，优化所有从u能到达的顶点v与集合S之间的最短距离。这样的操作执行n次（n为顶点个数），直到集合S已包含所有顶点。可以发现，prim算法的思想与最短路径中Dijkstra算法的思想几乎完全相同，只是在涉及最短距离时使用了集合S代替 Dijkstra算法中的起点s。

①将地图上的所有边都抹去，只有当访问一个顶点后オ把这个顶点顶点连接的边显现（这点和Dijkstra算法中相同）。

②将已访问的顶点置于ー个巨型防护罩中。可以沿着这个防护罩连接的边去访问未到达的顶点

③在地图中的顶点V(0≤i≤5)上记录顶点V与巨型防护罩之间的最短距离（即V与每个访问的顶点之间距离的最小值）。由于在①把所有边都抹去了，因此在初始状态下只在顶点V0上标记0，而其他顶点都标记无穷大（记为INF）。为了方便叙述，在下文中某几处出现的最短距离都是指从顶点V与当前巨型防护罩之间的最短距离。

下面是行动策略：

①由于要访问六个顶点，因此将②③步骤执行六次，每次访问一个顶点（如果是n个顶点，那么就执行n次）。

②每次都从还未访问的顶点中选择与当前巨型防护罩最近的顶点（记为Vk(0≤k≤5)），使用“爆裂模式”的能力恢复这条最近的边（并成为最小生成树中的一条边），前往访问。

③访问顶点Vk后，将Vk加入巨型防护罩中，开放地图上Vk连接的所有边，并査看以Vk作为巨型防护罩连接外界的接口的情况下，能否利用Vk刚开放的边使某些还未访问的顶点与巨型防护罩的最短距离变小。如果能，则将那个最短距离覆盖到地图对应的顶点上。

另外，为了得到最小生成树的边权之和，需要在访问顶点之前设置一个初值为0的变量sum，并在攻打过程中将加入最小生成树中的边的边权累加起来。