[书籍资源] 贪心核加速动态规划算法精确求解适用范围

[复制链接]

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-10-14 16:18 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

针对背包容量折扣系数在 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 随着数据规模的变大，求解时长增长平缓。