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

An Exact Algorithm for Solving Random Time-varying Knapsack Problem

作　　者：贺毅朝[1] 张新禄[2] 高锁刚[2] 宋超[3] 

机构地区：[1]石家庄经济学院信息工程学院,石家庄050031 [2]河北师范大学数学与信息科学学院,石家庄050016 [3]电子科技大学信息与软件工程学院,成都611731

出　　处：《小型微型计算机系统》2014年第4期854-857,共4页Journal of Chinese Computer Systems

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

摘　　要：随机时变背包问题(RTVKP)是智能计算领域中的一个动态组合优化问题,具有重要的理论与应用价值.对于背包载重随机变化的RTVKP问题(记为RTVKP3),首先利用改进的动态规划法提出了一种适于求解具有较小物品价值和较大背包载重的RTVKP3的确定性算法(记为MDP-RTVKP),给出了MDP-RTVKP可成功求解RTVKP3的必要条件;然后,基于MDPRTVKP和DPforRTVKP的不同适用性提出了一种适于求解任意RTVKP3实例的有效方法 GenericDPfRTVKP,并通过对大规模RTVKP3实例的仿真计算验证了GenericDPfRTVKP的通用性与高效性.Random time-varying knapsack problem （ RTVKP ） is a dynamic combinatorial optimization problem in intelligent computa- don, which has important values in theory and applications. First, a new determined algorithm （ MDP-RTVKP ） for RTVKIr3 is pro- posed based on modified method of dynamic programming, where RTVKP3 is the special case of RTVKP with random changed weights. MDP-RTVKP fit RTVKIr3 with less value of items and bigger weight of kanpsack. Analyzed the necessary conditions in which the algorithm can successfully solve instances of RTVKP3. Next, a general approach GenericDPfRTVKP for RTVKP3 is pro- posed, which combined MDP-RTVKP with DPforRTVKP and fit any instances of RTVKP3. The efficiency and feasibility of Ge- nericDPfRTVKP be identified bv simulation comtmtation results.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]