论文部分内容阅读
背包问题（KP）是计算机科学中典型的NP—hard问题，不存在多项式时间的精确算法。本文首先给出了求解0—1KP问题的一种改进的近似算法，讨论了算法复杂度与近似比；然后，给出了求解0—1KP的动态规划算法描述，并分析了算法的复杂度；最后，对两种方法进行了理论分析，并利用3个较大规模0—1KP实例的仿真计算结果与GDPSO进行比较。