上海有哪些做网站,基础建设包括哪些内容,网页站点怎么命名,网游推广员点击蓝字关注我们因公众号更改推送规则#xff0c;请点“在看”并加“星标”第一时间获取精彩技术分享来源于网络#xff0c;侵删01基本概念贪心算法是指在对问题求解时#xff0c;总是做出在当前看来是最好的选择。也就是说#xff0c;不从整体最优上加以考虑#xff0c;…点击蓝字关注我们因公众号更改推送规则请点“在看”并加“星标”第一时间获取精彩技术分享来源于网络侵删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语言知识汇总#includecstdio
#includeiostream
#includealgorithm
using namespace std;
int N;
struct Act{
int start;
int end;}act[100010];bool cmp(Act a,Act b)
{
return a.endb.end; }int greedy_activity_selector()
{
int num1,i1;
for(int j2;jN;j) {
if(act[j].startact[i].end) { ij; num; } }
return num;}int main()
{
int t;
scanf(%d,t);
while(t--){
scanf(%d,N);
for(int i1;iN;i){
scanf(%lld %lld,act[i].start,act[i].end);}act[0].start-1;act[0].end-1;sort(act1,actN1,cmp);
int resgreedy_activity_selector();
coutresendl; }}2.钱币找零问题这个问题在我们的日常生活中就更加普遍了。假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元至少要用多少张纸币用贪心算法的思想很显然每一步尽可能用面值大的纸币即可。在日常生活中我们自然而然也是这么做的。在程序中已经事先将Value按照从小到大的顺序排好。#includeiostream
#includealgorithm
using namespace std;
const int N7;
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 num0;
for(int iN-1;i0;i--){
int cmin(money/Value[i],Count[i]);moneymoney-c*Value[i];numc;}
if(money0) num-1;
return num;}int main()
{
int money;
cinmoney;
int ressolve(money);
if(res!-1) coutresendl;
else coutNOendl;}3.再论背包问题在从零开始学动态规划中我们已经谈过三种最基本的背包问题零一背包部分背包完全背包。很容易证明背包问题不能使用贪心算法。然而我们考虑这样一种背包问题在选择物品i装入背包时可以选择物品的一部分而不一定要全部装入背包。这时便可以使用贪心算法求解了。计算每种物品的单位重量价值作为贪心选择的依据指标选择单位重量价值最高的物品将尽可能多的该物品装入背包依此策略一直地进行下去直到背包装满为止。在零一背包问题中贪心选择之所以不能得到最优解原因是贪心选择无法保证最终能将背包装满部分闲置的背包空间使每公斤背包空间的价值降低了。在程序中已经事先将单位重量价值按照从大到小的顺序排好。#includeiostream
using namespace std;
const int N4;
void knapsack(float M,float v[],float w[],float x[]); int main()
{
float M50;
//背包所能容纳的重量
float w[]{0,10,30,20,5};
//每种物品的重量
float v[]{0,200,400,100,10};
//每种物品的价值
float x[N1]{0};
//记录结果的数组knapsack(M,v,w,x);
cout选择装下的物品比例endl;
for(int i1;iN;i) cout[i]:x[i]endl; } void knapsack(float M,float v[],float w[],float x[])
{
int i;
//物品整件被装下
for(i1;iN;i){
if(w[i]M) break; x[i]1; M-w[i]; }
//物品部分被装下
if(iN) x[i]M/w[i]; }4.多机调度问题n个作业组成的作业集可由m台相同机器加工处理。要求给出一种作业调度方案使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。作业不能拆分成更小的子作业每个作业均可在任何一台机器上加工处理。这个问题是NP完全问题还没有有效的解法(求最优解)但是可以用贪心选择策略设计出较好的近似算法(求次优解)。当nm时只要将作业时间区间分配给作业即可当nm时首先将n个作业从大到小排序然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中选择需要处理时间最长的然后依次选择处理时间次长的直到所有的作业全部处理完毕或者机器不能再处理其他作业为止。如果我们每次是将需要处理时间最短的作业分配给空闲的机器那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况这样势必效率较低。在下面的代码中没有讨论n和m的大小关系把这两种情况合二为一了。#includeiostream
#includealgorithm
using namespace std;
int speed[10010];
int mintime[110]; bool cmp( const int x,const int y)
{
return xy; } int main()
{
int n,m;
memset(speed,0,sizeof(speed));
memset(mintime,0,sizeof(mintime));
cinnm;
for(int i0;in;i) cinspeed[i]; sort(speed,speedn,cmp);
for(int i0;in;i) {*min_element(mintime,mintimem)speed[i]; }
cout*max_element(mintime,mintimem)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代码#includeiostream
#includealgorithm
using namespace std;int main()
{
int a[1000],t,n,sum;
scanf(%d,t);
while(t--){
scanf(%d,n);sum0;
for(int i0;in;i) scanf(%d,a[i]);
while(n3){summin(suma[1]a[0]a[n-1]a[1],suma[n-1]a[0]a[n-2]a[0]);n-2;}
if(n3) suma[0]a[1]a[2];
else if(n2) suma[1];
else suma[0];
printf(%d\n,sum);}}6.区间覆盖问题POJ1328是一道经典的贪心算法例题。题目大意是假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上只能覆盖d距离所以如果小岛能够被覆盖到的话它们之间的距离最多为d。题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目。对于每个小岛我们可以计算出一个雷达所在位置的区间。问题转化为如何用尽可能少的点覆盖这些区间。先将所有区间按照左端点大小排序初始时需要一个点。如果两个区间相交而不重合我们什么都不需要做如果一个区间完全包含于另外一个区间我们需要更新区间的右端点如果两个区间不相交我们需要增加点并更新右端点。AC代码#includecmath
#includeiostream
#includealgorithm
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 num1;
while(cinnd){
int counting1;
if(n0d0) break;
for(int i0;in;i){
int x,y;
cinxy;
if(yd){counting-1;}
double tsqrt(d*d-y*y);
//转化为最少区间的问题point[i].xx-t;
//区间左端点point[i].yxt;
//区间右端点}
if(counting!-1){qsort(point,n,sizeof(point[0]),cmp);
//按区间左端点排序
double spoint[0].y;
//区间右端点
for(int i1;in;i){
if(point[i].xs)
//如果两个区间没有重合,增加雷达数目并更新右端点{counting;spoint[i].y;}
else if(point[i].ys)
//如果第二个区间被完全包含于第一个区间,更新右端点{spoint[i].y;}}}
coutCase num: countingendl;num;}}7.销售比赛在学校OJ上做的一道比较好的题这里码一下。假设有偶数天要求每天必须买一件物品或者卖一件物品只能选择一种操作并且不能不选开始手上没有这种物品。现在给你每天的物品价格表要求计算最大收益。首先要明白第一天必须买最后一天必须卖并且最后手上没有物品。那么除了第一天和最后一天之外我们每次取两天小的买大的卖并且把卖的价格放进一个最小堆。如果买的价格比堆顶还大就交换。这样我们保证了卖的价格总是大于买的价格一定能取得最大收益。C语言知识汇总#includequeue
#includevector
#includecstdio
#includecstdlib
#includecstring
#includeiostream
#includealgorithm
using namespace std;
long long int price[100010],t,n,res;int main()
{ios::sync_with_stdio(false);
cint;
while(t--){
cinn;priority_queuelong long int, vectorlong long int, greaterlong long int q;res0;
for(int i1;in;i){
cinprice[i];}res-price[1];resprice[n];
for(int i2;in-1;ii2){
long long int buymin(price[i],price[i1]);
long long int sellmax(price[i],price[i1]);
if(!q.empty()){
if(buyq.top()){resres-2*q.top()buysell;q.pop();q.push(buy);q.push(sell);}
else{resres-buysell;q.push(sell);}}
else{resres-buysell;q.push(sell);}}
coutresendl;}}下面我们结合数据结构中的知识讲解几个例子。8.Huffman编码这同样是《算法导论》上的例子。Huffman编码是广泛用于数据文件压缩的十分有效的编码方法。我们可以有多种方式表示文件中的信息如果用01串表示字符采用定长编码表示则需要3位表示一个字符整个文件编码需要300000位采用变长编码表示给频率高的字符较短的编码频率低的字符较长的编码达到整体编码减少的目的则整个文件编码需要(45×113×312×316×39×45×4)×1000224000位由此可见变长码比定长码方案好总码长减小约25%。对每一个字符规定一个01串作为其代码并要求任一字符的代码都不是其他字符代码的前缀这种编码称为前缀码。可能无前缀码是一个更好的名字但是前缀码是一致认可的标准术语。编码的前缀性质可以使译码非常简单例如001011101可以唯一的分解为0,0,101,1101因而其译码为aabe。译码过程需要方便的取出编码的前缀为此可以用二叉树作为前缀码的数据结构树叶表示给定字符从树根到树叶的路径当作该字符的前缀码代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的路标。从上图可以看出最优前缀编码码的二叉树总是一棵完全二叉树而定长编码的二叉树不是一棵完全二叉树。给定编码字符集C及频率分布fC的一个前缀码编码方案对应于一棵二叉树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总花费215834。利用Huffman思想要使总费用最小那么每次只选取最小长度的两块木板相加再把这些和累加到总费用中即可。为了提高效率使用优先队列优化并且还要注意使用long long int保存结果。AC代码#includequeue
#includecstdio
#includeiostream
using namespace std;int main()
{
long long int sum;
int i,n,t,a,b;
while(~scanf(%d,n)){priority_queueint,vectorint,greaterint q;
for(i0;in;i){
scanf(%d,t);q.push(t);}sum0;
if(q.size()1){aq.top();suma;q.pop();}
while(q.size()1){aq.top();q.pop();bq.top();q.pop();tab;sumt;q.push(t);}
printf(%lld\n,sum);}}9.Dijkstra算法Dijkstra算法是由E.W.Dijkstra于1959年提出是目前公认的最好的求解最短路径的方法使用的条件是图中不能存在负边。算法解决的是单个源点到其他顶点的最短路径问题其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点简单的说就是bfs贪心算法的思想。#includeiostream
#includealgorithm
#define INF 1000
#define MAX_V 100
using 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];
cinVE;fill(d,dV1,INF);fill(used,usedV,false);
for(i0;iV;i){
for(j0;jV;j){
if(ij) cost[i][j]0;
else cost[i][j]INF;}}
for(m0;mE;m){
cinijcost[i][j];cost[j][i]cost[i][j];}
cinn;d[n]0;
//源点
while(true){
int vV;
for(m0;mV;m){
if((!used[m])(d[m]d[v])) vm;}
if(vV) break;used[v]true;
for(m0;mV;m){d[m]min(d[m],d[v]cost[v][m]);}}
for(i0;iV;i){
coutthe 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∈Uv∈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的权值最小的边加入生成树。#includeiostream
#includealgorithm
#define MAX_V 100
#define INF 1000
using 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];
cinVE;fill(mincost,mincostV1,INF);fill(used,usedV,false);
for(i0;iV;i){
for(j0;jV;j){
if(ij) cost[i][j]0;
else cost[i][j]INF;}}
for(m0;mE;m){
cinijcost[i][j];cost[j][i]cost[i][j];}mincost[0]0;
int res0;
while(true){
int vV;
for(m0;mV;m){
if((!used[m])(mincost[m]mincost[v]))vm;}
if(vV) break;used[v]true;resmincost[v];
for(m0;mV;m){mincost[m]min(mincost[m],cost[v][m]);}}
coutresendl;}Kruskal算法每一步直接将权值最小的不成环的边加入生成树我们借助并查集这一数据结构可以完美实现它。#includeiostream
#includealgorithm
#define MAX_E 100
using 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;
cinVE;initvalue(V);
for(i0;iE;i) cines[i].ues[i].ves[i].cost; sort(es,esE,comp);
int res0;
for(i0;iE;i){edge ees[i];
if(!same(e.u,e.v)){unite(e.u,e.v);rese.cost;}}
coutresendl; }bool comp(const edge e1,const edge e2)
{
return e1.coste2.cost; }void initvalue(int x)
{
for(int i0;ix;i) pre[i]i;}int find(int x)
{
int rx;
while(pre[r]!r) rpre[r];
int ix,j;
while(pre[i]!r){jpre[i];pre[i]r;ij;}
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 fxfind(x);
int fyfind(y);
if(fx!fy) pre[fx]fy; }如果你年满18周岁以上又觉得学【C语言】太难想尝试其他编程语言那么我推荐你学Python现有价值499元Python零基础课程限时免费领取限10个名额▲扫描二维码-免费领取戳“阅读原文”我们一起进步
