刘建芹，王英杰

（石家庄信息工程职业学院，河北 石家庄 050035）

1 引言

背包问题（knapsack problem，KP）是计算机科学中典型的NP－hard问题，最早由Dantzing［1］于20世纪50年代首先提出并研究。KP问题具有很高的理论与应用价值，在投资决策、预算控制、项目选择、资源分配和货物装载等方面有着非常重要的应用。由于KP问题的NP－hard性，使得该问题的求解比较困难，常见求解算法有两类：即确定性算法和非确定性算法。例如动态规划法和分支限界法［2，3］是求解KP问题的两种确定性算法，而求解 KP的模拟退火算法［4］、遗传算法［5］、蚁群算法［6］、粒子群算法［7］等进化算法通常被认为是非确定性算法。目前，利用进化算法求解KP问题的研究成果丰富，对利用各种进化算法求解KP问题的比较研究也非常多，因此本文主要研究动态规划法和基于贪心策略的近似算法求解KP问题，比较它们在求解速度与求解质量方面的优劣。

在第2节中，给出0－1KP问题的数学模型，并介绍了一种可快速求解的2－近似算法；在第3节给出了利用动态规划法求解KP问题的完整算法描述，讨论了其复杂度；随后，通过仿真计算和复杂度分析对两种方法进行了比较，并利用3个较大规模实例与文献［7］中的GDPSO进行比较。最后，总结全文并展望下一步的工作。

2 0－1KP问题及其近似算法

背包问题的数学描述［1，5］为：设n个物品的价值集为C＝ ｛c1，c2，…，cn｝，重量集为W＝ ｛w1，w2，…，wn｝，ci，wi∈Z＋，1≤i≤n，Z＋为正整数集；又设背包载重为M∈Z＋，满足条件n）。求解向量X＝ （x1，x2，…，xn）∈ ｛0，1｝n，使得

其中，当xi＝1时表示第i个物品装入背包；当xi＝0时表示第i个物品不装入背包。一般地，称背包问题中物品数n为问题的规模。……