精选优质文档-倾情为你奉上特殊0-1背包问题摘要算法设计与分析,其实可以解释为一类优化问题,一般针对可以利用计算机解决的离散型问题的优化。主要目的就是为了解决某一问题而提出各种不同的解决方案,并且要针对具体的问题做细致的空间和时间复杂度分析。所有的算法中,应该尽量选取“好”的算法,这里所说的“好”,首先是正确的,其次是所选算法解决问题的效率要尽可能的高。计算机计算时间的长短以及所用空间的大小,跟算法有直接关系,用来衡量算法好坏的两个重要标准就是就是时间和空间复杂度,所以提出好的解决方案,其算法是重中之重。针对0-1背包问题,解决方案有很多种,并且各种解决方案都有其自己的有点和缺点,其中比较重要的有分支限界法、动态规划法、贪心法、回溯法、分治策略等,本论文将利用分支限界法来解决0-1背包问题,并分析该算法的时间和空间复杂度,以及与另外一些算法的简单比较。关键字:计算机;分支限界法;0-1背包问题;复杂度分析SPECIAL 0-1 KNAPSACK PROBLEMABSTRACT