求解随机时变背包问题的确定性算法

作     者：贺毅朝 张新禄 高锁刚 宋超 HE Yi-chao;ZHANG Xin-lu;GAO Suo-gang;SONG Chao

作者机构：石家庄经济学院信息工程学院石家庄050031 河北师范大学数学与信息科学学院石家庄050016 电子科技大学信息与软件工程学院成都611731 

出 版 物：《小型微型计算机系统》 (Journal of Chinese Computer Systems)

年 卷 期：2014年第35卷第4期

页      面：854-857页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(10971052)资助 石家庄经济学院预研项目(2012-05)资助 

主　　题：动态优化问题 随机时变背包问题 动态规划法 算法复杂度 

摘      要：随机时变背包问题(RTVKP)是智能计算领域中的一个动态组合优化问题,具有重要的理论与应用价值.对于背包载重随机变化的RTVKP问题(记为RTVKP3),首先利用改进的动态规划法提出了一种适于求解具有较小物品价值和较大背包载重的RTVKP3的确定性算法(记为MDP-RTVKP),给出了MDP-RTVKP可成功求解RTVKP3的必要条件;然后,基于MDPRTVKP和DPforRTVKP的不同适用性提出了一种适于求解任意RTVKP3实例的有效方法 GenericDPfRTVKP,并通过对大规模RTVKP3实例的仿真计算验证了GenericDPfRTVKP的通用性与高效性.