算法分析课程设计

特殊 0-1 背包问题摘要算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机 解决的离散型问题的优化。主要目的就是为了解决某一问题而提出各种不同的解 决方案，并且要针对具体的问题做细致的空间和时间复杂度分析。所有的算法中， 应该尽量选取“好”的算法，这里所说的“好”，首先是正确的，其次是所选算 法解决问题的效率要尽可能的高。计算机计算时间的长短以及所用空间的大小， 跟算法有直接关系，用来衡量算法好坏的两个重要标准就是就是时间和空间复杂 度，所以提出好的解决方案，其算法是重中之重。针对0-1 背包问题，解决方案 有很多种，并且各种解决方案都有其自己的有点和缺点，其中比较重要的有分支 限界法、动态规划法、贪心法、回溯法、分治策略等，本论文将利用分支限界法 来解决0-1 背包问题，并分析该算法的时间和空间复杂度，以及与另外一些算法 的简单比较。关键字： 计算机；分支限界法；0-1 背包问题；复杂度分析SPECIAL 0-1 KNAPSACK PROBLEMABSTRACTAlgorithm Design and Analysis, in fact, can be interpreted as a kind of optimization problem, the general optimization that can utilize the computer to solve discrete problems. The main purpose is to put forward a variety of different solutions in order to solve a problem, and to address specific issues detailed space and time complexity analysis. All algorithms, should try to select a good algorithm, used herein, Good, the first is correct, followed by the efficiency of the selected algorithm to solve the problem is to be as high as possible. Computer to calculate the length of time and the size of the space used has a direct relationship with the algorithm, two important criteria used to measure the algorithm is good or bad is the time and space complexity, solutions proposed so good, and the algorithm is the most important . 0-1 knapsack problem, the solutions are many and various solutions have their own advantages and disadvantages, which is more important branch and bound, dynamic programming, greedy method, backtracking, divide-and-conquer strategy In this paper, using the branch and bound method to solve the 0-1 knapsack problem, and analyze the time and space complexity of the algorithm, as well as a simple comparison with the other algorithms.Key words: computer; branch and bound; 0-1 knapsack problem; complexity analysis1 问题描述给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包容量为c。 问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装 入背包的物品时,对每种物品 i 只有两种选择,即装入背包或不装入背包。不能 将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背 包问题。0-1背包问题的形式化描述是，给定c0,Wi0,Vi0, 1 i n，要求找出一个n元0-1 向量(xl, x2, xn)，Xie 0,1,1 in，使得 YWiXi c，而且工ViXi 达到最大。i=1i=1因此0-1背包问题是一个特殊的整数规划问题：max Y vxii iTY wx C i ix eO,1,1 i ni2 问题分析0-1 背包问题是一类典型的离散型优化问题，问题的约束条件和要求都很简 单。求解方案也比较多，本论文就几种典型的求解方案做简单的分析，但是主要 实现的是利用分支限界法解决的方案。下面是几种典型算法的简单分析：1. 分支限界法：分支限界法常以广度优先或以最小耗费（最大效益）优先的 方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩 展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子 结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入 活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展 过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 从活结点表 中选择下一扩展结点的不同方式导致不同的分支限界法：队列式（FIFO）分支限界法：按照队列先进先出（FIFO）原则选取下一个节点 为扩展节点。优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节 点成为当前扩展节点。最大优先队列：使用最大堆，体现最大效益优先最小优先队列：使用最小堆，体现最小费用优先2. 贪心算法：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是 说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优 选择。具有最优子结构性质的问题，用贪心算法更简单、更直接且解题效率更高。 当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有 问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问 题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其 最终结果却是最优解的很好近似。3. 回溯法：回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免 不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。 算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定 不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进 入该子树，继续按深度优先策略搜索。问题的解向量：回溯法希望一个问题的解能够表示成一个 n 元式(xl,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构 成了该实例的一个解空间。4. 动态规划：动态规划算法与分治法类似，其基本思想也是将待求解 问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同 子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算 了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答 案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划的一般步骤：找出最优解的性质，并刻划其结构特征。 递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。3 算法分析及描述0-1 背包问题，问题分析中的几种解决方案是同源的，那些算法中有些算法 是另一种算法的改进，比如：分支限界法可以看成是回溯法的改进，因为分支限 界法是有判别的进行搜索，以期望最早获得问题的最优解，即优先在最有可能获 得最优解的子树上搜索。而不像回溯法那样：对所有的可能过程进行搜索，直到 找到最好的一种方案。所以下面对几种算法作简单分析和比较时，相同的地方就 不再重复。3.1 分支限界法的分析与描述分支限界法的分析：已知有 N 个物品和一个可以容纳 M 重量的背包，每种物 品I的重量为WEIGHT, 一个只能全放入或者不放入，求解如何放入物品，可以 使背包里的物品的总效益最大。对物品的选取与否构成一棵解树，左子树表示不 装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合 要求的结点。分支限界法的描述：首先，要对输入数据进行预处理，将各物品依其单位重 量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级 由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值 和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可 行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点 一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优 先队列。当扩展到叶节点时为问题的最优值。3.2 贪心法的分析与描述贪心法的分析：假定有n个物体和一个背包，物体i有质量wi,价值为 pi,而背包的载荷能力为M。若将物体i的一部分xi (l=i=n,O=xi= 1)装入 背包中，则有价值pi*xi。在约束条件(w1*x1+w2*x2+wn*xn)=M下使目标(pl*xl+p2*x2+pn*xn)达到极大，此处 0二xiO,l二i二n.这个问题称为背包问题(Knapsack problem )。贪心法算法描述首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心 选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部 装入背包后，背包内的物品总重量未超过C,则选择单位重量价值次高的物品并 尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。3.3 回溯法的分析与描述回溯法的 分析：对于 0-l 背包问题回 溯法的一 个实例， n=4， c=7， p=9,l0,7,4,w=3,5,2,l. 这 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 难题。 0-1 背包问题的解空间可用子集树表示。解 0-1 背包问题的回溯 法与装载问题的回溯法十分类似。在搜索解空间树时，只要其左儿子结点是一个 可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜 索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp 是当前最优价值。当cp+rWbestp时，可剪去右子树。计算右子树中解的上界的 更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下 时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。3.4 动态规划法的分析与描述动态规划算法描述：设所给0-1背包问题的子问题 max工(Vk * Xk)k=i.n ；max工(Vk * Xk)二 j (k=i.n )；Xk w 0, 1， i 二k 二n；的最优值为m (i, j)是背包容量为j,可选择物品为i, i+1,n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，我们可以建立计算m(i,j)的递归式如下：m(i ， j) = maxm(i+1 ， j) ， m(i+1 ， j-wi)+ Vij = wim(i， j) = m(i+1,j)0 = j = wnm(n,j) = 00 = j wn4 分支限界法的 C 语言描述在程序中，队列的初始值为100，如果在进行分支限界算法的过程中用到的队列的最大 长度超过 100，那么所得到的结果很可能不是最优解，所以当运行结算结果界面出现“队满， 请修改对流初始大小！”时，必须修改队列的初始最大值，重新运行程序才能得到正确的最 优解。附录的代码里面重要部分由注释，下面简单介绍程序设计的几个关键部分。程序实现中用到的结构体及数据结构：分支限界法中所用队列的结点类型结构体定义：typedef struct QNodefloat weight;float value;int ceng;struct QNode *parent;bool leftChild;QNode,*qnode;队列类型的定义：typedef structqnode QMaxSize;int front,rear;SqQueue;队列的初始化函数：void InitQueue(SqQueue &sq ) /队列初始化sq.front=1;sq.rear=1;队列判空函数：bool QueueEmpty(SqQueue sq) /队列判空if(sq.front=sq.rear)return false;入队函数：void EnQueue(SqQueue & sq,qnode b)结点入队函数 if(sq.front=(sq.rear+1)%MaxSize)coutvv队满，请修改队列初始大小!vvendl;exit(1);/队满出错，不再继续计算return ;sq.Qsq.rear=b;sq.rear=(sq.rear+1)%MaxSize;入队函数设计中需要特别注意的是当队满时，就立即停止运行，不再耗费计算机资源。出对函数：qnode DeQueue(SqQueue & sq) 出队qnode e;if(sq.front=sq.rear)return 0;e=sq.Qsq.front; sq.front=(sq.front+1)%MaxSize; return e;其余部分详细代码见附录。5 测试数据及运行结果，按提示输入相应X在 windows XP SP3 系统， vc+6.0 的环境下，运行程序 的数据得到如下的结果：吐选定C:DOCU1ENTS AKD SETT INGSAD1IMI.-4 S7845S 89 384 4 9 83 5 357 9 2 5最优价值为：224分立限界法求解背包问题 的总数：5容量：50曲价值与对应重量：720品包品4物尹遍3入入入12 3 1 品品品品品 请请请物物物物物.竜里量量星 S-一1一3一3一1 1345 优品品品品 最物物物物6 分支限界法的优缺点与改进6.1 分支限界法的优缺点分支限界法优点：分支限界法本身可以看成是回溯法的一种改进，所以其效 率无疑要比回溯法的高，计算时间要短。分支限界法的搜索策略是，在扩展结点 处，先生成其所有的儿子结点，然后在从当前的活结点表中选择下一个扩展结点。 在每一个活结点处，计算一个函数值（限界）,并根据函数值，从当前活结点表 中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上的最优解的分支推 进，以尽快找出一个最优解。对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能 用动态规划算法求解的问题也能用贪心算法求解?下面研究 2个经典的组合优化 问题，并以此说明贪心算法与动态规划算法的主要差别。分支限界法与回溯法的不同（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解， 而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件 的解中找出在某种意义下的最优解。（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限 界法则以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法缺点：分支限界法的空间复杂度为O（2n），其中n为所求解问题 的规模。即分支限界法所用的计算机内存空间是2n规模的空间，对于所装载物 品数量较大时，需要为队列分配的内存空间非常大，这是分支限界法的一大缺点。6.2 分支限界法的改进与其他几种算法相比之下，分支限界法已经是一个很好的算法，效率高，速 度快，特别是比回溯法好了不少。但是分支限界法仍然有课改进的地方。1）分支限界法中的队列采用先进先出的算法（FIFO），算法将分支限界法特殊0-1背包问题 的活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点成为当前 扩展结点，这种情况下算法将会对更多的结点进行计算，浪费了时间。2）在分支限界法中，队列采用优先队列，及将队列式分支限界法中活结点 组织成一个优先队列，并按优先队列的原则选取优先级最高的下一个活结点作为 当前的扩展结点。参考文献1 王晓东.算法设计与分析（第 2版）.北京：清华大学出版社，20082 孟爱国.C语言程序设计上海：复旦大学出版社,2010.023 严蔚敏，吴伟民.数据结构（C语言版）.北京：清华大学出版社，20074 陈嫒. 数据结构学习指导 实验指导 课程设计. 北京：机械工业出版社2008.01附录 源程序清单#include #include #include #define MaxSize 100typedef struct QNodefloat weight;float value;int ceng;struct QNode *parent; bool leftChild;QNode,*qnode;typedef structqnode QMaxSize;int front,rear;SqQueue;SqQueue sq;float bestv=0;int n=0;float wMaxSize;float vMaxSize;int bestxMaxSize; qnode bestE;/初始化队列长度为100/定义队列类型/定义队列/最优解/实际物品数/物品的重量/物品的价值/ 存放最优解void InitQueue(SqQueue &sq ) /队列初始化 sq.front=1;sq.rear=1; bool QueueEmpty(SqQueue sq) /队列判空 if(sq.front=sq.rear)return true;elsereturn false;void EnQueue(SqQueue & sq,qnode b) 结点入队函数 if(sq.front=(sq.rear+1)%MaxSize)coutvv队满，请修改队列初始大小!vvendl;exit(1);/队满出错，不再继续计算return ;sq.Qsq.rear=b; sq.rear=(sq.rear+1)%MaxSize;qnode DeQueue(SqQueue & sq) 出队qnode e; if(sq.front=sq.rear)return 0; e=sq.Qsq.front; sq.front=(sq.front+1)%MaxSize; return e;void EnQueue1(float wt,float vt, int i ,QNode *parent, bool leftchild)qnode b;if (i=n)/可行叶子结点if (vt=bestv)bestE=parent;bestxn=(leftchild)?1:0;return;b=(qnode)malloc(sizeof(QNode); /非叶子结点b-weight=wt; b-value=vt; b-ceng=i; b-parent=parent; b-leftChild=leftchild; EnQueue(sq,b);void maxLoading(float w,float v,int c) float wt=0; float vt=0;int i=1;/当前的扩展结点所在的层float ew=0;/扩展节点所相应的当前载重量float ev=0;/扩展结点所相应的价值qnode e=NULL; qnode t=NULL; InitQueue(sq);EnQueue(sq,t);/空标志进队列while (!QueueEmpty(sq)wt=ew+wi; vt=ev+vi; if (wt bestv) bestv=vt;EnQueue1(wt,vt,i,e,true); / 左儿子结点进队列/ 取下一扩展结点EnQueue1(ew,ev,i,e,false);/右儿子总是可行；e=DeQueue(sq); if (e = NULL) if (QueueEmpty(sq)break;EnQueue(sq,NULL);/ 同层结点尾部标志e=DeQueue(sq);/ 取下一扩展结点i+;ew=e-weight;/更新当前扩展结点的值ev=e-value;cout 最优价值为 ：bestvendl0;j-)/构造最优解 bestxj=(bestE-leftChild?1:0); bestE=bestE-parent;for(int k=1;kv=n;k+) if(bestxk=1)coutvv物品vvkvv:重量：vvwkvv 价值：vvvkvvendl;coutvvendl;void main()int c;float ewvMaxSize;coutvv- 分支限界法求解0-1背包问题vvendl;coutvv请输入物品的总数：；cinn;coutvv请输入背包容量：；cinc;coutvv请输入物品的价值与对应重量： vvendl;for(int i=1;iv=n;+i)coutewviwi; vi=ewvi;coutendl; maxLoading(w, v, c);