贪心核加速动态规划算法精确求解适用范围

• 作者: 冯世强 张琴 潘大志 王茂萍
• 来源期刊: 软件导刊
• 学科: 工学
• 关键词: 折扣{0-1}背包问题 贪心核加速动态规划算法 动态规划 价值密度 贪心策略
• 年，卷（期）: 2020,（8）
• 所属期刊栏目: 计算机软件与理论
• 页码范围: 54-59
• 页数: 6页
• 分类号: TP312
• 字数: 4466字
• 语种: 中文
• DOI: 10.11907/rjdk.192600

摘要

针对背包容量折扣系数在 0.8～0.9时,贪心核加速动态规划算法(GCADP)无法求得逆向强相关折扣{0-1}背包问题实例(IDKP)精确解的问题,为求得 D{0-1}KP实例的精确解,在对 IDKP实例参数进行分析的基础上,给出GCADP算法能精确求解D{0-1}KP实例的限定条件:任意项集的价值系数满足价值最小项大于价值次大项的 0.99倍.将该条件应用到 4类 D{0-1}KP实例的参数设置中,生成新的大规模 D{0-1}KP实例.对4类D{0-1}KP实例运用GCADP和动态规划(DP)进行计算,计算结果表明,新的4类D{0-1}KP实例均得到精确解,并且GCADP随着数据规模的变大,求解时长增长平缓.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘大志	西华师范大学数学与信息学院	50	194	9.0	11.0
5	冯世强	西华师范大学数学与信息学院	33	29	3.0	3.0
6	张琴	西华师范大学数学与信息学院	5	0	0.0	0.0
7	王茂萍	西华师范大学数学与信息学院	1	0	0.0	0.0