| 贪心核加速动态规划算法精确求解适用范围 |
| |
| 引用本文： | 殷亚林.贪心核加速动态规划算法精确求解适用范围[J].教育技术导刊,2009,19(8):54-59. |
| |
| 作者姓名： | 殷亚林 |
| |
| 作者单位： | 1. 西华师范大学 数学与信息学院,2. 西华师范大学 计算方法与应用研究所，四川 南充 637009 |
| |
| 基金项目： | 国家自然科学基金项目（11871059）|四川省教育厅自然科学基金项目（18ZA0469）|西华师范大学校级科研团队项目（CXTD2015-4） |
| |
| 摘 要： | 针对背包容量折扣系数在 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 随着数据规模的变大，求解时长增长平缓。
|
| 关 键 词： | 折扣｛0-1｝背包问题 贪心核加速动态规划算法 动态规划 价值密度 贪心策略 |
| 收稿时间： | 2019-11-14 |
Greedy Core Acceleration Dynamic Programming Algorithm to Accurately Solving Range |
| |
| WANG Mao-ping,PAN Da-zhi,FENG Shi-qiang,ZHANG Qin.Greedy Core Acceleration Dynamic Programming Algorithm to Accurately Solving Range[J].Introduction of Educational Technology,2009,19(8):54-59. |
| |
| Authors: | WANG Mao-ping PAN Da-zhi FENG Shi-qiang ZHANG Qin |
| |
| Institution: | 1. College of Mathematics and Information，China West Normal University| 2. Institute of Computing Method and Application Software，China West Normal University，Nanchong 637009，China |
| |
| Abstract: | The greedy core acceleration dynamic programming algorithm（GCADP）can’t find the exact solution of the instance when solving the inverse strongly correlated instances of D｛0-1｝KP（IDKP）with the knapsack capacity discounted coefficient of 0.8-0.9. In order to obtain the exact solution of the D｛0-1｝KP instance，based on the analysis of the IDKP instance parameters，the GCADP algorithm can accurately solve the D｛0-1｝KP instance with limited condition that the value coefficient of any item set satisfies the smallest value item and is greater than 0.99 times the second largest value item. This condition is applied to the parameter settings of the four types of D｛0-1｝KP instances to create a new large scale four-class D｛0-1｝KP instance. The four types of D｛0-1｝KP instances use GCADP and dynamic programming（DP）calculations. Instances calculation results show that the new four types of D｛0-1｝KP instances are all accurately solved，and the data size increases，the solve time of GCADP grows slowly. |
| |
| Keywords: | discount｛0-1｝knapsack problem greedy core acceleration dynamic programming algorithm dynamic programming value density greedy strategy |
| 本文献已被 维普 等数据库收录！ |
| 点击此处可从《教育技术导刊》浏览原始摘要信息 |
| 点击此处可从《教育技术导刊》下载免费的PDF全文 |
