[1]孙佳宁,马海龙,张立臣,等.求解 0-1 背包问题的融合贪心策略的回溯算法[J].计算机技术与发展,2022,32(02):190-195.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 031]
　SUN Jia-ning,MA Hai-long,ZHANG Li-chen,et al.Backtracking Algorithm of Fusion Greedy Strategy for Solving 0-1 Knapsack Problem[J].,2022,32(02):190-195.[doi:10. 3969 / j. issn. 1673-629X. 2022. 02. 031]
点击复制

求解 0-1 背包问题的融合贪心策略的回溯算法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
32
期数:
2022年02期
页码:
190-195
栏目:
应用前沿与综合
出版日期:
2022-02-10

文章信息/Info

Title:
Backtracking Algorithm of Fusion Greedy Strategy for Solving 0-1 Knapsack Problem
文章编号:
1673-629X(2022)02-0190-06
作者:
孙佳宁1; 2; 3 ; 马海龙1; 2; 3 ; 张立臣1; 2; 3 ; 李 鹏1; 2; 3*
1. 现代教学技术教育部重点实验室,陕西 西安 710062;
2. 陕西省教学信息技术工程实验室,陕西 西安 710119;
3. 陕西师范大学 计算机科学学院,陕西 西安 710119
Author(s):
SUN Jia-ning1; 2; 3 ; MA Hai-long1; 2; 3 ; ZHANG Li-chen1; 2; 3 ; LI Peng1; 2; 3*
1. Key Laboratory of Modern Teaching Technology of Ministry of Education,Xi’an 710062,China;
2. Engineering Laboratory of Teaching Information Technology of Shaanxi Province,Xi’an 710119,China;
3. School of Computer Science,Shaanxi Normal University,Xi’an 710119,China
关键词:
0-1 背包问题; 贪心算法; 回溯算法; 剪枝策略; 递归算法
Keywords:
knapsack problem; greedy algorithm; backtracking algorithm; pruning strategy; recursion algorithm
分类号:
TP301. 6
DOI:
10. 3969 / j. issn. 1673-629X. 2022. 02. 031
摘要:
0-1 背包问题作为经典的 NP 完全问题一直得到广泛的关注和研究。 研究发现,经典回溯算法在解决 0 -1 背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差。 虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可以找到问题的最优解。 针对这些问题,提出一种融合贪心策略和剪枝策略的新型回溯算法。 该算法将贪心算法得到的问题近似解用于剪枝策略的判断条件中,并在物品取舍时将当前的物品重量与背包的剩余容量进行比较,以避免重复计算,减少迭代次数,提高算法的执行效率。 大量的仿真实验结果表明,在一定问题规模下,与经典回溯算法相比,所提出的新型回溯算法仍能够在短时间内准确找到问题的最优解,且具有更高的执行效率。
Abstract:
As a classic NP-complete problem,the 0-1 knapsack problem has been receiving extensive attentions and research. It is foundthat when using the classic backtracking algorithm to solve? ? the 0-1 knapsack problem,the time complexity of the algorithm is relativelyhigh,which leads to poor applicability when the number of the problem is large,which means that the solution of? ? ?the problem cannot beobtained in a short time. Although the classic greedy algorithm and a large number of new algorithms being generated currently greatlyreduce the running time, they generally sacrifice the accuracy of the algorithm and cannot guarantee that the optimal solution to theproblem can be found. In order to solve these problems,a new backtracking algorithm combining greedy strategy and pruning strategy isproposed,in which an approximate solution of the problem obtained by the greedy algorithm is used as the judgment condition of pruningstrategy, and comparing the current weight of item with the remaining capacity of the backpack when selecting items, so as to avoidrepeated calculations,reduce the number of iterations,and improve the algorithm implementation efficiency. Extensive experiments areconducted to determine the optimal solution. The results show that,under a certain problem size,comparing with the classic backtrackingalgorithms,the proposed backtracking algorithm can accurately find the optimal solution to the problem in a shorter time, and thusachieves high execution efficiency.

相似文献/References:

[1]袁廷磊,吾守尔·斯拉木.图的最优矩阵构建研究[J].计算机技术与发展,2013,(07):151.
　YUAN Ting-lei,WUSHOUER Silamu.Research on Optimal Matrix Construction of Diagram[J].,2013,(02):151.
[2]刘瑞杰,史原,李孝贵,等.提高三峡船闸实际通过能力的贪心模拟退火算法[J].计算机技术与发展,2014,24(03):246.
　LIU Rui-jie,SHI Yuan,LI Xiao-gui,et al.Greedy Simulated Annealing Algorithm of Improving Actual Navigation Capacity of Yangtze Gorges Ship Lock[J].,2014,24(02):246.
[3]李霞[],尹川东[],袁云[]. 旅游路线个性化推荐算法比较分析[J].计算机技术与发展,2016,26(09):73.
　LI Xia[],YIN Chuan-dong[],YUAN Yun[]. Comparison and Analysis of Personalized Recommending Algorithm of Travelling Route[J].,2016,26(02):73.
[4]王建辉,郑光勇,徐雨明.混合人工化学反应优化算法求解 0-1 背包问题[J].计算机技术与发展,2020,30(07):71.[doi:10. 3969 / j. issn. 1673-629X. 2020. 07. 016]
　WANG Jian-hui,ZHENG Guang-yong,XU Yu-ming.Artificial Chemical Reaction Optimization Algorithm for 0-1 Knapsack Problem[J].,2020,30(02):71.[doi:10. 3969 / j. issn. 1673-629X. 2020. 07. 016]
[5]董　凯,赵　旭.基于马尔可夫决策过程的入侵检测方法研究[J].计算机技术与发展,2021,31(05):131.[doi:10. 3969 / j. issn. 1673-629X. 2021. 05. 023]
　.ＲｅｓｅａｒｃｈｏｎＩｎｔｒｕｓｉｏｎＤｅｔｅｃｔｉｏｎＭｅｔｈｏｄＢａｓｅｄｏｎＭａｒｋｏｖＤｅｃｉｓｉｏｎＰｒｏｃｅｓ[J].,2021,31(02):131.[doi:10. 3969 / j. issn. 1673-629X. 2021. 05. 023]
[6]聂 鑫,殷若兰,刘海峰.软硬件协同的遗传算法设计[J].计算机技术与发展,2021,31(11):114.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 019]
　NIE Xin,YIN Ruo-lan,LIU Hai-feng.Design of Genetic Algorithm Based on Software and Hardware Cooperation[J].,2021,31(02):114.[doi:10. 3969 / j. issn. 1673-629X. 2021. 11. 019]
[7]陈建荣.求解 0-1 背包问题的改进二进制捕鱼算法[J].计算机技术与发展,2023,33(05):187.[doi:10. 3969 / j. issn. 1673-629X. 2023. 05. 028]
　CHEN Jian-rong.An Improved Binary Fishing Algorithm for 0-1 Knapsack Problem[J].,2023,33(02):187.[doi:10. 3969 / j. issn. 1673-629X. 2023. 05. 028]

更新日期/Last Update: 2022-02-10