启发式算法求解背包问题研究  

作　　者：黄林峰[1] 

机构地区：[1]淄博职业学院信息工程系,山东淄博255314

出　　处：《科技经济市场》2016年第11期155-156,共2页

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

关 键 词：背包问题 启发式算法 贪心法 动态规划 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]