C语言贪心算法
01
基本概念
贪心算法是指在对问题求解时，总是做出在当前看来是好的选择。也就是说，不从整体优上加以考虑，只做出在某种意义上的局部优解。贪心算法不是对所有问题都能得到整体优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
02
贪心算法的基本思路
解题的一般步骤是：
1.建立数学模型来描述问题；
2.把求解的问题分成若干个子问题；
3.对每一子问题求解，得到子问题的局部优解；
4.把子问题的局部优解合成原来问题的一个解。
03
该算法存在的问题
不能保证求得的后解是佳的
不能用来求大值或小值的问题
只能求满足某些约束条件的可行解的范围
04
贪心算法适用的问题
贪心策略适用的前提是：局部优策略能导致产生全局优解。
实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。
05
贪心选择性质
所谓贪心选择性质是指所求问题的整体优解可以通过一系列局部优的选择，换句话说，当考虑做何种选择的时候，我们只考虑对当前问题佳的选择而不考虑子问题的结果。这是贪心算法可行的个基本要素。贪心算法以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择终导致问题的整体优解。
当一个问题的优解包含其子问题的优解时，称此问题具有优子结构性质。问题的优子结构性质是该问题可用贪心算法求解的关键特征。
06
贪心算法的实现框架
从问题的某一初始解出发：
while (朝给定总目标前进一步){利用可行的决策，求出可行解的一个解元素。}
由所有解元素组合成问题的一个可行解；
07
例题分析
话不多说，我们来看几个具体的例子慢慢理解它：
1.活动选择问题
这是《算法导论》上的例子，也是一个非常经典的问题。有n个需要在同一天使用同一个教室的活动a1,a2,…,an，教室同一时刻只能由一个活动使用。每个活动ai都有一个开始时间si和结束时间fi 。一旦被选择后，活动ai就占据半开时间区间[si,fi)。如果[si,fi]和[sj,fj]互不重叠，ai和aj两个活动就可以被安排在这一天。该问题就是要安排这些活动使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S，其中各项活动按照结束时间单调递增排序。
考虑使用贪心算法的解法。为了方便，我们用不同颜色的线条代表每个活动，线条的长度就是活动所占据的时间段，蓝色的线条表示我们已经选择的活动；红色的线条表示我们没有选择的活动。
如果我们每次都选择开始时间早的活动，不能得到优解：
如果我们每次都选择持续时间短的活动，不能得到优解：
可以用数学归纳法证明，我们的贪心策略应该是每次选取结束时间早的活动。直观上也很好理解，按这种方法选择相容活动为未安排活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。
C语言知识汇总
using namespace std; int N;struct Act {int start;int end; }act[100010];
bool cmp(Act a,Act b){ return a.end<b.end; }
int greedy_activity_selector(){ int num=1,i=1; for(int j=2;j<=N;j++) { if(act[j].start>=act[i].end) { i=j; num++; } } return num; }
int main(){ int t;scanf("%d",&t);while(t--) {scanf("%d",&N);for(int i=1;i<=N;i++) {scanf("%lld %lld",&act[i].start,&act[i].end); } act[].start=-1; act[].end=-1; sort(act+1,act+N+1,cmp);int res=greedy_activity_selector();cout<<res<<endl; } } 2.钱币找零问题
这个问题在我们的日常生活中就更加普遍了。假设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,,2,1,,3,5};int Value[N]={1,2,5,10,20,50,100};
int solve(int money){int num=;for(int i=N-1;i>=;i--) {int c=min(money/Value[i],Count[i]); money=money-c*Value[i]; num+=c; }if(money>) num=-1;return num; }
int main(){int money;cin>>money;int res=solve(money);if(res!=-1) cout<<res<<endl;else cout<<"NO"<<endl; }3.再论背包问题
在从零开始学动态规划中我们已经谈过三种基本的背包问题：零一背包，部分背包，完全背包。很容易证明，背包问题不能使用贪心算法。然而我们考虑这样一种背包问题：在选择物品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]; }
4.多机调度问题
n个作业组成的作业集，可由m台相同机器加工处理。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业；每个作业均可在任何一台机器上加工处理。这个问题是NP完全问题，还没有有效的解法(求优解)，但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当n<=m时，只要将作业时间区间分配给作业即可；当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间长的，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间长的作业在处理的情况，这样势必效率较低。在下面的代码中没有讨论n和m的大小关系，把这两种情况合二为一了。
#include<iostream> #include<algorithm> using namespace std; int speed[10010]; int mintime[110];
bool cmp( const int &x,const int &y){ return x>y; }
int main(){ int n,m; memset(speed,,sizeof(speed)); memset(mintime,,sizeof(mintime)); cin>>n>>m; for(int i=;i<n;++i) cin>>speed[i]; sort(speed,speed+n,cmp); for(int i=;i<n;++i) { *min_element(mintime,mintime+m)+=speed[i]; } cout<<*max_element(mintime,mintime+m)<<endl; }5.小船过河问题
POJ1700是一道经典的贪心算法例题。题目大意是只有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，少需要多久。先将所有人过河所需的时间按照升序排序，我们考虑把单独过河所需要时间多的两个旅行者送到对岸去，有两种方式：
1.快的和次快的过河，然后快的将船划回来；次慢的和慢的过河，然后次快的将船划回来，所需时间为：t[0]+2*t[1]+t[n-1]；
2.快的和慢的过河，然后快的将船划回来，快的和次慢的过河，然后快的将船划回来，所需时间为：2*t[0]+t[n-2]+t[n-1]。
算一下就知道，除此之外的其它情况用的时间一定更多。每次都运送耗时长的两人而不影响其它人，问题具有贪心子结构的性质。
AC代码：
#include<iostream>#include<algorithm>using namespace std;
int main(){int a[1000],t,n,sum;scanf("%d",&t);while(t--) {scanf("%d",&n); sum=0;for(int i=;i<n;i++) scanf("%d",&a[i]);while(n>3) { sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]); n-=2; }if(n==3) sum+=a[]+a[1]+a[2];else if(n==2) sum+=a[1];else sum+=a[];printf("%d\n",sum); } }6.区间覆盖问题
POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧，而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上，只能覆盖d距离，所以如果小岛能够被覆盖到的话，它们之间的距离多为d。题目要求计算出能够覆盖给出的所有岛屿的少雷达数目。对于每个小岛，我们可以计算出一个雷达所在位置的区间。
问题转化为如何用尽可能少的点覆盖这些区间。先将所有区间按照左端点大小排序，初始时需要一个点。如果两个区间相交而不重合，我们什么都不需要做；如果一个区间完全包含于另外一个区间，我们需要更新区间的右端点；如果两个区间不相交，我们需要增加点并更新右端点。
AC代码：
#include<cmath>#include<iostream>#include<algorithm>using namespace std;struct Point {double x;double y; }point[1000];
int cmp(const void *a, const void *b){return (*(Point *)a).x>(*(Point *)b).x?1:-1; }
int main(){int n,d;int num=1;while(cin>>n>>d) {int counting=1;if(n==&&d==) break;for(int i=;i<n;i++) {int x,y;cin>>x>>y;if(y>d) { counting=-1; }double t=sqrt(d*d-y*y);//转化为少区间的问题 point[i].x=x-t;//区间左端点 point[i].y=x+t;//区间右端点 }if(counting!=-1) { qsort(point,n,sizeof(point[]),cmp);//按区间左端点排序double s=point[].y;//区间右端点for(int i=1;i<n;i++) {if(point[i].x>s)//如果两个区间没有重合,增加雷达数目并更新右端点 { counting++; s=point[i].y; }else if(point[i].y<s)//如果第二个区间被完全包含于个区间,更新右端点 { s=point[i].y; } } }cout<<"Case "<<num<<':'<<' '<<counting<<endl; num++; } }7.销售比赛
在学校OJ上做的一道比较好的题，这里码一下。假设有偶数天，要求每天必须买一件物品或者卖一件物品，只能选择一种操作并且不能不选，开始手上没有这种物品。现在给你每天的物品价格表，要求计算大收益。首先要明白，天必须买，后一天必须卖，并且后手上没有物品。那么除了天和后一天之外我们每次取两天，小的买大的卖，并且把卖的价格放进一个小堆。如果买的价格比堆顶还大，就交换。这样我们保证了卖的价格总是大于买的价格，一定能取得大收益。
C语言知识汇总
#include<queue>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>using namespace std;long long int price[100010],t,n,res;
int main(){ ios::sync_with_stdio(false);cin>>t;while(t--) {cin>>n; priority_queue<long long int, vector<long long int>, greater<long long int> > q; res=0;for(int i=1;i<=n;i++) {cin>>price[i]; } res-=price[1]; res+=price[n];for(int i=2;i<=n-1;i=i+2) {long long int buy=min(price[i],price[i+1]);long long int sell=max(price[i],price[i+1]);if(!q.empty()) {if(buy>q.top()) { res=res-2*q.top()+buy+sell; q.pop(); q.push(buy); q.push(sell); }else { res=res-buy+sell; q.push(sell); } }else { res=res-buy+sell; q.push(sell); } } cout<<res<<endl; } }下面我们结合数据结构中的知识讲解几个例子。
8.Huffman编码
这同样是《算法导论》上的例子。Huffman编码是广泛用于数据文件压缩的十分有效的编码方法。我们可以有多种方式表示文件中的信息，如果用01串表示字符，采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300000位；采用变长编码表示，给频率高的字符较短的编码，频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要(45×1+13×3+12×3+16×3+9×4+5×4)×1000=224000位，由此可见，变长码比定长码方案好，总码长减小约25%。
对每一个字符规定一个01串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀，这种编码称为前缀码。可能无前缀码是一个更好的名字，但是前缀码是一致认可的标准术语。编码的前缀性质可以使译码非常简单：例如001011101可以的分解为0,0,101,1101，因而其译码为aabe。译码过程需要方便的取出编码的前缀，为此可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的路标。
从上图可以看出，优前缀编码码的二叉树总是一棵完全二叉树，而定长编码的二叉树不是一棵完全二叉树。给定编码字符集C及频率分布f，C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为dT(c)，dT(c)也是字符c的前缀码长。则平均码长定义为：
使平均码长达到小的前缀码编码方案称为C的优前缀码。
Huffman编码的构造方法：先合并小频率的2个字符对应的子树，计算合并后的子树的频率；重新排序各个子树；对上述排序后的子树序列进行合并；重复上述过程，将全部结点合并成1棵完整的二叉树；对二叉树中的边赋予0、1，得到各字符的变长编码。
POJ3253一道就是利用这一思想的典型例题。题目大意是有把一块无限长的木板锯成几块给定长度的小木板，每次锯都需要一定费用，费用就是当前锯的木板的长度。给定各个要求的小木板的长度以及小木板的个数，求小的费用。以要求3块长度分别为5,8,5的木板为例：先从无限长的木板上锯下长度为21的木板，花费21；再从长度为21的木板上锯下长度为5的木板，花费5；再从长度为16的木板上锯下长度为8的木板，花费8；总花费=21+5+8=34。利用Huffman思想，要使总费用小，那么每次只选取小长度的两块木板相加，再把这些和累加到总费用中即可。为了提高效率，使用优先队列优化，并且还要注意使用long long int保存结果。
AC代码：
#include<queue>#include<cstdio>#include<iostream>using namespace std;
int main(){long long int sum;int i,n,t,a,b;while(~scanf("%d",&n)) { priority_queue<int,vector<int>,greater<int> >q;for(i=;i<n;i++) {scanf("%d",&t); q.push(t); } sum=0;if(q.size()==1) { a=q.top(); sum+=a; q.pop(); }while(q.size()>1) { a=q.top(); q.pop(); b=q.top(); q.pop(); t=a+b; sum+=t; q.push(t); }printf("%lld\n",sum); } }
9.Dijkstra算法
Dijkstra算法是由E.W.Dijkstra于1959年提出，是目前公认的好的求解短路径的方法，使用的条件是图中不能存在负边。算法解决的是单个源点到其他顶点的短路径问题，其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点近的顶点，简单的说就是bfs+贪心算法的思想。
#include<iostream>#include<algorithm>#define INF 1000#define MAX_V 100using namespace std;
int main(){int V,E;int i,j,m,n;int cost[MAX_V][MAX_V];int d[MAX_V];bool used[MAX_V];cin>>V>>E; fill(d,d+V+1,INF); fill(used,used+V,false);for(i=;i<V;i++) {for(j=;j<V;j++) {if(i==j) cost[i][j]=0;else cost[i][j]=INF; } }for(m=;m<E;m++) {cin>>i>>j>>cost[i][j]; cost[j][i]=cost[i][j]; }cin>>n; d[n]=0;//源点while(true) {int v=V;for(m=;m<V;m++) { if((!used[m])&&(d[m]<d[v])) v=m; } if(v==V) break; used[v]=true;for(m=;m<V;m++) { d[m]=min(d[m],d[v]+cost[v][m]); } }for(i=;i<V;i++) {cout<<"the shortest distance between "<<n<<" and "<<i<<" is "<<d[i]<<endl; } }10.小生成树算法
设一个网络表示为无向连通带权图G =(V, E) , E中每条边(v,w)的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树的代价是指生成树上各边权的总和，在G的所有生成树中，耗费小的生成树称为G的小生成树。例如在设计通信网络时，用图的顶点表示城市，用边(v,w)的权c[v][w]表示建立城市v和城市w之间的通信线路所需的费用，小生成树给出建立通信网络的经济方案。
构造小生成树的Kruskal算法和Prim算法都利用了MST(小生成树)性质：设顶点集U是V的真子集(可以任意选取)，如果(u,v)∈E为横跨点集U和V—U的边，即u∈U，v∈V- U，并且在所有这样的边中，(u,v)的权c[u][v]小，则一定存在G的一棵小生成树，它以(u,v)为其中一条边。
使用反证法可以很简单的证明此性质。假设对G的任意一个小生成树T，针对点集U和V—U，(u,v)∈E为横跨这2个点集的小权边，T不包含该小权边<u, v>，但T包括节点u和v。将<u,v>添加到树T中，树T将变为含回路的子图，并且该回路上有一条不同于<u,v>的边<u’,v’>,u’∈U,v’∈V-U。将<u’,v’>删去，得到另一个树T’，即树T’是通过将T中的边<u’,v’>替换为<u,v>得到的。由于这2条边的耗费满足c[u][v]≤c[u’][v’]，故即T’耗费≤T的耗费，这与T是任意小生成树的假设相矛盾，从而得证。
Prim算法每一步都选择连接U和V-U的权值小的边加入生成树。
#include<iostream>#include<algorithm>#define MAX_V 100#define INF 1000using namespace std;
int main(){int V,E;int i,j,m,n;int cost[MAX_V][MAX_V];int mincost[MAX_V];bool used[MAX_V];cin>>V>>E; fill(mincost,mincost+V+1,INF); fill(used,used+V,false);for(i=;i<V;i++) {for(j=;j<V;j++) {if(i==j) cost[i][j]=0;else cost[i][j]=INF; } }for(m=;m<E;m++) {cin>>i>>j>>cost[i][j]; cost[j][i]=cost[i][j]; } mincost[0]=0;int res=;while(true) {int v=V;for(m=;m<V;m++) { if((!used[m])&&(mincost[m]<mincost[v])) v=m; } if(v==V) break; used[v]=true; res+=mincost[v];for(m=;m<V;m++) { mincost[m]=min(mincost[m],cost[v][m]); } }cout<<res<<endl; }Kruskal算法每一步直接将权值小的不成环的边加入生成树，我们借助并查集这一数据结构可以完美实现它。
#include<iostream>#include<algorithm>#define MAX_E 100using namespace std; struct edge {int u,v,cost; };int pre[MAX_E]; edge es[MAX_E];int find(int x);void initvalue(int x);bool same(int x,int y);void unite(int x,int y);bool comp(const edge& e1,const edge& e2);
int main(){int V,E;int i,j,m,n;cin>>V>>E; initvalue(V);for(i=;i<E;i++) cin>>es[i].u>>es[i].v>>es[i].cost; sort(es,es+E,comp);int res=;for(i=;i<E;i++) { edge e=es[i];if(!same(e.u,e.v)) { unite(e.u,e.v); res+=e.cost; } }cout<<res<<endl; }
bool comp(const edge& e1,const edge& e2){return e1.cost<e2.cost; }
void initvalue(int x){for(int i=;i<x;i++) pre[i]=i; }
int find(int x){int r=x;while(pre[r]!=r) r=pre[r];int i=x,j;while(pre[i]!=r) { j=pre[i]; pre[i]=r; i=j; }return r; }
bool same(int x,int y){if(find(x)==find(y)) return true;else return false; }
void unite(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy) pre[fx]=fy; }来源 ：CSDN，简书等
相关文章