算法设计-课程设计报告

《算法设计与分析》１什么是算法？算法的特征有哪些？根据我自己的理解，算法是解决问题的方法步骤。比如在解决高数问题的时候，可以分步骤进行解答，在编程的过程算法可以得到最好的体现。算法是一系列解决问题的清晰指令，因为我最近在考研复习，对于会的题目还有进行多次的巩固，但是一步步的写很浪费时间，所以我只是写出关键指令，比如化简通分，洛必达法则，上下同阶。这样可以提高效率。算法的指令也是同样的。能够对一定规范的输入，在有限时间内获得所要求的输出。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。２若给定某一算法，一般如何对其分析与评价？一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。计算机的资源，最重要的是时间和空间（存储器）资源。算法的复杂性有时间复杂性和空间复杂性之分。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:=1tondob[i]:=a[n-i+1];fori:=1tondoa[i]:=b[i];算法2:fori:=1tondiv2dobegint:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=tend;算法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，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。具体代码如下：1.//4d2贪心算法背包问题2.#includestdafx.h3.#includeiostream4.usingnamespacestd;5.6.constintN=3;7.8.voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]);9.10.intmain()11.{12.floatM=50;//背包所能容纳的重量13.//这里给定的物品按单位价值减序排序14.floatw[]={0,10,20,30};//下标从1开始15.floatv[]={0,60,100,120};16.17.floatx[N+1];18.19.cout背包所能容纳的重量为：Mendl;20.cout待装物品的重量和价值分别为：endl;21.for(inti=1;i=N;i++)22.{23.cout[i]:(w[i],v[i])endl;24.}25.26.Knapsack(N,M,v,w,x);27.28.cout选择装下的物品比例如下：endl;29.for(inti=1;i=N;i++)30.{31.cout[i]:x[i]endl;32.}33.34.return0;35.}36.37.voidKnapsack(intn,floatM,floatv[],floatw[],floatx[])38.{39.//Sort(n,v,w);//这里假定w[],v[]已按要求排好序40.inti;41.for(i=1;i=n;i++)42.{43.x[i]=0;//初始化数组x[]44.}45.46.floatc=M;47.for(i=1;i=n;i++)//物品整件被装下,x[i]=148.{49.if(w[i]c)50.{51.break;52.}53.x[i]=1;54.c-=w[i];55.}56.57.//物品i只有部分被装下58.if(i=n)59.{60.x[i]=c/w[i];61.}62.}程序运行结果为：动态规划之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的背包，如何让背包里装入的物品具有最大的价值总和？nameweightvalue12345678910a26066991212151515b23033669991011c65000666661011d54000666661010e460006666666这张表是至底向上，从左到右生成的。为了叙述方便，用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的代码1.publicfunctionget01PackageAnswer(bagItems:Array,bagSize:int):Array2.{3.varbagMatrix:Array=[];4.vari:int;5.varitem:PackageItem;6.for(i=0;ibagItems.length;i++)7.{8.bagMatrix[i]=[0];9.}10.for(i=1;i=bagSize;i++)11.{12.for(varj:int=0;jbagItems.length;j++)13.{14.item=bagItems[j]asPackageItem;15.if(item.weighti)16.{17.//i背包转不下item18.if(j==0)19.{20.bagMatrix[j][i]=0;21.}22.else23.{24.bagMatrix[j][i]=bagMatrix[j-1][i];25.}26.}27.else28.{29.//将item装入背包后的价值总和30.varitemInBag:int;31.if(j==0)32.{33.bagMatrix[j][i]=item.value;34.continue;35.}36.else37.{38.itemInBag=bagMatrix[j-1][i-item.weight]+item.value;39.}40.bagMatrix[j][i]=(bagMatrix[j-1][i]itemInBag?bagMatrix[j-1][i]:itemInBag)41.}42.}43.}44.//findanswer45.varanswers:Array=[];46.varcurSize:int=bagSize;47.for(i=bagItems.length-1;i=0;i--)48.{49.item=bagItems[i]asPackageItem;50.if(curSize==0)51.{52.break;53.}54.if(i==0&&curSize0)55.{56.answers.push(item.name);57.break;58.}59.if(bagMatrix[i][curSize]-bagMatrix[i-1][curSize-item.weight]==item.value)60.{61.answers.push(item.name);62.curSize-=item.weight;63.}64.}65.returnanswers;66.}四结合实际，谈谈本课程学习的收获、体会、建议与意见等。通过算法设计与分析的讲解，我回归了以前的知识点，以前在学习C语言和C++的时候对贪心算法，回溯法，有一些了解，在老师的更细心讲解下我对算法的重要性和策略有更好的理解，在面向对象的时候学会了一个公式编程=数据结构+算法。算法是指令，就像带兵打仗的将军，是挥斥方遒的决定性策略。策略的评估可以用时间复杂度和空间复杂度来计算。