算法设计课程设计报告

1、.算法设计与分析什么是算法？算法的特征有哪些？根据我自己的理解，算法是解决问题的方法步骤。比如在解决高数问题的时候，可以分步骤进行解答，在编程的过程算法可以得到最好的体现。算法是一系列解决问题的清晰指令， 因为我最近在考研复习， 对于会的题目还有进行多次的巩固， 但是一步步的写很浪费时间， 所以我只是写出关键指令， 比如化简通分，洛必达法则，上下同阶。这样可以提高效率。 算法的指令也是同样的。能够对一定规范的输入， 在有限时间内获得所要求的输出。 一个算法的优劣可以用空间复杂度与时间复杂度来衡量。若给定某一算法，一般如何对其分析与评价？一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的

2、多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。计算机的资源，最重要的是时间和空间（存储器）资源。算法的复杂性有时间复杂性和空间复杂性之分。1.时间复杂性：例 1：设一程序段如下（为讨论方便，每行前加一行号）(1) for i:=1 to n do(2) for j:=1 to n do(3) x:=x+1.试问在程序运行中各步执行的次数各为多少？解答：行号 次数(频度)(1) n+1(2) n*(n+1)(3) n*n可见，这段程序总的执行次数是：f(n)=2n2+2n+1 。在这里， n 可以表示问题的规模，当 n 趋向无穷大时，如果f(n

3、)的值很小，则算法优。作为初学者，我.们可以用 f(n)的数量级 O 来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。2.空间复杂性 :例 2:将一一维数组的数据 (n 个)逆序存放到原数组中 ,下面是实现该问题的两种算法 :算法 1:for i:=1 to n dobi:=an-i+1;for i:=1 to n doai:=bi;算法 2:for i:=1 to n div 2 dobegint:=ai;ai:=an-i-1;an-i-1:=tend;算法 1 的时间复杂度为2n,空间复杂度为2n算法 2 的时间复杂度为3*n/2, 空间复杂度为 n+

4、1显然算法 2 比算法 1 优，这两种算法的空间复杂度可粗略地表示为S(n)=O(n)3、从下面算法策略中自选一组，结合某具体问题的求解来介绍算法思想，并加以总结、比较：递归与分治、动态规划与贪心法、回溯法与分支限界法动态规划算法类似于分治法， 基本思想也是将待求解问题分解成若干个子问题。化整为零，减少了运算量。贪心算法，是永不知足的求最优解，有点类似于我们所说的完美主义者。两者之间有相同点， 总结来说某种程度上， 动规是贪心的泛化， 贪心是动规的特例贪心： A 最优 +B 最优动态规划：（ A+B）最优就单步而言.贪心的 A 最优是前一步的结果， B 最优需要遍历找到动态规划的 A 为前一步

5、的可行解，需要选择一个B 后再去找 A动态规划算法之 0-1 背包问题：给定 n 种物品和一个背包。物品 i 的重量是Wi，其价值为 Vi，背包的容量为 C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大 ?与 0-1 背包问题类似，所不同的是在选择物品 i 装入背包时，可以选择物品 i 的一部分，而不一定要全部装入背包， 1in。这 2 类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而 0-1 背包问题却不能用贪心算法求解。 用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值 Vi/Wi ，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品

6、装入背包。 若将这种物品全部装入背包后， 背包内的物品总重量未超过 C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。具体代码如下：1. /4d2 贪心算法 背包问题2. #include "stdafx.h"3. #include <iostream>4. using namespace std;5.6. const int N = 3;7.8. void Knapsack(int n,float M,float v,float w,float x);9.10. int main()11. 12. float M

7、= 50;/ 背包所能容纳的重量.13. / 这里给定的物品按单位价值减序排序14. float w = 0,10,20,30;/ 下标从 1 开始15. float v = 0,60,100,120;16.17. float xN+1;18.19. cout<<" 背包所能容纳的重量为： "<<M<<endl;20. cout<<" 待装物品的重量和价值分别为： "<<endl;21. for(int i=1; i<=N; i+)22. 23. cout<<"&qu

8、ot;<<i<<":("<<wi<<","<<vi<<")"<<endl;24. 25.26. Knapsack(N,M,v,w,x);27.28. cout<<" 选择装下的物品比例如下： "<<endl;29. for(int i=1; i<=N; i+)30. 31. cout<<""<<i<<":"<<xi&

9、lt;<endl;32. 33.34. return 0;35. .36.37. void Knapsack(int n,float M,float v,float w,float x)38. 39. /Sort(n,v,w);/ 这里假定 w,v 已按要求排好序40. int i;41. for (i=1;i<=n;i+)42. 43. xi=0;/ 初始化数组 x44. 45.46. float c=M;47. for (i=1;i<=n;i+)/ 物品整件被装下 ,xi=148. 49. if (wi>c)50. 51.break;52. 53. xi=1;54.

10、 c-=wi;55. 56.57. / 物品 i 只有部分被装下58. if (i<=n).59. 60. xi=c/wi;61. 62. 程序运行结果为：动态规划之 01 背包状态转换方程 fi,j = Max fi-1,j-Wi+Pi( j >= Wi ),fi-1,j fi,j表示在前 i 件物品中选择若干件放在承重为j 的背包中，可以取得的最大价值。Pi 表示第 i 件物品的价值。决策：为了背包中物品总价值最大化，第i 件物品应该放入背包中吗？题目描述：有编号分别为 a,b,c,d,e 的五件物品，它们的重量分别是 2,2,6,5,4，它们的价值分别是 6,3,5,4,6，

11、现在给你个承重为 10 的背包，如何让背包里装入的物品具有最大的价值总和？naweval1234567891meightue0a26066991111122555b230336699911.01c65000666661101d54000666661100e460006666666这张表是至底向上，从左到右生成的。为了叙述方便，用e2 单元格表示 e 行 2 列的单元格，这个单元格的意义是用来表示只有物品 e 时，有个承重为 2 的背包，那么这个背包的最大价值是0，因为 e 物品的重量是 4，背包装不了。对于 d2 单元格，表示只有物品 e，d 时,承重为 2 的背包 ,所能装入的最大价值，仍然

12、是 0，因为物品 e,d 都不是这个背包能装的。同理， c2=0 ，b2=3,a2=6 。对于承重为 8 的背包， a8=15, 是怎么得出的呢？根据 01 背包的状态转换方程，需要考察两个值，一个是 fi-1,j, 对于这个例子来说就是b8 的值 9，另一个是 fi-1,j-Wi+Pi ；在这里，fi-1,j 表示我有一个承重为8 的背包，当只有物品b,c,d,e 四件可选时，这个背包能装入的最大价值fi-1,j-Wi 表示我有一个承重为6 的背包（等于当前背包承重减去物品a 的重量），当只有物品b,c,d,e 四件可选时，这个背包能装入的最大价值fi-1,j-Wi 就是指单元格b6,值为

13、9，Pi 指的是 a 物品的价值，即6.由于 fi-1,j-Wi+Pi = 9 + 6 = 15大于 fi-1,j = 9 ，所以物品 a 应该放入承重为8的背包以下是 actionscript3的代码1. public function get01PackageAnswer(bagItems:Array,bagSize:int):Array2. 3. var bagMatrix:Array=;4. var i:int;5. var item:PackageItem;6. for(i=0;i<bagItems.length;i+)7. 8.bagMatrixi = 0;9. 10. fo

14、r(i=1;i<=bagSize;i+)11. 12. for(var j:int=0;j<bagItems.length;j+)13. 14.item = bagItemsj as PackageItem;15.if(item.weight > i)16.17./i 背包转不下 item18.if(j=0)19.20.bagMatrixji= 0;21.22.else23.24.bagMatrixji=bagMatrixj-1i;25.26.27.else28.29./ 将 item 装入背包后的价值总和30.var itemInBag:int;31.if(j=0)32.3

15、3.bagMatrixji= item.value;34.continue;35.36.else37.38.itemInBag =bagMatrixj-1i-item.weight+item.value;39.40.bagMatrixji = (bagMatrixj-1i > itemInBag ? bagMatrixj-1i : itemInBag)41.42. 43. 44. /find answer45. var answers:Array=;46. var curSize:int = bagSize;47. for(i=bagItems.length-1;i>=0;i-)48. 49. item = bagItemsi as PackageItem;50. if(curSize=0)51. 52.break;53. 54. if(i=0 && curSize > 0)55. 56.answers.push();57.break;58. 59. if(bagMatrixicurSize-bagMatrixi-1curSize-item.weight=item.value)60. 61.answers.push();62.curSiz