算法分析课程设计(摘要+正文)19页.docx

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