0-1背包问题的算法设计策略对比与分析报告

1、算法设计与分析大作业班级：电子名：学号：任课老师：李 瑞 芳 日期：算法设计与分析课程论文算法设计与分析课程论文0-1 背包问题的算法设计策略对比与分析0-1 背包问题的算法设计策略对比与分析0-1背包问题的算法设计策略对比与分析引言算法将起到决定性的作用。通俗的讲，算法是解决问题的一种方法。也因此“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算 法为例，对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算 法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先 行课课程的知识。算法复杂性分析的方法介绍算法复杂性的高低体现

2、在运行该算法所需要的计算机资源的多少上，所需的资源越多，该算法的（存储器）T(nS(n)之分。算法复杂性是算法运行所需要的计算机资源的量，这个量应集中反映算法的效率，并从运行该算 法的实际计算机中抽象出来，换句话说，这个量应该只依赖要解决的问题规模算法的输入和算法本 和AC=F(N,I,A)T=F(N，I,A)S=F(N，I,A)其中F(N,I,A)是一个三元函数。通A隐含在复杂性函数名当中，因此表达式中一般不A即：C=F(N,I)T=F(N,I)S=F(N,I)算法复杂性中时间与空间复杂性算法相似，所以以下算法复杂性主要以时间复杂性为例：算法的时间复杂性一般分为三种情况：最坏情况、最好情况和

3、平均情况。下面描述算法复杂性时都是用的简化的复杂性算法分析，引入了渐近意义的记号O,，和o。O表示渐近上界表示渐近下界： 表示同阶 即 且 f(n)= 常见的算法分析设计策略介绍递归与分治策略分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。 情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。递归算法举

4、例：共11页 第1页共共11页 第6页共共11页 第7页定义为：Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地1n 0F (n)1n 1F(nF(n2)n 1第n个Fibonacci数可递归地计算如下： int fibonacci(int n)if (n = 1) return 1;return fibonacci(n-1)+fibonacci(n-2);从上看出：递归算法的有点为：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点为：递归算法的运行效率较低，无论是耗费

5、的计算时间还是占用的存储空间都比非递归算法要多。分治算法：kadhoc解1merge将k并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：T (n) n 1kT (n / m) f(n)n logm n1通过迭代法求得方程的解： 算法举例：T (n) nlogm kk f (n/ m j )a0:j 1n元素。据此容易设计出二。搜索算法： templateint BinarySearch(Type a, const Type& x, int l, int r)while (r = int m = if (x = am) return m;

6、if (x am) r = m-1; else l = m+1;return -1;算法设计与分析课程论文算法设计与分析课程论文0-1 背包问题的算法设计策略对比与分析0-1 背包问题的算法设计策略对比与分析算法复杂度分析：每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏情况下， while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。快速排序法：在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就 因而总的比较和移动次数较少。void QuickSort (Type a,

7、 int p, int r)if (pr) int q=Partition(a,p,r);QuickSort (a,p,q-1); QuickSort (a,q+1,r); 复杂性分析：最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn) 辅助空间：O(n)或O(logn)动态规划动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题但是经分解 的答案，就可以避免大量重复计算，从而得到多项式时间算法。方法步骤： 1）递归地定义最优值。以自底向上的方式计算出最优值。举例：矩阵连成问题基本要素： 1）重叠子问题备忘录方法将矩阵连乘积简记Ai:j，这ij考察计算Ai:j的最优计

8、算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为：( A A.A)(A.A )ii1kk k2j计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量。算法如下：void MatrixChain(int *p，int n，int *m，int *s)for (int i = 1; i = n; i+) mii = 0; for (int r = 2; r = n; r+)for (int i = 1; i = n - r+1; i+) int j=i+r-1;mij = mi+1j+ pi-1*pi*pj; sij

9、 = i;for (int k = i+1; k j; k+) int t = mik + mk+1j + pi-1*pk*pj;if (t mij) mij = t; sij = k;算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)， O(n3O(n3O(n2贪心算法顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考 虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是 如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其 最终

10、结果却是最优解的很好近似。可用贪心算法解决的问题的性质： 1） 贪心选择性质2） 最优子结构性质举例：最优装载问题有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。算法描述最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下。templatevoid Loading(int x, Type w, Type c, int n)int *t = new int n+1; Sort(w, t, n);for (int i = 1; i = n; i+)

11、xi = 0;for (int i = 1; i = n & wti half)|(t*(t-1)/2-counthalf) return; if (tn) sum+;elsefor (int i=0;i2;i+) p1t=i;count+=i;for (int j=2;j=t;j+) pjt-j+1=pj-1t-j+1pj-1t-j+2; count+=pjt-j+1;Backtrack(t+1);for (int j=2;j=t;j+) count-=pjt-j+1;count-=i;复杂度分析计算可行性约束需要O(n)时间，在最坏情况下有 O(2n)个结点需要计算可行性约束，故解符号三角

12、形问题的回溯算法所需的计算时间为 O(n2n)。分支限界法分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。常见的两种分支限界法：(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。优先队列式分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。举例:0-1背包问题算法思想：首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。位重量价值的物品装满剩余容

13、量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将 部分算法如下：while (i != n+1) / 非叶结点/ 检查当前扩展结点的左儿子结点Typew wt = cw + wi;if (wt bestp) bestp = cp+pi; AddLiveNode(up, cp+pi, cw+wi, true, i+1); up = Bound(i+1);/ 检查当前扩展结点的右儿子结点if (up = bestp) / /取下一个扩展节点（略）0-10-1背包问题 ： 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装

14、入背包的物品，使得装入背包中物品的总价值最大?动态规划算法：n设所给0-1背包问题的子问题maxv xkkk inw x jkkxki,i k nkm(i，j)，即m(i，j)j，可选择物品为时0-10-1j)的递归式如下。 j),m(i j w )v j wm(i, j) m(i j)iii j wivm(n, j) j wn0 j 0wn算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要(n2n)计算时间。改进算法：由m(i,j)i(1in)m(i,j)是关于变量j的阶梯状单调不减函数。跳跃点是

15、这一类函数的描述特征。在一般情况下， 函数m(i,j)pi存储函数pi可依计算的递归式递归地由表pi+1时pn+1=(0，0)。函数m(i,j)是由函数m(i+1,j)与函数m(i+1,j-wi)+vi作max函数m(i,j)的全部跳跃点包含于函数 m(i+1jpi+1m(i+1， j-wi)+vi 的跳跃点集qi+1 的并集中。易知， (s,t)qi+1 当且仅当wiscpi+1qi+1另一方面，设(a，b)和(c，d)是pi+1qi+1中的2个跳跃点，则当ca且db 时， (c，d)受控于(a，b)，从而(c，d)不是pi中的跳跃点。除受控跳跃点外， pi+1qi+1中的其它跳跃点均为pi

16、中的跳跃点。由此可见，在递归地由表pi+1计算表pi时，可先由pi+1计算出qi+1，然后合并表pi+1和表qi+1，并清除其中的受控跳跃点得到表pi。背包问题的算法设计策略对比与分析改进后复杂性分析：pi(1in)qi+1需要O(|pi+1|)pi+1和并清除受控跳跃点也需要O(|pi+1|)计算时间。从跳跃点集pi的定义可以看出，pi 中的跳跃点相应于xi,xn的0/1赋值。因此，pi中跳跃点个数不超过2n-i+1。由此可见，算法计算跳跃点集pi所花费的计算时间为从而，改进后算法的计算时间复杂性为O(2n)。当所给物品的重量wi(1in)是整数时，|pi|c+(1in)O(minnc,2n贪心算法：i只有2能将物品ii品的部分，使它适合背包问题。不适合0-1背包问题，所以不能用贪心算法计算。回溯法：回溯法的三个条件： 解空间：子集树nw x cn可行性约束函数：ii1i1上界函数：template Typep Knap:Bound(int i)/ 计算上界Typew cleft = c - cw;/Typep b = cp;/ 以物品单位重量价值递减序装入物品while (i = n & wi = cleft) cleft -= wi;b += pi; i+;/ 装满背包if (i = n) b += pi/wi * c