算法-贪心算法知识总结_贪心算法的数学归纳法

目录

1.要素

2.步骤

3.应用实例

4.反例

---

1.要素

（1）贪心选择性质

贪心选择性质是指，所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

我们来对贪心算法和动态规划算法做一个对比。

 在动态规划算法中，每步所做的选择往往依赖于相关子问题的解。因而只有在解出相关的子问题后，才能做出选择。

在贪心算法中，仅在当前状态下做出最好选择，即局部最优选择。然后再去解做出这个选择后产生的相应的子问题。

贪心算法所做的贪心选择可以依赖以往所做的选择，但绝不依赖将来所做的选择，也不依赖子问题的解。

由于上述原因，动态规划算法通常以自底向上的方式解决各个子问题，而贪心算法通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择，就将所求问题简化为规模更小的子问题。

（2）最优子结构性质

当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

2.步骤

（1）.把求解的问题分成若干个子问题。
（2）.对每一子问题求解，得到子问题的局部最优解。
（3）.把子问题的解局部最优解合成原来解问题的一个解。

3.应用实例

这里简要说一下每一个实例的重点

（1）活动安排问题

问题描述：

设有n个活动的集合E={1,2,…, n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有要求使用该资源的起始时间s,和结束时间f，且si<fi。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[s i, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。
例如：

 计算过程如下：

 对于活动安排问题，贪心算法总能求得的整体最优解，即它最终确定的相容活动集合的规模是最大的，这个结论可以用数学归纳法证明。

事实上，设E={1,2,…,n}为所给定的活动集合。由于E中活动按结束时间的非减序排列,故活动1具有最早完成时间。

首先证明活动安排问题有一个最优解以贪心算法选择开始，即该最优解中包含活动1。

设A ∈E是所给的活动安排问题的一个最优解，且A中活动也按结束时间非减序排列，A中的第一个活动是活动k。若k=1，则A就是一个以贪心选择开始的最优解。若k>l，则设B-A-{k}U{1}。由于fi≤fk且A中活动是相容的，故B中的活动也是相容的。又由于B中活动个数与A中活动个数相同，且A是最优的，故B也是最优的。也就是说，B是以贪心选择活动1开始的最优活动安排。由此可见，总存在以贪心选择开始的最优活动安排方案。
进一步，在做了贪心选择，即选择了活动1后，原问题就简化为对E中所有与活动1相容的活动进行活动安排的子问题。

即若A是原问题的最优解，则A'=A-{1}是活动安排问题E'={i∈E:si≥fi}的最优解。事实上，如果能找到E的一个解B'，包含比A'更多的活动，则将活动1加入到B中将产生E的一个解B，它包含比A更多的活动。这与A的最优性矛盾。因此，每步所做的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。

对贪心选择次数用数学归纳法即知，贪心算法 最终产生原问题的最优解。

会场安排问题与活动安排问题类似

会场安排问题是尽可能使用少的会场安排活动，这里附上会场安排问题的核心代码

算法设计分析：

  从文件中获取数据，最先进行排序，按照开始时间由小到大排序，如果开始时间相同就比较结束时间，结束时间越早的就在前面。贪心算法，即尽可能多地在一场会场里安排活动，利用一个整型数组记录当前的活动是否被安排过，从第一个开始安排，只要后面的开始时间大于等于当前的结束时间，就可以安排。

int findmin(int n,int a[][2]){
	int count;
	int i,j;
	int f[n];
	count=0;//cou记录此时安排了多少活动 
	for(i=0;i<n;i++)
	f[i]=0;	
	for(i=0;i<n;i++){
		if(f[i]==0){
			count++;
			int stime=a[i][1];
			for(j=i+1;j<n;j++){
				if(a[j][0]>=stime&&f[j]==0){
					stime=a[j][1];f[j]=1;
				}
			}
		}
	}
	return count;
}

（2）最优装载问题

问题描述： 

算法描述：

最优装载问题与活动安排问题其实是类似的，采用重量轻的优先装载。

贪心选择性质：

设集装箱已依其重量从小到大排序，(x，x2，…，x,)是最优装载问题的一个最优解，设k= min {i|xi=1}，如果给定的最优装载问题有解，则1≤k≤n。
(1)当k=1时，(x1,x2,…xn)是一个满足贪心选择性质的最优解。

(2)当k>1时，取y1=1，yk=0，yi=xi;1<i≤n，i≠k，则

因此，(y1,y2,"",yn)是所给最优装载问题的可行解。
   另一方面，由(y1,y2…, yn,)是满足贪心选择性质的最优解。所以，最优
装载问题具有贪心选择性质。

 最优子结构性质

设(x1,x2，…,xn)是最优装载问题的满足贪心选择性质的最优解，则x1=1，(x2,X3，…xn)是轮船载重量为c-w1、待装船集装箱为{2,3，…、n}时相应最优装载问题的最优解。也就是说，最优装载问题具有最优子结构性质。
由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法的正确性。算法 Loading 的主要计算量在于将集装箱依其重量从小到大排序，所以算法所需的计算时间为O(nlogn)。

（3）哈夫曼编码

问题分析：

哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩率通常为20%～90%。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0、1串表示各字符的最优表示方式。假设有一个数据文件包含100000个字符，要用压缩的方式存储它。该文件中各字符出现的频率如表4-1所示。文件中共有6个不同字符出现，字符a出现45000次，字符b出现13000次等。
 

前缀码：对每一个字符规定一个0、1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。
 哈夫曼算法的正确性：

 

最优子结构证明：

核心代码如下

应用优先队列，使算法的时间复杂度优化。

priority_queue<t*,vector<t*>,my>que;//最小堆 
void create(t * temp){
	if(temp->l){//如果有左子树 
		temp->l->code=temp->code+"0";
		create(temp->l);
	}
	if(!(temp->l)&&!(temp->r)){//如果是叶子节点 
		cout<<temp->word<<":"<<temp->code<<endl;
	}
	if(temp->r){
		temp->r->code=temp->code+"1";
		create(temp->r);
	}
}
void createtree(){
	vector<int>ve;
	vector<char>v;
	char w;
	int we;
	int n;
	cin>>n;
	while(n>0){//输入 
		cin>>w>>we;
		ve.push_back(w);
		v.push_back(we);
		n--;
	}
	int length=ve.size(); 
	for(int i=0;i<length;i++){
		t *tt=new t;
		tt->word=ve[i];
		tt->weight=v[i];
		tt->code="";
		tt->l=NULL;
		tt->r=NULL;
		que.push(tt);
	}
	while(que.size()>1){
		t *a,*b;
		a=que.top();
		que.pop();
		b=que.top();
		que.pop();
		t *temp=new t;
		temp->weight=a->weight+b->weight;
		temp->l=a;
		temp->r=b;
		temp->code="";
		temp->word='\0'; 
		que.push(temp);
	}
	create(que.top());
}

（4）单源最短路径

给定一个带权有向图G=(V,E)，其中每条边的权是非负实数。另外，给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
算法基本描述：

Dijkstra算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置顶点集合S,并不断地做贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组 dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组 dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。
贪心选择性质：

Dijkstra算法是应用贪心算法设计策略的又一个典型例子，所做的贪心选择是从V-S中选择具有最短特殊路径的顶点u，从而确定从源到u的最短路径长度dist[u]。这种贪心选择为什么能导致最优解呢?换句话说，为什么从源到u没有更短的其他路径呢?事实上，如果存在一条从源到u且长度比 dist[u]更短的路,设这条路初次走出S之外到达的顶点为x∈V-S，然后徘徊于S内外若干次，最后离开S到达u。

（7）区间覆盖问题

 分析：从文件中提取数据，先进行排序，从最小的数开始覆盖，即最小数+固定闭区间长度，然后从得到的数后面的最小的数据开始覆盖，这样就可以得到最小的段数。

#include<stdio.h>
#include<stdlib.h>
int n,k;
int a[100];
void getnumber(){
	FILE *fp;
	if((fp=fopen("input2.txt","rt"))==NULL){
		printf("打开失败");
		return;
	}
    fscanf(fp,"%d",&n);
	fscanf(fp,"%d",&k);
	int i;
	for(i=0;i<n;i++){
		fscanf(fp,"%d",&a[i]);
	}
	fclose(fp);	
}
void sort(){
	int i,j,t;
	for(i=0;i<n-1;i++){
		for(j=i+1;j<n;j++){
			if(a[i]>a[j]){
				t=a[i];a[i]=a[j];a[j]=t;
			}
		}
	}
}
void wtout(int count){
	FILE *fp;
	fp=fopen("output2.txt","w");
	if(fp==NULL){
		printf("error");
		return;
	}
	fprintf(fp,"%d",count);
	fclose(fp);
}
void findmin(){
	sort();
	int t,i,j;i=0;
	int count=0;//记录最小段数 
	t=a[i]+k;count++;
	while(t<a[n-1]){
		for(j=i+1;j<n;j++){
			if(a[j]>=t)
			break;
		}
        i=j;
		t=a[j]+k;
		count++;
	}
	wtout(count);
}
int main(){
	getnumber();
	findmin();
	return 0;
}

4.反例

0-1背包问题:

给定n种物品和一个背包。物品i的重量是w,，其价值为v，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大?
在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。
此问题的形式化描述是，给定c>0，wi>0，vi>0 (1≤i≤n)，要求找出一个n元的0-1向(x1,x2,…,xn)，xi∈ {0,1}，1≤i≤n，使得，而且达到最大。
背包问题:

与0-1背包问题类似，不同的是在选择物品i (1≤i≤n)装入背包时，可以选择物品i的一部分，而不一定要全部装入背包。

 此问题的形式化描述是,给定c>0, wi>0, vi>0(1≤i≤n),要求找出一个n元向量(x1,x2,…,xn) （0≤xi≤1，1≤i≤n)，使得，而且达到最大。

 这两类问题都具有最优子结构性质。对于0-1背包问题，设A是能够装入容量为c的背包的具有最大价值的物品集合，则A=A-{j}是n-1个物品1,2,…,j-1,j+1,…, n可装入容量为c-wj,的背包的具有最大价值的物品集合。对于背包问题，类似地，若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量w，剩余的将是n1个原重物品1,2,…,j-1, j+1,…, n及重为wj-w的物品 j中可装入容量为c-w的背包且具有最大价值的物品。

背包问题可以用贪心算法求解，而0-1背包问题不能用贪心算法求解。

 对于0-1背包问题，贪心选择之所以不能得到最优解是因为，在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每千克背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案,再做出最好选择。

上述主要是结合课本加上自己的分析总结的，希望自己可以坚持学习，收获更多的知识！