谈谈贪心算法

谈谈贪心算法谈谈贪心算法安师大附中金孝岱贪心算法是一种符合人们日常思维习惯的简单有效的程序设计算法。贪心算法可用于求解最优问题。在信息学竞赛中常有它的用武之地。略举几个近年来竞赛中的题目就能见到运用贪心算法的踪影: 2006冬令营《风之韵》 2007 noip《纪念品分发》 2007 ioi 中国队选拔赛《挂坠》 2008noip《排序椅》 2008ioi 《传送器》什么是贪心算法,顾名思义～贪心算法总是作出在当前看来是最好的选择。虽然贪心算法不是对所有问题都能得到整体最优解～但对范围相当广的许多问题都...

谈谈贪心算法安师大附中金孝岱贪心算法是一种符合人们日常思维习惯的简单有效的程序设计算法。贪心算法可用于求解最优问题。在信息学竞赛中常有它的用武之地。略举几个近年来竞赛中的题目就能见到运用贪心算法的踪影: 2006冬令营《风之韵》 2007 noip《纪念品分发》 2007 ioi 中国队选拔赛《挂坠》 2008noip《排序椅》 2008ioi 《传送器》什么是贪心算法,顾名思义～贪心算法总是作出在当前看来是最好的选择。虽然贪心算法不是对所有问题都能得到整体最优解～但对范围相当广的许多问题都能产生整体最优解或是问题的次优解。因此有很好研究它的必要。我们先来看看贪心算法在数据结构中的应用。求最小生成树的prim算法中～挑选的顶点是候选边中权值最小的边的一个端点～而加边法的kruskal算法中～更是首先将边的权值从小到大进行排序依次选取。再看看求单源最短路径的算法。其基本算法思想是:设臵顶点集合s并不断作贪心选择～来扩充这个集合～以最终求得最短路径。还有哈夫曼编码也用到贪心算法。 1 贪心算法和分治法及动态规划三者都具有子结构～都是将原问题归纳为更小规模的相似的子问题～并通过求解子问题～最后获得整体解～三者有何不同呢,只有搞清三者的区别～才能很好地运用它们来解决问题。首先是它们的子问题,或称子结构,是不同的。分治法中各子结构是独立的～动态规划一般具有重叠最优子结构～除了必须满足具有最优子结构外～还要满足无后效性。贪心算法要求问题具有最优子结构。其次～在算法实现上看～分治法一旦递归地求出各子结构的解后～便可自下而上地将这些子结构解合并成问题的解。动态规划是所有子问题只计算一次并记录下来～以备后面的子问题使用～用空间换取时间, 所以求当前的解要依赖前面子结构的解。一般采用自底向上的递推方式求解。贪心法则是从上而下～从问题的初始阶段开始每个阶段作一个贪心的选择～不断将问题转换为规模更小的子问题～并期望通过每一次的局部最优选择达到全局最优。贪心算法具有两个重要性质:?最优子结构性质?贪心选择性质用好贪心算法关健是对一个问题能否运用贪心算法的判断和贪心标准的设计。对于一个问题能否用贪心算法要给出严格的证明是件比较困难的事～借助一个称为“拟阵”的工具～可以建立一个关于贪心算法的较一般的理论。这个理论在确定何时使用贪心算法可以得到问题的整体最优解十分有用。但是比较深奥难以理解。我 2 们主要还是根据贪心算法的两个性质～以及运用反证法来证明。更重要的是要通过编程实践多摸素、总结～从而掌握贪心算法。另外运用贪心算法的思想与其它算法相配合～如“枚举+贪心”～“启发+随机化”多次贪心以及用于分支定界上等都有很好的效果。下面通过一些例题来看看如何运用贪心算法。例1.背包问题【题目描述】这是一大家很熟悉的背包问题。给定n种货物和一个载重量为 m的背包。已知第i种货物的重量为wi ,其总价值为pi～编程确定一个装货方案～使得装入背包中货物的总价值最大。输出此总价值和装货方案。【算法分析】 0～1背包问题对每种物品只有两种选择:选和不选～可用动态规划解决。而背包问题～可以选择物品的一部分装载～这样就可以把背包装满～用贪心算法可求得最优解。采用贪心标准是:选择单位重量价值高的货物优先装入～这样才能保证背包中所装货物总价值最大。而0～1背包用贪心算法却不能得到整体最优～为什么呢,我们来看一个例子: 有一背包容量为50千克，有三种货物: 物品1重10千克;价值60元; 物品2重20千克，价值100元; 3 物品3重30千克;价值120元。总价值:,用贪心算法, 20 80+100+60=240 20 对于0～1背包问题～贪心选择之所以不能得到最 10 优解是因为它无法保证最终将背包装满～部分背包的闲臵使单位重量背包空间的价值降低。例2(排队问题【题目描述】在一个医院B 超室～有n个人要做不同身体部位的B超～已知每个人需要处理的时间为ti～,00,从而新的序列比原最优序列好～这与假设矛盾～故s1为最小时间～同理可证s2…sn依次最小。例3(:数列极差问题【题目描述】在黑板上写了N个正整数做成的一个数列～进行如下操作:每一次擦去其中的两个数a和b～然后在数列中加入一个数a×b+1～ 5 如此下去直至黑板上剩下一个数～在所有按这种操作方式最后得到的数中～最大的max～最小的为min～则该数列的极差定义为M=max-min。编程任务:对于给定的数列～编程计算出极差M。输入输出样例: 输入: 4 2 1 4 3 输出: 13 【算法分析】当看到此题时～我们会发现求max与求min是两个相似的过程。若我们把求解max与min的过程分开～着重探讨求max的问题。下面我们以求max为例来讨论此题用贪心策略求解的合理性。讨论:假设经,,,3,次变换后得到？个数:a ,b , max,,max,?,?,,～其中max,是,,,,,个数经,,,？,次,变换后所得的最大值～此时有两种求值方式～设其所求值分别为 z1～z2～则有:z1,(,×,，,,×max,，,～z2,(,×max,，,,×,+,所以z1,z2,max,,,?,若经,,,,,次变换后所得的？个数为:,～,～,,,?,?,,且,不为,,,,,次变换后的最大值～即,,max,则此时所求得的最大值为: 6 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值 7 输出:一个正整数～即满足条件的集合所包含的最少元素个数输入输出样例输入: 输出: 4 4 3 6 2 4 0 2 4 7 【算法分析】本题数据规模较大～用搜索做会超时～而动态规划无从下手。考虑贪心算法。题目意思是要找一个集合～该集合中的数的个数既要少又要和所给定的所有区间有交集。,每个区间至少有两个该集合中的数,。我们可以从所给的区间中选数～为了选尽量少的数～应该使所选的数和更多的区间有交集这就是贪心的标准。一开始将所有区间按照右端点从小到大排序。从第一个区间开始逐个向后检查～看所选出的数与所查看的区间有无交集～有两个则跳过～只有一个数相交～就从当前区间中选出最大的一个数,即右端点,～若无交集～则从当前区间选出两个数～就,右端点～右端点-1,～直至最后一个区间。 #include //整数区间问题 using namespace std; struct prince{ 8 int left,right;//区间左右端点 }a[10000]; int n; int result;//存放结果中的数 int cmp(const void *a,const void *b){ return (*(prince *)a).right-(*(prince *)b).right; } int work(){ qsort(a+1,n,sizeof(a[0]),cmp);//按区间右端点由小到大排序 int i,j,k; int a1,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].left>a2 )//完全不包含 {a1=a[i].right-1;a2=a[i].right;result=result+2;} if (a[i].left>a1 && a[i].right>a2 && a[i].left<=a2) {a1=a2;a2=a[i].right;result++;}//只包含一个 } return result; } int main(){ 9 freopen("range6.in","r",stdin); freopen("range6.out","w",stdout); cin>>n; int i; for(i=1;i<=n;i++) cin>>a[i].left>>a[i].right; cout< 表示这个大陆上的城市数和道路数。接下来有M行～每行包括三个整数i、j,1 i,j N且i , j,、v(1 , V , 10000)～表示一条道路的信息。其中i和j表示这条路在城市i和城市j之间～v表示沿着这条路进行一次交易所得的收益。i和j的顺序是无关的～并且任意两个城市之间最多存在一条路。 11 输出数据你的输出文件应该2行～第1行包含N个整数。其中第k个整数表示你在城市k中的商队将要前往哪个城市进行交易,如果这支商队进行交易的话,或者为0,如果这支商队不进行任何交易,。第2行输出最大收益值。输入输出样例 input.in output.out 样例图示 4 5 2 3 1 2 1 2 40 150 1 3 30 2 3 50 2 4 30 3 4 20 最大收益=40+50+30+30 【算法分析】本题转化成模型就是:在一个无向图中～对于每个点～取一条和它相关联的边,如果这样的边存在的话,～使得取出来的所有边的权和最大。首先～如果这个图是不连通的～那么它的各个连通分量之间是没有任何联系的。对这些连通分量中的问题可以分别独立地解决～合并起来就是整个问题的解。所以我们在下面的讨论中假定图是连 12 通的。直观地考虑～如果图中存在度为1的点～那么就把这一点上的唯一的一条边分配给这个点,将某条边“分配”给某个点的含义是:将这条边作为和这一点相关联的边取出来～同时这一点就失效了～因为和它相关联的其他边都不能再取了,。如果不存在这样的点～那么此时有两种情况:一种是边数等于点数～那么这个图就是一个环～这时可以取出图中所有的边,一种是边数大于点数～那么就可以把这个图中权最小的一条边直接删去～因为这条边“显然”不会被取到的。依据这样一个直观思想～本题可以用贪心法来解决。贪心算法,用于连通图,: 1、如果图中只有一个点～直接结束算法。 2、如果图中存在度为1的点～执行3,否则转4。 3、任意找一个度为1的点v～将v上的唯一一条边分配给它。转2。 4、如果图中的边数等于点数～执行5,否则转6。 5、设图中的点数,也就是边数,为n。任取一条边e1～将它分配给它的两个端点中的任意一个v1,然后将v1上的另一条边e2分配给e2的另一个端点v2,将v2上的另一条边e3分配给e3的另一个端点v3,……如此重复直到将en分配给vn～即图中所有的边都已分配～结束算法。 6、将图中权最小的边不分配而直接删去。如果此时图仍然连通～则转2,否则对这个图的两个连通分量分别执行本算法。 13 例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 中。一个整数～表示最大可能的得分。输入文件示例输入: 3 14 3 10 20 30 4 5 6 输出: 47 【算法分析】本题上面一排数是作为被减数的～若对被减数采用贪心算法不一定能得到全局最优解。因为被减数小减数大～其差小会导致最大得分少。先运用贪心的思想对第二排减数进行从大到小排序～再运用动态规划思想递推求解。 #include//数字游戏 using namespace std; struct XX {int a,b; }a[201]; int n,m,f[2][201],i,j; int comp(const void *a,const void *b) { return(*(XX*)b).b-(*(XX*)a).b; } int main() { freopen ("game10.in","r",stdin); 15 freopen ("game.out","w",stdout); memset(f,0,sizeof(f)); cin>>n>>m; for (i=1;i<=n;i++) cin>>a[i].a>>a[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)); cout<

                    本文档为【谈谈贪心算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

谈谈贪心算法

你可能还喜欢