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

被引：15

作者：

贺毅朝 ^{[1
]}

田海燕 ^{[2
,3
]}

张新禄 ^{[2
]}

王志威 ^{[2
]}

高锁刚 ^{[2
]}

机构：

[1] 石家庄经济学院信息工程学院

[2] 河北师范大学数学与信息科学学院

[3] 计算数学与应用河北省重点实验室

来源：

计算机科学 | 2012年 / 39卷 / 07期

关键词：

NP-难问题; 0-1背包问题; 动态优化; 时变背包问题; 动态规划法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论]; O224 [最优化的数学理论];

学科分类号：

摘要：

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

引用

页码：237 / 241

页数：5