谈谈贪心算法下载_Word模板_19

is_721103

暂无简介

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

谈谈贪心算法安师大附中金孝岱贪心算法是一种符合人们日常思维习惯的简单有效的程序

设计

领导形象设计圆作业设计 ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计

算法。贪心算法可用于求解最优问题。在信息学竞赛中常有它的用武之地。略举几个近年来竞赛中的题目就能见到运用贪心算法的踪影: 2006冬令营《风之韵》 2007 noip《纪念品分发》 2007 ioi 中国队选拔赛《挂坠》 2008noip《排序椅》 2008ioi 《传送器》什么是贪心算法,顾名思义～贪心算法总是作出在当前看来是最好的选择。虽然贪心算法不是对所有问题都能得到整体最优解～但对范围相当广的许多问题都能产生整体最优解或是问题的次优解。因此有很好研究它的必要。我们先来看看贪心算法在数据结构中的应用。求最小生成树的prim算法中～挑选的顶点是候选边中权值最小的边的一个端点～而加边法的kruskal算法中～更是首先将边的权值从小到大进行排序依次选取。再看看求单源最短路径的算法。其基本算法思想是:设臵顶点集合s并不断作贪心选择～来扩充这个集合～以最终求得最短路径。还有哈夫曼编码也用到贪心算法。 1 贪心算法和分治法及动态规划三者都具有子结构～都是将原问题归纳为更小规模的相似的子问题～并通过求解子问题～最后获得整体解～三者有何不同呢,只有搞清三者的区别～才能很好地运用它们来解决问题。首先是它们的子问题,或称子结构,是不同的。分治法中各子结构是独立的～动态规划一般具有重叠最优子结构～除了必须满足具有最优子结构外～还要满足无后效性。贪心算法要求问题具有最优子结构。其次～在算法实现上看～分治法一旦递归地求出各子结构的解后～便可自下而上地将这些子结构解合并成问题的解。动态规划是所有子问题只计算一次并记录下来～以备后面的子问题使用～用空间换取时间, 所以求当前的解要依赖前面子结构的解。一般采用自底向上的递推方式求解。贪心法则是从上而下～从问题的初始阶段开始每个阶段作一个贪心的选择～不断将问题转换为规模更小的子问题～并期望通过每一次的局部最优选择达到全局最优。贪心算法具有两个重要性质:?最优子结构性质?贪心选择性质用好贪心算法关健是对一个问题能否运用贪心算法的判断和贪心标准的设计。对于一个问题能否用贪心算法要给出严格的证明是件比较困难的事～借助一个称为“拟阵”的工具～可以建立一个关于贪心算法的较一般的理论。这个理论在确定何时使用贪心算法可以得到问题的整体最优解十分有用。但是比较深奥难以理解。我 2 们主要还是根据贪心算法的两个性质～以及运用反证法来证明。更重要的是要通过编程实践多摸素、总结～从而掌握贪心算法。另外运用贪心算法的思想与其它算法相配合～如“枚举+贪心”～“启发+随机化”多次贪心以及用于分支定界上等都有很好的效果。下面通过一些例题来看看如何运用贪心算法。例1.背包问题【题目描述】这是一大家很熟悉的背包问题。给定n种货物和一个载重量为 m的背包。已知第i种货物的重量为wi ,其总价值为pi～编程确定一个装货

方案

气瓶现场处置方案 .pdf 气瓶现场处置方案 .doc 见习基地管理方案.doc 关于群访事件的化解方案建筑工地扬尘治理专项方案下载

～使得装入背包中货物的总价值最大。输出此总价值和装货方案。【算法

分析

定性数据统计分析pdf 销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析

】 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) 输入输出

格式

pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载

: 输入:第一行一个正整数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<//数字游戏 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<方法

快递客服问题件处理详细方法山木方法pdf 计算方法pdf 华与华方法下载八字理论方法下载

:首先将所有会议按结束时间从小到大排序～每次总是安排结束时间早的会议～这样不仅安排了一个会议～同时又为剩余的会议留下尽可能的时间。例8(智力大冲浪【题目描述】小伟报名参加电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者～主持人为了表彰大家的勇气～先奖励每个参赛者m元。接下来主持人宣布比赛规则:首先～比赛时间分为n个时段,n<=500,,它又给出了很多小游戏～每个小游戏都必须在规定期限ti前完成,i<=ti<=n,。如果一个游戏不能在规定期限完成～则要从奖励费m元中扣去一部分钱wi～wi 为自然数～不同的游戏扣去的钱数不同。当然每个游戏本身都很简单～保证每个参赛者都能在一个时段内完成～而且都必须从整数段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。问小伟最多能得到多少钱, 17 输入:第1行为m～表示一开始奖励给每个参赛者的钱数第2行为n表示有n个小游戏。第3行有n个数～分别表示n个游戏规定完成的期限第4行有n个数～分别表示n个游戏不能在规定期限完成的扣款数输出:仅一个数～表示小伟能赢得最多的钱数。样例: 输入: 10000 7 4 2 4 3 1 4 6 70 60 50 40 30 20 10 输出: 9950 【算法分析】因为不同的小游戏不能准时完成时具有不同的扣款权数～而且是最优解问题～所以本题很容易就想到了贪心法。贪心的主要思想是要让扣款数值大的尽量准时完成。这样我们就先把这些任务按照扣款的数目进行排序～把大的排在前面～先进行放臵。假如罚款最多的一个任务的完成期限是k～我们应该把它安排在哪个时段完成呢,应该放在第k个时段～因为放在1，k任意一个位臵～效果都是一样的。一旦出现一个不可能在规定时限前完成的任务～则把 18 其扔到最大的一个空时间段～这样必然是最优的～因为不能完成的任务～在任意一个时间段中罚款数目都是一样的. 本题也可以有另外一种贪心算法～即先把所有的数据按照结束时间的先后排序～然后从前向后扫描。当扫描到第n个时段～发现里面所分配任务的结束时间等于n-1～那么就说明在前面这些任务中必须舍弃一个～于是再扫描第1，n这n个时段～挑出一个最小的去掉并累加扣款值～然后再去调整排列顺序～让后面的元素填补前面的空缺～例9(合并果子,fruit.pas,。【题目描述】在一个果园里～多多已经将所有的果子打了下来～而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并～多多可以把两堆果子合并到一起～消耗的体力等于两堆果子的重量之和。可以看出～所有的果子经过n-1次合并之后～就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家～所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1～并且已知果子的种类数和每种果子的数目～你的任务是设计出合并的次序方案～使多多耗费的体力最少～并输出这个最小的体力耗费值。 19 例如～有3种果子～数目依次为1、2、9。可以先将1、2堆合并～新堆数目为3～耗费体力为3。接着～将新堆与原先的第三堆合并～又得到新的堆～数目为12～耗费体力为12。所以多多总共耗费体力15=3+12。可以证明15为最小的体力耗费值。【输入】输入文件fruit.in包括两行。第一行是一个整数n(1?n?10000)～表示果子的种类数。第二行包含n个整数～用空格分隔～第i个整数ai(1?ai?20000)是第i种果子的数目。【输出】输出文件fruit.out包括一行～这一行只包含一个整数～也就是最小的体力耗费值。输入数据保证这个值小于231。【样例输入】 3 1 2 9 【样例输出】 15 【数据规模】对于30%的数据～保证有n?1000, 对于50%的数据～保证有n?5000, 对于全部的数据～保证有n?10000。【算法分析】此题用贪心法。先将果子数排序～取其中最小的两堆合并～得 20 到一个新堆,再排序～再取其中最小的两堆合并……直到只剩一堆。为尽快出解～排序的速度显得格外重要～可用堆排序算法。例10( 建筑抢修,repair.pas,。【题目描述】小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏。经过了一场激烈的战斗～T部落消灭了所有Z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤～如果不尽快修复的话～这些建筑设施将会完全毁坏。现在的情况是:T部落基地里只有一个修理工人。虽然他能瞬间到达任何一个建筑～但是修复每个建筑都需要一定的时间。同时～修理工人修理完一个建筑才能修理下一个建筑～不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕～这个建筑就报废了。你的任务是帮小刚合理制定一个修理顺序～以抢修尽可能多的建筑。【输入】输入文件第一行是一个整数N～N行每行两个整数T1、T2描述一个建筑:修理这个建筑需要T1秒～如果在T2秒之内还没有修理完成～这个建筑就报废了。【输出】 21 输出文件只有一行～是一个整数S～表示最多可以抢修S个建筑。 N,150000; T1,T2,maxlongint 【样例输入】 4 100 200 200 1300 1000 1250 2000 3200 【样例输出】 3 【算法分析】贪心 O(N Log N) + 高级数据结构。很容易想到动态规划。按截止时间排序～维护队列q～如果能插入就插入～如不能插入～就把一个花费时间最大的替换下来贪心算法和贪心思想看似简单～真正完全掌握要下一番功夫。和任何优秀算法一样～贪心算法也有它的局限性～用不对会丢很多解～用得好～在编程中能起到事半功倍的效果。有不对之处请指正～谢谢大家: 22 23

本文档为【谈谈贪心算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

谈谈贪心算法

热门搜索

历史搜索