算法分析与设计终期论文.doc

0/1背包问题的算法分析研究 摘要0/1背包为题是一个典型的NP问题关于这个问题有多种不同的解法这里主要总结了分治动态规划贪心和回溯算法的设计思想以及分别用他们解决0/1背包问题的时间和空间复杂度分析比较总结这四种方法实现的优缺点我们发现用贪心算法解0/1背包问题只能得到近似最优解而不能得到真正的最优解且在不同的约束条件下四种算法各有优劣 关键字0/1背包问题分治法动态规划法贪心算法回溯算法 0/