《算法分析课程设计(摘要+正文)(共18页)》由会员分享，可在线阅读，更多相关《算法分析课程设计(摘要+正文)(共18页)（18页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上特殊0-1背包问题摘要算法设计与分析，其实可以解释为一类优化问题，一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出各种不同的解决方案，并且要针对具体的问题做细致的空间和时间复杂度分析。所有的算法中，应该尽量选取“好”的算法，这里所说的“好”，首先是正确的，其次是所选算法解决问题的效率要尽可能的高。计算机计算时间的长短以及所用空间的大小，跟算法有直接关系，用来衡量算法好坏的两个重要标准就是就是时间和空间复杂度，所以提出好的解决方案，其算法是重中之重。针对0-1背包问题，解决方案有很多种，并且各种解决方案都有其自己的有点和缺点，其中比较重要
2、的有分支限界法、动态规划法、贪心法、回溯法、分治策略等，本论文将利用分支限界法来解决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 solv
3、e 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 b
4、y 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 spac
5、e 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-c
6、onquer 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 问
7、题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。0-1背包问题的形式化描述是，给定c0,Wi0,Vi0，1in，要求找出一个n元0-1向量（x1，x2，xn），Xi0,1,1in，使得，而且达到最大。因此0-1背包问题是一个特殊的整数规划问题：2 问题分析0-1背包问题是一类典型的离散型优化问题，问题的约束条件和要求都很简单。求解方案也比较多，本论文
8、就几种典型的求解方案做简单的分析，但是主要实现的是利用分支限界法解决的方案。下面是几种典型算法的简单分析：1.分支限界法：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法： 队列式(FIFO
9、)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。 最大优先队列：使用最大堆，体现最大效益优先 最小优先队列：使用最小堆，体现最小费用优先 2.贪心算法：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。具有最优子结构性质的问题，用贪心算法更简单、更直接且解题效率更高。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问
10、题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。3.回溯法：回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。显约束：对分量xi的取值限定。隐约束：为
11、满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。 4. 动态规划：动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。动态规划的一般步骤：找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解
12、。3 算法分析及描述0-1背包问题，问题分析中的几种解决方案是同源的，那些算法中有些算法是另一种算法的改进，比如：分支限界法可以看成是回溯法的改进，因为分支限界法是有判别的进行搜索，以期望最早获得问题的最优解，即优先在最有可能获得最优解的子树上搜索。而不像回溯法那样：对所有的可能过程进行搜索，直到找到最好的一种方案。所以下面对几种算法作简单分析和比较时，相同的地方就不再重复。3.1 分支限界法的分析与描述分支限界法的分析：已知有N个物品和一个可以容纳M重量的背包，每种物品I的重量为WEIGHT，一个只能全放入或者不放入，求解如何放入物品，可以使背包里的物品的总效益最大。对物品的选取与否构成一棵
13、解树，左子树表示不装入，右表示装入，通过检索问题的解树得出最优解，并用结点上界杀死不符合要求的结点。分支限界法的描述：首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。3.2 贪心法的分析与描述贪心法的分析： 假定
14、有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，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进
15、行下去，直到背包装满为止。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难题。0-1背包问题的解空间可用子集树表示。解0-1背包问题的回溯法与装载问题的回溯法十分类似。在搜索解空间树时，只要其左儿子结点是一个可行结点，搜索就进入其左子树。当右子树有可能包含最优解时才进入右子树搜索。否则将右子树剪去。设r是当前剩余物品价值总和；cp是当前价值；bestp是当前最优价值。当cp+rbestp时，可剪去右子树。计算右子树中解的上界的更好方法是将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。
