CAJ | 학술논문

背包问题（KP）是计算机科学中典型的NP—hard问题，不存在多项式时间的精确算法。本文首先给出了求解0—1KP问题的一种改进的近似算法，讨论了算法复杂度与近似比；然后，给出了求解0—1KP的动态规划算法描述，并分析了算法的复杂度；最后，对两种方法进行了理论分析，并利用3个较大规模0—1KP实例的仿真计算结果与GDPSO进行比较。
배포문제（KP）시계산궤과학중전형적NP—hard문제，불존재다항식시간적정학산법。본문수선급출료구해0—1KP문제적일충개진적근사산법，토론료산법복잡도여근사비；연후，급출료구해0—1KP적동태규화산법묘술，병분석료산법적복잡도；최후，대량충방법진행료이론분석，병이용3개교대규모0—1KP실례적방진계산결과여GDPSO진행비교。
Knapsack problem(KP) is a typical NP-hard problem in computer science,which has no polyno- mial time algorithms for solving it. Firstly, it presents improved 2-approximation algorithm for 0-1KP, discusses its complexity and approximation rates, and then describes dynamic programming method and its complexity analysis. Finally, it carries the theoretical analysis on the two methods, and compares the sim- ulation results by three large-scale demonstrations of 0-1KP with GDPSO.