求解0—1背包问题的两种方法的分析与比较

• 作者: 刘建芹 王英杰
• 来源期刊: 河北省科学院学报
• 关键词: 背包问题 近似算法 动态规划 算法复杂度
• 年，卷（期）: 2012,（3）
• 页码范围: 11-16
• 页数: 6页
• 分类号: TP18
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王英杰		13	19	3.0	3.0
2	刘建芹		11	205	5.0	11.0