论文部分内容阅读
背包问题自提出以来引起学者广泛研究，积累了许多优秀求解算法。精确求解算法主要有动态规划法，分枝限界法。这些算法能精确得到问题的解。但是由于这类算法的时间复杂度通常都是问题规模的指数级，因此当问题的规模变大时，这些算法花费的时间让人无法忍受。针对这种现象，研究者提出了启发式的方法。求解背包问题的启发式算法非常多，本文主要介绍两种典型的确定性启发算法来求解背包问题。