华中科技大学学报（自然科学版）2024，Vol.52Issue(2)：16-21,6.DOI:10.13245/j.hust.240201
基于贪心回溯的求解完全0-1背包问题局部动态规划算法
Greedy backtracking based local dynamic programming for complete 0-1 knapsack problem
摘要
Abstract
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难度/动态规划/贪心/回溯Key words
complete 0-1 knapsack problem/NP-hard/dynamic programming/greedy/backtracking分类
信息技术与安全科学引用本文复制引用
何琨,任硕,郭子杰,裘天宝..基于贪心回溯的求解完全0-1背包问题局部动态规划算法[J].华中科技大学学报（自然科学版）,2024,52(2):16-21,6.基金项目
微软亚洲联合研究基金资助项目(100338928). （100338928）
