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

• 作者: 张新禄 王志威 田海燕 贺毅朝 高锁刚
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: NP-难问题 0-1背包问题 动态优化 时变背包问题 动态规划法
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 人工智能
• 页码范围: 237-241
• 分类号: TP18
• 字数: 5285字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2012.07.054

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贺毅朝	石家庄经济学院信息工程学院	53	677	14.0	25.0
2	田海燕	河北师范大学数学与信息科学学院	5	31	2.0	5.0
4	高锁刚	河北师范大学数学与信息科学学院	12	48	2.0	6.0
5	张新禄	河北师范大学数学与信息科学学院	14	108	5.0	10.0
8	王志威	河北师范大学数学与信息科学学院	1	25	1.0	1.0