基于贪心回溯的求解完全0-1背包问题局部动态规划算法  

Greedy backtracking based local dynamic programming for complete 0-1 knapsack problem

作　　者：何琨[1] 任硕 郭子杰 裘天宝 HE Kun;REN Shuo;GUO Zijie;QIU Tianbao(School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China)

机构地区：[1]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《华中科技大学学报（自然科学版）》2024年第2期16-21,共6页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：微软亚洲联合研究基金资助项目(100338928).

摘　　要：对于具有NP难度的完全0-1背包问题,提出了一种基于贪心与回溯思想的局部动态规划算法.该算法借鉴贪心与回溯技术快速找到近似最优解,再通过局部动态规划的结果回溯逼近最优解,兼顾了算法的正确性与时间复杂度.相比于传统动态规划算法,该算法在大多数情况下能够显著缩短求解时间;相较于智能算法,该算法能够保证所求解是最优解.实验结果表明:所提出的算法在绝大多数情形下均能够在更短时间内准确找到问题的最优解,并且该算法贪心地进行最大单位平均价值成分的选取,背包容量不再直接影响求解时间,因此对于背包容量极大的情况,该算法能够极大地缩短求解时间.A local dynamic programming algorithm was proposed based on the greedy and backtracking method for the NP-hard problem of complete 0-1 knapsack.The greedy and backtracking techniques were utilized to quickly find an approximate optimal solution and then the optimal solution was approached through the result of local dynamic programming,balancing the correctness and time complexity of the algorithm.Compared with traditional dynamic programming algorithms,the solution time in most cases was significantly reduced,while compared with intelligent algorithms,it can guarantee the optimal solution.Numerous experimental results show that the proposed algorithm can accurately find the optimal solution in a shorter time in most cases compared to classical dynamic programming algorithms,and the knapsack capacity does not directly affect the solution time.For cases where the knapsack capacity is extremely large,this algorithm can greatly reduce the solution time.

关 键 词：完全0-1背包问题 NP难度 动态规划 贪心 回溯 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]