基于动态规划法求解动态0-1背包问题

摘要：

随机时变背包问题(RTVKP)是一种动态组合优化问题,也是一种典型的NP-hard问题.由于RTVKP问题中物品的价值、重量和背包载重均是动态变化的,导致问题的求解非常困难.在动态规划法基础上,提出了一种求解背包载重随机变化的RTVKP问题的确定性算法,分析了其复杂度和成功求解需要满足的条件.对两个大规模实例的计算表明,该算法是求解RTVKP问题的一种高效算法.

关键词：NP-难问题、0-1背包问题、动态优化、时变背包问题、动态规划法

所属期刊栏目：39

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金10971052;河北省高等学校科学技术研究青年基金2010260

在线出版日期：2012-12-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：237-241