算法分析与设计课程的设计论文

1、 信息技术学院 算法设计与分析课程考查论文 题 目 0 0- -1 1 背包问题的算法设计谋略比照与分析 专业 计算机科学与技术 班级 20062006 级软件方向 学 号 061124015061124015 姓 名 _ 刘翠兰 _ 任 课教师 _ 宋振方 _ 完成日期 20212021 年 1212 月 3131 日2006级软件方向算法设计与分析课程考查论文 第1页共14页 0-1背包问题的算法设计谋略比照与分析 0引言 对于计算机科学来说， 算法的概念是至关重要的， 例如，在一个大型软件系统的开发中， 设计出 有效的算法将起决定性的作用。算法是解决问题的一种方法或一个过程。程序是算法用

2、某种设计语 言具体实现描。计算机的普及极大的改变了人们的生活。目前，各行业、各领域都广泛采用了计算 机信息技术，并由此产生出开发各种应用软件的需求。为了以最小的本钱、最快的速度、最好的质 量开发出适合各种应用需求的软件，必须遵循软件工程的原那么。设计一个高效的程序不仅需要编程 小技巧，更需要合理的数据组织和清晰高效的素算法，这正是计算机科学领域数据结构与算法设计 所研究的主要内容。 1算法复杂性分析的方法介绍 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为 时间复杂性，需要的 空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本 身的函数。如

3、果分别用 M I和A表示算法要解问题的规模、算法的输入和算法本身，而且用 决示复 杂性，那么，应该有 C=F(N,I,A)。一般把时间复杂性和空间复杂性分开，并分别用 讶日S来表示，那么 有：T=T(N,I)和S=S(N,I)。(通常，让A急含在复杂性函数名当中 最坏情况下的时间复杂性： k Tmax(N) = max T (N , I ) = max 值(N , I ) I - D N I z D N i _1 最好情况下的时间复杂性： k MN) = min T(N , I) = min (N ,I ) r DN R DN 平均情况下的时间复杂性： Tavg(N) = Z P(I)T(N,

4、I) = Z P(I )L ti6i(N,I) I DN D N i 其中D睡规模为N勺合法输入的集合；I*是DN中使T(N, I*) 到达Tmax(N)的合法输入； 是中使 T(N,)到达Tmin(N)的合法输入；而P(I)是在算法的应用中出现输入 I的概率。 算法复杂性在渐近意义下的阶： 渐近意义下的记号：Q Q、。、o设f(N)和g(N)是定义在正数集上的正函数。 邸定义：如果存在正的常数 3日自然数N0,使得当NN0时有f(N) Cg(N)，那么称函数f(N)当N分大 时下有界，且g(N)是它的一个下界，记为f(N)= Q (g(N)。即f(N)的阶不低于g(N)的阶。 0的定义：定义

5、f(N)= 0 (g(N)当且仅当f(N)=O(g(N) 且f(N)= Q (g(N)。此时称f(N)与g(N)同阶。 。的定义：对于任意给定的 0,都存在正整数N0,使得当N浏0寸有f(N)/Cg(N) &，那么称函数f(N) 当N充分大时的阶比g(N)低，记为f(N)=o(g(N)。 k = tie(N, I i z! * = T(N,I )= T(N,I ) = T(N ,I )= T(N ,I ) =寸 ti6i(N , I ) i =1 0-1背包问题的算法设计谋略比照与分析 第2页共14页 例如，4NlogN+7=o(3N2+4NlogN+7)。 2常见的算法分析设计谋略介

6、绍 2.1递归与分治策略 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各 个击破，分而治之。对这 k个子问题分别求解。如果子问题的规模仍然不够小，那么再划分为 k个子问 题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。将求出的小规模的问题的 解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。由于分治法产生的子问题往 往是原来问题的较小规模，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段， 可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易求出其解。由此 自然引出递归算法。分治与递归像是一对挛生

7、兄弟，经常同时应用在算法设计之中，并由此产生许 多高效的算法。 2.2动态规划 动态规划算法与分治法类似，其根本思想也是将待求解问题分解成假设干个子问题。但是经分解得 到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有 些子问题被重复计算了许屡次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的 答案，就可以防止大量重复计算，从而得到多项式时间算法。 动态规划的一般步骤：找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 2.3贪心算法 顾名思义，贪心算法总是作出在当前

8、看来最好的选择。也就是说贪心算法并不从整体最优考虑， 它所作出的选择只是在某种意义上的局部最优选择。具有最优子结构性质的问题，用贪心算法更简 单、更直接且解题效率更高。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法 不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最 小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很 好近似。 2.4回溯法 有许多问题，当需要找出它的解集或者要求答复什么解是满足某些约束条件的最正确解时， 往往要使 用回溯法。 回溯法的根本做法是搜索，或是一种组织得井井有条的，能防止不必要搜索

9、的穷举式搜索法。这 种方法适用于解一些组合数相当大的问题。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间 树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，那么跳过对该结点为根的子树 的搜索，逐层向其祖先结点回溯；否那么，进入该子树，继续按深度优先策略搜索。 问题的解向量：回溯法希望一个问题的解能够表示成一个 n元式(x1,x2,xn)的形式。 显约束：对分量xi的取值限定。 隐约束：为满足问题的解而对不同分量之间施加的约束。 解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空 间。2006级软件方向算法设

10、计与分析课程考查论文 第11页共14页 3 2.5分支限界法 分支限界法常以广度优先或以最小消耗(最大效益)优先的方式搜索问题的解空间树。在分支限 界法中，每一个活结点只有一次时机成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所 有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点 被参加活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续 到找到所需的解或活结点表为空时为止。 从活结点表中选择下一扩展结点的不同方式导致不同的分 支限界法： 队列式(FIFO)分支限界法：按照队列先进先出( FIFO)原那么

11、选取下一个节点为扩展节点。 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 最大优先队列：使用最大堆，表达最大效益优先 最小优先队列：使用最小堆，表达最小费用优先 3结合0-1背包问题详述动态规划、贪心算法、回溯法、分支限界法解决问题的过程 0-1背包问题：给定 n种物品和一个背包。物品 i的重量是 Wi,其价值为Vi ,背包的容量是 c。 问应如何选择装入背包中的物品，使得装入背包中的物品总价值最大。在选择装入背包的物品时， 对每种物品i只能有两种选择，装入包或者不装入。不能物品 i装入包屡次，也不能之装入局部的 物品io 3.1动态规划算法 问题描述

12、 此问题的形式化描述是， 给定c0,Wi0,Vi0 , 1 n,要求找出一个 n元0-1向量(x1 , x2, xn), Xi W0,1,1 3Mn,使得 WiXiWiXi 苴 c ,c ,而且 ViXiViXi 到达最大。因此 0-1背包问题是一个特殊的整 i * i注 n 数规划问题： max Vj xj i A I ,二-WiXi 竺C xi 0,1, 1 i . n 算法描述： 设所给0-1背包问题的子问题 max E (Vk * Xk) k=i.n ; ma近(Vk * Xk) = j (k=i.n ) ; Xk 0 , 1, i =k = wi 0 = j = wn 0 = j w

13、n #include #define Max 101 int mMaxMax,wMax,vMax,xMax; void Knapsack(int c,int n) ( int jMax=min(wn-1,c); m(i , j) = maxm(i+1 m(i , j) = m(i+1,j) m(n,j) = Vn m(n,j) = 0 程序： 0-1背包问题的算法设计谋略比照与分析 第4页共14页 for(int j=0;j=jMax;j+)mnj=0; for(int j=wn;j1;i-) ( jMax=min(wi-1,c); for(int j=0;jjMax;j+)mij=mi+1j

14、; for(int j=wi;j=w1)m1c=max(m1c,m2c-w1+v1); void Traceback(int c,int n) ( for(int i=0;in;i+) if(mic=mi+1c)xi=0; else ( xi=1; c-=wi; xn=(mnc)?1:0; int main() ( int n,i,c; while(scanf(%d,&n)&n) ( scanf(%d,&c); for(i=1;i=n;i+)scanf(%d%d,&vi,&wi); Knapsack(c,n); Traceback(c,n); for(i

15、=1;i=n;i+)printf(%d ,xi); printf(n); return 0; 3.2贪心算法 问题描述： 假定有n个物体和一个背包，物体 i有质量wi,价值为pi ,而背包的载荷能力为 M 假设将物体i的一局部xi ( 1=i=n,0=xi=1) 装入背包中，那么有价值pi*xi 。在约束条件 (w1*x1+w2*x2+ . +wn*xn)=M 下 使目标(p1*x1+p2*x2+ . +pn*xn)到达 极大，此处 0=xi0,1=i=n. 这个问题称为背包问题( Knapsack problem )。 算法描述 首先计算每种物品单位重量的价值 Vi/Wi，然后，依贪心选择策

16、略，将尽可能多的 单位重 量价值最高 的物品装入背包。假设将这种物品全部装入背包后，背包内的物品总重量未超过 C,那么选 择单位重量价值次高的物品并尽可能多地装入背包。 依此策略一直地进行下去, 程序代码： #include struct goodinfo float p; / 物品效益 float w; / 物品重量 float X; / 物品该放的数量 int flag; / 物品编号 ; / 物品信息结构体 void Insertionsort(goodinfo goods,int n) int j,i; for(j=2;jgoodsi.p) goodsi+1=goodsi; i-; g

17、oodsi+1=goods0; / 按物品效益，重量比值做升序排列 void bag(goodinfo goods,float M,int n) float cu; int i,j; for(i=1;i=n;i+) goodsi.X=0; cu=M; / 背包剩余容量 for(i=1;icu)/ 当该物品重量大与剩余容量跳出 break; goodsi.X=1; cu=cu-goodsi.w;/ 确定背包新的剩余容量 if(i=n) goodsi.X=cu/goodsi.w;/ 该物品所要放的量 for(j=2;j=n;j+) /* 按物品编号做降序排列*/ goods0=goodsj; i=

18、j-1; while (goods0.flaggoodsi.flag) ( goodsi+1=goodsi; i-； goodsi+1=goods0; lllllllllllllllllllllllllllllllllllllllllll cout最优解为:endl; for(i=1;i=n;i+) ( cout 第i件物品要放:; coutgoodsi.Xendl; void main() ( cout|- 运用贪心法解背包问题 - |endl; cout|-power by zhanjiantao(028054115)-|endl; cout|- |endl; int j; int n;

19、float M; goodinfo *goods;ll 定义一个指针 while(j) ( coutn; goods=new struct goodinfo n+1;ll coutM; coutendl; int i; for(i=1;i=n;i+) ( goodsi.flag=i; cout 请输入第igoodsi.w; cout 请输入第igoodsi.p; goodsi.p=goodsi.plgoodsi.w;ll 得出物品的效益，重量比 coutendl; Insertionsort(goods,n); bag(goods,M,n); coutpress to run agianend

20、l; coutpress to exitj; 3.3回溯算法 问题描述： 对于0-1背包问题回溯法的一个实例， n=4, c=7 , p=9,10,7,4,w=3,5,2,1.这4个物品的单位重量价 值分别为3,2,3,5,4.以物品为单位价值的递减序装入物品。先装入物品 4,然后装入物品3和1.装入 这3个物品后，剩余的背包容量为1,只能装入0.2的物品2.由此可得到一个解为 x=1,0,2,1,1,其相 应的价值为22.尽管这不是一个可行解，但可以证明其价值是最有大的上界。因此，对于这个实例， 最优值不超过22. 算法描述：0-l背包问题是子集选取问题。一般情况下， 0-1背包问题是NP难

21、题。0-1背包问题的 解空间可用子集树表示。解 0-1背包问题的回溯法与装载问题的回溯法十分类似。在搜索解空间树 时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进 入右子树搜索。否那么将右子树剪去。设 r是当前剩余物品价值总和； cp是当前价值；bestp是当前 最优价值。当cp+r bestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依 其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一局部而装满背包。由 此得到的价值是右子树中解的上界。 程序： #include using namespace std; class

22、Knap friend int Knapsack(int p,int w,int c,int n ); public: void print() for(int m=1;m=n;m+) coutbestxm; coutendl; ; private: int Bound(int i); void Backtrack(int i); int c;/ 背包容量 int n; / 物品数 int *w;/ 物品重量数组 int *p;/ 物品价值数组 int cw;/ 当前重量 int cp;/ 当前价值 int bestp;/ 当前最优值 2006级软件方向算法设计与分析课程考查论文 第11页共1

23、4页 7 int *bestx;/ 当前最优解 int *x;/ 当前解 ； int Knap:Bound(int i) ( /计算上界 int cleft=c-cw;/ 剩余容量 int b=cp; /以物品单位重量价值递减序装入物品 while(i=n&wi=cleft) ( cleft-=wi; b+=pi; i+; /装满背包 if(in) ( if(bestpcp) ( for(int j=1;j=n;j+) bestxj=xj; bestp=cp; return; if(cw+wibestp)/ 搜索右子树 ( xi=0; Backtrack(i+1); class Obj

24、ect ( friend int Knapsack(int p,int w,int c,int n); public: 0-1背包问题的算法设计谋略比照与分析 第8页共14页 int operator=a.d); private: int ID; float d; ; int Knapsack(int p,int w,int c,int n) ( / 为 Knap:Backtrack 初始化 int W=0; int P=0; int i=1; Object *Q=new Objectn; for(i=1;i=n;i+) ( Qi-1.ID=i; Qi-1.d=1.0*pi/wi; P+=pi

25、; W+=wi; if(W=c) return P;/ 装入所有物品 /依物品单位重量排序 float f; for( i=0;in;i+) for(int j=i;jn;j+) ( if(Qi.dQj.d) ( f=Qi.d; Qi.d=Qj.d; Qj.d=f; Knap K; K.p = new intn+1; K.w = new intn+1; K.x = new intn+1; K.bestx = new intn+1; K.x0=0; K.bestx0=0; for( i=1;i=n;i+) ( K.pi=pQi-1.ID; K.wi=wQi-1.ID; K.cp=0; 2006级

26、软件方向算法设计与分析课程考查论文 第11页共14页 9 K.cw=0; K.c=c; K.n=n; K.bestp=0; /回溯搜索 K.Backtrack(1); K.print(); delete Q; delete K.w; delete K.p; return K.bestp; void main() ( int *p; int *w; int c=0; int n=0; int i=0; char k; cout0-1 背包问题- 回溯法 endl; cout by zbqplayer endl; while(k) ( cout请输入背包容量(c) : c; cout请输入物品的个

27、数(n) : n; p=new intn+1; w=new intn+1; p0=0; w0=0; cout请输入物品的价值(p) : endl; for(i=1;ipi; cout请输入物品的重量 (w) : endl; for(i=1;iwi; cout最优解为(bestx) : endl; cout最优值为(bestp) : endl; coutKnapsack(p,w,c,n)endl; couts 重新开始endl; coutq 退出k; 3.4分支限界 问题描述： 有N个物品和一个可以容纳 M重量的背包，每种物品I的重量为 WEIGHT 一个只能全放入或者 0-1背包问题的算法设计

28、谋略比照与分析 第10页共14页 不放入，求解如何放入物品， 可以使背包里的物品的总效益最大。 对物品的选取与否构成一棵解树， 左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求 的结点。 算法描述： 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优 先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满 剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行 结点，那么将它参加到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅 当右儿子

29、结点满足上界约束时才将它参加子集树和活结点优先队列。当扩展到叶节点时为问题的最 优值。 程序： #include struct good int weight; int benefit; int flag;/ 是否可以装入标记 ; int number=0;/ 物品数量 int upbound=0; int curp=0, curw=0;/ 当前效益值与重量 int maxweight=0; good *bag=NULL; void Init_good() bag=new good number; for(int i=0; inumber; i+) ( cout请输入第件i+1bagi.wei

30、ght; cout请输入第件i+1bagi.benefit; bagi.flag=0;/ 初始标志为不装入背包 coutendl; int getbound(int num, int *bound_u)/ 返回本结点的 c 限界和 u 限界 ( for(int w=curw, p=curp; numnumber & (w+bagnum.weight)=maxweight; num+) ( w=w+bagnum.weight; p=w+bagnum.benefit; *bound_u=p+bagnum.benefit; return ( p+bagnum.benefit*(maxweig

31、ht-w)/bagnum.weight); void LCbag() ( int bound_u=0, bound_c=0;/ 当前结点的 c限界和u限界 for(int i=0; iupbound )/ 遍历左子树 upbound=bound_u;/ 更改已有u限界，不更改标志 if( getbound(i, &bound_u)bound_c )/ 遍历右子树 /假设装入，判断右子树的 c限界是否大于左子树根的 c限界，是那么装入 ( upbound=bound_u;/ 更改已有 u 限界 curp=curp+bagi.benefit; curw=curw+bagi.weight;/

32、 从已有重量和效益加上新物品 bagi.flag=1;/ 标记为装入 void Display() ( cout可以放入背包的物品的编号为： ; for(int i=0; i0) couti+1; coutendl; delete bag; 4、比照分析以上四种算法策略： 贪心算法：贪心算法中，作出的每步贪心决策都无法改变， 因为贪心策略是由上一步的最优解推导 下一步的最优解，而上一部之前的最优解那么不作保存。 由前面中的介绍，可以知道贪心法正确的 条件是：每一步的最优解一定包含上一步的最优解。 动态规划算法：全局最优解中一定包含某个局部最优解， 但不一定包含前一个局部最优解， 因此需 要记录之前的所有最优解 。动态规划