文档介绍：该【算法设计 课程设计报告 】是由【君。好】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【算法设计 课程设计报告 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告《算法设计与分析》1什么就就是算法?算法得特征有哪些?根据我自己得理解,算法就就是解决问题得方法步骤。比如在解决高数问题得时候,可以分步骤进行解答,在编程得过程算法可以得到最好得体现。算法就就是一系列解决问题得清晰指令,因为我最近在考研复****对于会得题目还有进行多次得巩固,但就就是一步步得写很浪费时间,所以我只就就是写出关键指令,比如化简通分,洛必达法则,上下同阶。这样可以提高效率。算法得指令也就就是同样得。能够对一定规范得输入,在有限时间内获得所要求得输出。一个算法得优劣可以用空间复杂度与时间复杂度来衡量。2 若给定某一算法,一般如何对其分析与评价?一个算法得复杂性得高低体现在运行该算法所需要得计算机资源得多少上面,所需得资源越多,我们就说该算法得复杂性越高;反之,所需得资源越低,则该算法得复杂性越低。计算机得资源,最重要得就就是时间和空间(存储器)资源。算法得复杂性有时间复杂性和空间复杂性之分。1、时间复杂性:例1:设一程序段如下(为讨论方便,每行前加一行号)(1)fori:=1tondo(2) forj:=1tondo(3)x:=x+1、、、、、、试问在程序运行中各步执行得次数各为多少?解答:行号次数(频度)(1)n+1(2)n*(n+1)(3) n*n可见,这段程序总得执行次数就就是:f(n)=2n2+2n+1。在这里,n可以表示问题得规模,当n趋向无穷大时,如果f(n)得值很小,则算法优。作为初学者,我们可以用f(n)得数量级O来粗略地判断算法得时间复杂性,如上例中得时间复杂性可粗略地表示为T(n)=O(n2)。2、空间复杂性:例2:将一一维数组得数据(n个)逆序存放到原数组中算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告,下面就就是实现该问题得两种算法:算法1:fori:=1tondo b[i]:=a[n-i+1]; fori:=1tondoa[i]:=b[i];算法2:fori:=1ton div2 do begin t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t end;算法1得时间复杂度为2n,空间复杂度为2n算法2得时间复杂度为3*n/2,空间复杂度为n+1显然算法2比算法1优,这两种算法得空间复杂度可粗略地表示为S(n)=O(n)3、从下面算法策略中自选一组,结合某具体问题得求解来介绍算法思想,并加以总结、比较: 递归与分治、动态规划与贪心法、回溯法与分支限界法动态规划算法类似于分治法,基本思想也就就是将待求解问题分解成若干个子问题。化整为零,减少了运算量。贪心算法,就就是永不知足得求最优解,有点类似于我们所说得完美主义者。两者之间有相同点,总结来说某种程度上,动规就就是贪心得泛化,贪心就就是动规得特例贪心:A最优+B最优动态规划:(A+B)最优就单步而言贪心得A最优就就是前一步得结果,B最优需要遍历找到动态规划得A为前一步得可行解,需要选择一个B后再去找A动态规划算法之0-1背包问题:给定n种物品和一个背包。物品i得重量就就是Wi,其价值为Vi,背包得容量为C。应如何选择装入背包得物品,使得装入背包中物品得总价值最大?算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告?与0-1背包问题类似,所不同得就就是在选择物品i装入背包时,可以选择物品i得一部分,而不一定要全部装入背包,1≤i≤n。?????这2类问题都具有最优子结构性质,极为相似,但背包问题可以用贪心算法求解,而0-1背包问题却不能用贪心算法求解。用贪心算法解背包问题得基本步骤就就是,首先计算每种物品单位重量得价值Vi/Wi,然后,依贪心选择策略,将尽可能多得单位重量价值最高得物品装入背包。若将这种物品全部装入背包后,背包内得物品总重量未超过C,则选择单位重量价值次高得物品并尽可能多地装入背包。依此策略一直地进行下去,直到背包装满为止。????具体代码如下://4d2?贪心算法?背包问题??#include?"stdafx、h"??#include?<iostream>???using?namespace?std;?????const?int?N?=?3;????void?Knapsack(int?n,float?M,float?v[],float?w[],float?x[]);????int?main()??{??????float?M?=?50;//背包所能容纳得重量??????//这里给定得物品按单位价值减序排序??算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告????float?w[]?=?{0,10,20,30};//下标从1开始??????float?v[]?=?{0,60,100,120};????????float?x[N+1];????????cout<<"背包所能容纳得重量为:"<<M<<endl;??????cout<<"待装物品得重量和价值分别为:"<<endl;??????for(int?i=1;?i<=N;?i++)??????{??????????cout<<"["<<i<<"]:("<<w[i]<<","<<v[i]<<")"<<endl;??????}????????????Knapsack(N,M,v,w,x);????????cout<<"选择装下得物品比例如下:"<<endl;??????for(int?i=1;?i<=N;?i++)??????{??????????cout<<"["<<i<<"]:"<<x[i]<<endl;??????}????算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告????return?0;??}????void?Knapsack(int?n,float?M,float?v[],float?w[],float?x[])??{??????//Sort(n,v,w);//这里假定w[],v[]已按要求排好序??????int?i;??????for?(i=1;i<=n;i++)??????{??????????x[i]=0;//初始化数组x[]??????}????????float?c=M;??????for?(i=1;i<=n;i++)//物品整件被装下,x[i]=1??????{??????????if?(w[i]>c)??????????{??????????????break;??????????}??????????x[i]=1;??算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告????????c-=w[i];??????}????????//物品i只有部分被装下??????if?(i<=n)??????{??????????x[i]=c/w[i];??????}??}??程序运行结果为:动态规划之01背包状态转换方程?f[i,j]=Max{ f[i-1,j-Wi]+Pi(j>=Wi), ?f[i-1,j]}f[i,j]表示在前i件物品中选择若干件放在承重为j得背包中,可以取得得最大价值。Pi表示第i件物品得价值。决策:为了背包中物品总价值最大化,第 i件物品应该放入背包中吗?题目描述:有编号分别为a,b,c,d,e得五件物品,她们得重量分别就就是2,2,6,5,4,她们得价值分别就就是6,3,5,4,6,现在给您个承重为10得背包,如何让背包里装入得物品具有最大得价值总和?算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告nameweightvalue**********a26066991212151515b23033669991011c65000666661011d54000666661010e460006666666这张表就就是至底向上,从左到右生成得。为了叙述方便,用e2单元格表示e行2列得单元格,这个单元格得意义就就是用来表示只有物品e时,有个承重为2得背包,那么这个背包得最大价值就就是0,因为e物品得重量就就是4,背包装不了。对于d2单元格,表示只有物品e,d时,承重为2得背包,所能装入得最大价值,仍然就就是0,因为物品e,d都不就就是这个背包能装得。同理,c2=0,b2=3,a2=6。对于承重为8得背包,a8=15,就就是怎么得出得呢?根据01背包得状态转换方程,需要考察两个值,一个就就是f[i-1,j],对于这个例子来说就就就是b8得值9,另一个就就是f[i-1,j-Wi]+Pi;算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告在这里,?f[i-1,j]表示我有一个承重为8得背包,当只有物品b,c,d,e四件可选时,这个背包能装入得最大价值f[i-1,j-Wi]表示我有一个承重为6得背包(等于当前背包承重减去物品a得重量),当只有物品b,c,d,e四件可选时,这个背包能装入得最大价值f[i-1,j-Wi]就就就是指单元格b6,值为9,Pi指得就就是a物品得价值,即6由于f[i-1,j-Wi]+Pi=9+6=15大于f[i-1,j]=9,所以物品a应该放入承重为8得背包以下就就是actionscript3得代码public?function?get01PackageAnswer(bagItems:Array,bagSize:int):Array??{??????var?bagMatrix:Array=[];??????var?i:int;??????var?item:PackageItem;??????for(i=0;i<bagItems、length;i++)??????{??????????bagMatrix[i]?=?[0];??????}??????for(i=1;i<=bagSize;i++)??????{??算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告????????for(var?j:int=0;j<bagItems、length;j++)??????????{??????????????item?=?bagItems[j]?as?PackageItem;??????????????if(item、weight?>?i)??????????????{??????????????????//i背包转不下item??????????????????if(j==0)??????????????????{??????????????????????bagMatrix[j][i]?=?0;??????????????????}??????????????????else??????????????????{??????????????????????bagMatrix[j][i]=bagMatrix[j-1][i];??????????????????}??????????????}??????????????else??????????????{??????????????????//将item装入背包后得价值总和??????????????????var?itemInBag:int;??????????????????if(j==0)??算法设计课程设计报告算法设计课程设计报告算法设计课程设计报告????????????????{??????????????????????bagMatrix[j][i]?=?item、value;??????????????????????continue;??????????????????}??????????????????else??????????????????{??????????????????????itemInBag?=?bagMatrix[j-1][i-item、weight]+item、value;??????????????????}??????????????????bagMatrix[j][i]?=?(bagMatrix[j-1][i]?>?itemInBag???bagMatrix[j-1][i]?:?itemInBag)??????????????}??????????}??????}??????//find?answer??????var?answers:Array=[];??????var?curSize:int?=?bagSize;??????for(i=bagItems、length-1;i>=0;i--)??????{??????????item?=?bagItems[i]?as?PackageItem;??????????if(curSize==0)??????????{