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