| 求解0-1背包问题的两种方法的分析与比较 |
| |
| 引用本文： | 刘建芹,王英杰.求解0-1背包问题的两种方法的分析与比较[J].河北省科学院学报,2012,29(3):11-16. |
| |
| 作者姓名： | 刘建芹 王英杰 |
| |
| 作者单位： | 石家庄信息工程职业学院,河北石家庄,050035 |
| |
| 基金项目： | 河北省高等学校科学技术研究项目 |
| |
| 摘 要： | 背包问题(KP)是计算机科学中典型的NP-hard问题,不存在多项式时间的精确算法。本文首先给出了求解0-1KP问题的一种改进的近似算法,讨论了算法复杂度与近似比;然后,给出了求解0-1KP的动态规划算法描述,并分析了算法的复杂度;最后,对两种方法进行了理论分析,并利用3个较大规模0-1KP实例的仿真计算结果与GDPSO进行比较。
|
| 关 键 词： | 背包问题 近似算法 动态规划 算法复杂度 |
Analyzing and comparing of two methods for solving 0-1 knapsack problem |
| |
| LIU Jian-qin,WANG Ying-jie.Analyzing and comparing of two methods for solving 0-1 knapsack problem[J].Journal of The Hebei Academy of Sciences,2012,29(3):11-16. |
| |
| Authors: | LIU Jian-qin WANG Ying-jie |
| |
| Affiliation: | (Shijiazhuang Information Engineering Vocational College,Shijiazhuang Hebei 050035,China) |
| |
| Abstract: | |
| |
| Keywords: | Knapsack problem Approximation algorithm Dynamic programming Algorithm complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
