贪心算法的应用实例.doc

《贪心算法的应用实例.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、贪心算法的应用实例例2．排队问题【题目描述】在一个医院B超室，有n个人要做不同身体部位的B超，已知每个人需要处理的时间为ti，（0

2、k之后的人无影响，对sk之前的人等待都减少了，(s1-sk)>0,从而新的序列比原最优序列好，这与假设矛盾，故s1为最小时间，同理可证s2…sn依次最小。例3．:数列极差问题【题目描述】在黑板上写了N个正整数做成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a×b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。编程任务：对于给定的数列，编程计算出极差M。输入输出样例：输入：42143输出：13【算法分析】当看到此题时，我们会发现求max与求min是两

3、个相似的过程。若我们把求解max与min的过程分开，着重探讨求max的问题。下面我们以求max为例来讨论此题用贪心策略求解的合理性。讨论：假设经（Ｎ－3）次变换后得到３个数：a,b,max＇（max＇≥ａ≥ｂ），其中max＇是（Ｎ－２）个数经（Ｎ－３）次ｆ变换后所得的最大值，此时有两种求值方式，设其所求值分别为z1，z2，则有：z1＝(ａ×ｂ＋１）×max＇＋１，z2＝(ａ×max＇＋１）×ｂ+１所以z1－z2＝max＇－ｂ≥０若经（Ｎ－２）次变换后所得的３个数为：ｍ，ａ，ｂ（ｍ≥ａ≥ｂ）且ｍ不为（Ｎ－２）次变换后的最大值，即ｍ＜max＇则此时所求得的最大值为：z3＝（ａ×

4、ｂ+１）×ｍ+１此时z1－z3＝(１+ａｂ）（max＇－ｍ）＞０　所以此时不为最优解。所以若使第ｋ（１≤ｋ≤Ｎ－１）次变换后所得值最大，必使（ｋ－１）次变换后所得值最大（符合贪心策略的特点2），在进行第ｋ次变换时，只需取在进行（ｋ－１）次变换后所得数列中的两最小数ｐ，ｑ施加ｆ操作：ｐ←ｐ×ｑ+1，ｑ←∞即可（符合贪心策略特点1），因此此题可用贪心策略求解。在求ｍin时，我们只需在每次变换的数列中找到两个最大数ｐ，ｑ施加作用ｆ：ｐ←ｐ×ｑ+１，ｑ←-∞即可．原理同上。这是一道两次运用贪心策略解决的一道问题，它要求选手有较高的数学推理能力。例4．整数区间range.cpp【题目

5、描述】我们定义一个整数区间[a,b],a,b是一个从a开始至b结束的连续整数的集合。编一个程序，对给定的n个区间，找出满足下述条件的所含元素个数最少的集合中元素的个数：对于所给定的每一个区间，都至少有两个不同的整数属于该集合。(1<=n<=10000,0<=a<=b<=1000)输入输出格式：输入：第一行一个正整数n，接下来有n行，每行给定一个区间的a,b值输出：一个正整数，即满足条件的集合所包含的最少元素个数输入输出样例输入：输出：4436240247【算法分析】本题数据规模较大，用搜索做会超时，而动态规划无从下手。考虑贪心算法。题目意思是要找一个集合，该集合中的数的个数

6、既要少又要和所给定的所有区间有交集。（每个区间至少有两个该集合中的数）。我们可以从所给的区间中选数，为了选尽量少的数，应该使所选的数和更多的区间有交集这就是贪心的标准。一开始将所有区间按照右端点从小到大排序。从第一个区间开始逐个向后检查，看所选出的数与所查看的区间有无交集，有两个则跳过，只有一个数相交，就从当前区间中选出最大的一个数（即右端点），若无交集，则从当前区间选出两个数，就（右端点，右端点-1），直至最后一个区间。#include//整数区间问题usingnamespacestd;structprince{intleft,right;//区间左右

7、端点}a[10000];intn;intresult;//存放结果中的数intcmp(constvoid*a,constvoid*b){return(*(prince*)a).right-(*(prince*)b).right;}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