贪心算法的应用实例

1贪心算法的应用实例例2．排队问题【题目描述】在一个医院B超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0i=n）,请求出一种排列次序，使每个人排队等候时间总和最小。输入数据：第1行一个正整数n（你=10000》，第2行有n个不超过1000的正整数ti.输出要求：n个人排队时间最小总和。输入输出样例输入：451087输出：67【算法分析】本题贪心算法：n个人时间从小到大排序，就是这n个人最佳排队方案。求部分和的和即为所求。反证法证明：假设有最优解序列：s1,s2…sn,如s1不是最小的Tmin，不妨设sk=Tmin,将s1与sk对调，显然，对sk之后的人无影响，对sk之前的人等待都减少了，(s1-sk)0,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。例3．:数列极差问题【题目描述】在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。编程任务：对于给定的数列，编程计算出极差M。输入输出样例：输入：42143输出：13【算法分析】当看到此题时，我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。下面我们以求max为例来讨论此题用贪心策略求解的合理性。讨论：假设经（Ｎ－3）次变换后得到３个数：a,b,max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为z1，z2，则有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ+１所以z1－z2＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，2ｂ（ｍ≥ａ≥ｂ）且ｍ不为（Ｎ－２）次变换后的最大值，即ｍ＜max＇则此时所求得的最大值为：z3＝（ａ×ｂ+１）×ｍ+１此时z1－z3＝(１+ａｂ）（max＇－ｍ）＞０所以此时不为最优解。所以若使第ｋ（１≤ｋ≤Ｎ－１）次变换后所得值最大，必使（ｋ－１）次变换后所得值最大（符合贪心策略的特点2），在进行第ｋ次变换时，只需取在进行（ｋ－１）次变换后所得数列中的两最小数ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合贪心策略特点1），因此此题可用贪心策略求解。在求ｍin时，我们只需在每次变换的数列中找到两个最大数ｐ，ｑ施加作用ｆ：ｐ←ｐ×ｑ+１，ｑ←-∞即可．原理同上。这是一道两次运用贪心策略解决的一道问题，它要求选手有较高的数学推理能力。例4．整数区间range.cpp【题目描述】我们定义一个整数区间[a,b],a,b是一个从a开始至b结束的连续整数的集合。编一个程序，对给定的n个区间，找出满足下述条件的所含元素个数最少的集合中元素的个数：对于所给定的每一个区间，都至少有两个不同的整数属于该集合。(1=n=10000,0=a=b=1000)输入输出格式：输入：第一行一个正整数n，接下来有n行，每行给定一个区间的a,b值输出：一个正整数，即满足条件的集合所包含的最少元素个数输入输出样例输入：输出：4436240247【算法分析】本题数据规模较大，用搜索做会超时，而动态规划无从下手。考虑贪心算法。题目意思是要找一个集合，该集合中的数的个数既要少又要和所给定的所有区间有交集。（每个区间至少有两个该集合中的数）。我们可以从所给的区间中选数，为了选尽量少的数，应该使所选的数和更多的区间有交集这就是贪心的标准。一开始将所有区间按照右端点从小到大排序。从第一个区间开始逐个向后检查，看所选出的数与所查看的区间有无交集，有两个则跳过，只有一个数相交，就从当前区间中选出最大的一个数（即右端点），若无交集，则从当前区间选出两个数，就（右端点，右端点-1），直至最后一个区间。#includeiostream//整数区间问题usingnamespacestd;structprince{intleft,right;//区间左右端点}a[10000];intn;intresult;//存放结果中的数intcmp(constvoid*a,constvoid*b){return(*(prince*)a).right-(*(prince*)b).right;3}intwork(){qsort(a+1,n,sizeof(a[0]),cmp);//按区间右端点由小到大排序inti,j,k;inta1,a2;a1=a[1].right-1;a2=a[1].right;result=2;for(i=2;i=n;i++){if(a[i].left=a1&&a[i].right=a2)continue;//完全包含if(a[i].lefta2)//完全不包含{a1=a[i].right-1;a2=a[i].right;result=result+2;}if(a[i].lefta1&&a[i].righta2&&a[i].left=a2){a1=a2;a2=a[i].right;result++;}//只包含一个}returnresult;}intmain(){freopen(range6.in,r,stdin);freopen(range6.out,w,stdout);cinn;inti;for(i=1;i=n;i++)cina[i].lefta[i].right;coutwork()endl;return0;}例5．骆驼商队CamelTrading【题目描述】在一片古老的大地上，虽然商业已经非常繁荣，但是那里的人们仍然延续着古老的交易方式。他们牵着骆驼在城市之间往来奔波，贩运成批的商品，换来一袋袋的金币。这片大陆上有N个城市，编号为1……N。在一些城市之间有路可通，有路就有商队。但是在不同的城市之间经商所得的收益不同，在下面的这个N=4的例子中，在城市1和城市2之间进行一次交易可以获得40枚金币，在城市2和3之间交易一次可以获得50枚金币，等等。在任意两个城市之间，这样的交易只能进行一次。因为你第二次贩运你的商品时，人们对它们就不会感兴趣了。现在你只身来到这个大陆上，用有限的资金在每个城市中购买了一支商队。你需要想办法让你的这N支商队给你带来最大的经济收益。304050203012344任务说明给出这个大陆的地图和每两个城市之间的贸易值（如果这两个城市之间有路可通的话），你需要指挥你的N支商队进行一次经商，使得这N支商队在这次经商中获得的总收益最大。注意：你的每支商队只能进行一次交易，即它们只能从它们所在的城市到达一个相邻的城市。当然，它们也可以不进行任何交易。输入数据输入文件的第一行有两个整数N（1N100）、M（M0），分别表示这个大陆上的城市数和道路数。接下来有M行，每行包括三个整数i、j（1i,jN且ij）、v(1V10000)，表示一条道路的信息。其中i和j表示这条路在城市i和城市j之间，v表示沿着这条路进行一次交易所得的收益。i和j的顺序是无关的，并且任意两个城市之间最多存在一条路。输出数据你的输出文件应该2行，第1行包含N个整数。其中第k个整数表示你在城市k中的商队将要前往哪个城市进行交易（如果这支商队进行交易的话）或者为0（如果这支商队不进行任何交易）。第2行输出最大收益值。输入输出样例input.inoutput.out样例图示45124013302350243034202312150最大收益=40+50+30+30【算法分析】本题转化成模型就是：在一个无向图中，对于每个点，取一条和它相关联的边（如果这样的边存在的话），使得取出来的所有边的权和最大。首先，如果这个图是不连通的，那么它的各个连通分量之间是没有任何联系的。对这些连通分量中的问题可以分别独立地解决，合并起来就是整个问题的解。所以我们在下面的讨论中假定图是连通的。直观地考虑，如果图中存在度为1的点，那么就把这一点上的唯一的一条边分配给这个点（将某条边“分配”给某个点的含义是：将这条边作为和这一点相关联的边取出来，同时这一点就失效了，因为和它相关联的其他边都不能再取了）。如果不存在这样的点，那么此时有两种情况：一种是边数等于点数，那么这个图就是一个环，这时可以取出图中所有的边；一种是边数大于点数，那么就可以把这个图中权最小的一条边直接删去，因为这条边“显然”不会被取到的。依据这样一个直观思想，本题可以用贪心法来解决。贪心算法（用于连通图）：1、如果图中只有一个点，直接结束算法。2、如果图中存在度为1的点，执行3；否则转4。3、任意找一个度为1的点v，将v上的唯一一条边分配给它。转2。4、如果图中的边数等于点数，执行5；否则转6。5、设图中的点数（也就是边数）为n。任取一条边e1，将它分配给它的两个端点中的任意5一个v1；然后将v1上的另一条边e2分配给e2的另一个端点v2；将v2上的另一条边e3分配给e3的另一个端点v3；……如此重复直到将en分配给vn，即图中所有的边都已分配，结束算法。6、将图中权最小的边不分配而直接删去。如果此时图仍然连通，则转2；否则对这个图的两个连通分量分别执行本算法。例6．数字游戏【题目描述】小W发明了一个游戏，他在黑板上写出一行数字a1，a2，…an,然后给你m个回合的机会，每个回合你可以从中选一个数擦除它，接着剩下来的每个数字ai都要递减一个值bi。如此重复m个回合，所有你擦除的数字之和就是你得到的分数。编程帮小W算算，对于每个给出的an和bn序列，可以得到的最大得分是多少？数据输入：由文件game.in提供输入数据。文件的第1行一个整数n（1≤n≤200），表示数字的个数；第二行一个整数m（1≤m≤n），表示回合数；接下来一行有n个不超过10000的正整数，a1，a2，…an，表示原始数字；最后一行有n个不超过500的正整数，b1，b2，…bn，表示每回合每个数字递减的值。结果输出:程序运行结束时，将计算结果输出到文件game.out中。一个整数，表示最大可能的得分。输入文件示例输入：33102030456输出：47【算法分析】本题上面一排数是作为被减数的，若对被减数采用贪心算法不一定能得到全局最优解。因为被减数小减数大，其差小会导致最大得分少。先运用贪心的思想对第二排减数进行从大到小排序，再运用动态规划思想递推求解。#includeiostream//数字游戏usingnamespacestd;structXX{inta,b;}a[201];intn,m,f[2][201],i,j;intcomp(constvoid*a,constvoid*b){return(*(XX*)b).b-(*(XX*)a).b;}intmain()6{freopen(game10.in,r,stdin);freopen(game.out,w,stdout);memset(f,0,sizeof(f));cinnm;for(i=1;i=n;i++)cina[i].aa[i].b;qsort(a+1,n,sizeof(a[0]),comp);for(i=1;i=n;i++)for(j=1;j=min(i,m);j++)f[i%2][j]=max(f[(i-1)%2][j],f[(i-1)%2][j-1]+a[i].a-\a[i].b*(j-1));coutf[n%2][m]endl;return0;}例7．开会问题某公司的会议日益增多，以至于全公司唯一的会议室都不够用了。现在给出这段时期的会议时间表，要求你失单适当删除一些会议，使得剩余的会议在时间上互不冲突，要求删除的会议最少。输入格式：第1行n,表示有n个会议。接下来有n行，每行两个数，si，fi表示会议i的起止时间。输出格式：仅1行，删除的最少会议数d.N=500,si,fi为整型数注意：会议（1，3）和会议（