Journal of Frontiers of Computer Science and Technology ›› 2023, Vol. 17 ›› Issue (3): 595-607.DOI: 10.3778/j.issn.1673-9418.2106033

• Theory·Algorithm • Previous Articles     Next Articles

Research on Greedy Core Algorithms via Piecewise Sorting for Discounted {0-1} Knapsack Problem

DAI Zuhua, LIU Yuanyuan, DI Shilong, FAN Qi   

  1. College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China
  • Online:2023-03-01 Published:2023-03-01

折扣{0-1}背包问题之分段排序贪心核算法研究

代祖华,刘园园,狄世龙,樊琦   

  1. 西北师范大学 计算机科学与工程学院,兰州 730070

Abstract: The greedy core method of D{0-1}KP problem is an approximate solution algorithm, which usually adopts the design pattern of divide and conquer algorithm, and divides subproblems by estimated core interval. Its performance is closely related to the accuracy of core interval size. The main way to improve the algorithm is to optimize core interval estimation. On the basis of studying the concept of {0-1}KP core, a repaired definition of D{0-1}KP core interval is proposed, and a piecewise sorting strategy is constructed to reduce the size of its core interval. Thus, the greedy core method of D{0-1}KP is improved. The repaired greedy core acceleration dynamic programming algorithm (RGCADP) and the repaired greedy core acceleration dynamic programming algorithm via piecewise sorting (RGCADP_PS) are designed.  Experimental results on D{0-1}KP standard datasets show that the average solving time of RGCADP and RGCADP_PS is improved by 71.3% and 77.2% compared with the basic dynamic programming algorithm (BDP). The average solution error rate of proposed algorithms can be reduced by 0.5 percentage points and 4.7 percentage points compared?with that of the particle swarm optimization based greedy repair algorithm for D{0-1}KP (PSO-GRDKP) and the greedy core acceleration dynamic programming algorithm (GCADP). The average solving time improvement rate of  RGCADP_PS  is 5.9% higher than that of RGCADP.

Key words: discounted {0-1} knapsack problem, repaired core interval definition, greedy core algorithm, piece-wise sorting, greedy core dynamic programming acceleration algorithm

摘要: 折扣{0-1}背包问题(D{0-1}KP)的贪心核算法是一种近似解算法,常通过估算核区间划分子问题,采用分治算法设计求解算法,算法性能与核区间估计准确性密切相关,核区间估算优化是算法改进的主要途径。在研究{0-1}KP核概念基础上,提出D{0-1}KP核区间的修正定义,构建分段排序策略以缩减核区间规模,改进了D{0-1}KP贪心核算法,设计了修复贪心核动态规划加速算法(RGCADP)、分段排序贪心核动态规划加速算法(RGCADP_PS)。两个算法在D{0-1}KP标准数据集上的实验结果表明:与基本动态规划算法(BDP)相比,RGCADP、RGCADP_PS算法平均求解时间提升率为71.3%、77.2%;RGCADP、RGCADP_PS算法平均解误差率低于粒子群贪心修复算法(PSO-GRDKP)0.5个百分点,低于贪心核加速动态规划(GCADP)算法4.7个百分点;RGCADP_PS时间性能提升率高于RGCADP算法5.9%。

关键词: 折扣{0-1}背包问题, 核区间定义修正, 贪心核算法, 分段排序, 贪心核动态规划加速算法