1. 课题研究目的及意义

背包问题（knapsack problem）[1-3]是运筹学中的一个典型的NP优化问题，在现代理科学中有着重要的应用，在实际生活中也有着广泛的应用背景。许多关于工业，经济，金融与计算机领域的问题都可以建立与之相对应的背包问题的数学模型（如：货物装载，线性材料切割，资源分配，投资决策等），解决该问题就可以的到优化的结果，从而提高决策的经济性。因此，研究背包问题无论是在理论上还是在实际生活中都有着极其重大的意义。在注重经济性的当今社会，背包问题的影响愈来愈大，应用愈来愈频繁，是现代数学问题不可忽视的一部分。

动态规划（DP）[4,5]是运筹学的一个分支，是一种重要的算法设计方法,适于求解具有最优子结构性质的最优化问题。自问世以来，其在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。

在利用DP求解问题时,刻画子问题的最优解的结构特征,并依此建立问题与子问题最优值之间的递推公式是算法设计的关键所在;一旦建立了递推公式,就可以根据它按照自底向上的方式逐一求解各子问题的最优值,最终求得原问题的最优值(这一过程通常利用填表实现);然后,根据求得的最优值和递推公式,按照自顶向下的方式逐步确定问题的一个最优解。

2.国内外研究现[6]

求解KP的算法一般分为两类：一类是精确算法[7-10]，如动态规划、回溯法和分支限界法等。另一类是非精确算法，主要有随机算法、近似算法、生物算法和 演化算法(EAs)等。目前，人们模仿自然界中生物的群体行为，或者受社会 实践中某些社会活动的启发，提出了许多有效的EAs，如遗传算法(genetic algorithm，简称 GA)[11]、粒子群优化(particle swarm optimization，简称 PSO)[12,13]等，并已被成功用于求解。、

Dantzig在二十世纪五十年代中期提出背包问题后，首先进行了开创性研究，利用贪婪算法的到了一个理想解，得出了0/1背包问题的最优解的上界。

1974年，Horowitz和Sahni利用分冶方法设计出了求解背包问题著名的二表 算法，并且提出了背包问题的可分性，指明了求解该问题的另外一条新的途径。