首页|求解0-1背包问题的融合贪心策略的回溯算法

求解0-1背包问题的融合贪心策略的回溯算法

扫码查看
原文链接
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 万方数据
  • 维普
0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究.研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差.虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可以找到问题的最优解.针对这些问题,提出一种融合贪心策略和剪枝策略的新型回溯算法.该算法将贪心算法得到的问题近似解用于剪枝策略的判断条件中,并在物品取舍时将当前的物品重量与背包的剩余容量进行比较,以避免重复计算,减少迭代次数,提高算法的执行效率.大量的仿真实验结果表明,在一定问题规模下,与经典回溯算法相比,所提出的新型回溯算法仍能够在短时间内准确找到问题的最优解,且具有更高的执行效率.
Backtracking Algorithm of Fusion Greedy Strategy for Solving 0-1 Knapsack Problem

孙佳宁、马海龙、张立臣、李鹏

展开 >

现代教学技术教育部重点实验室,陕西 西安 710062

陕西省教学信息技术工程实验室,陕西 西安 710119

陕西师范大学 计算机科学学院,陕西 西安 710119

0-1背包问题 贪心算法 回溯算法 剪枝策略 递归算法

国家自然科学基金教育部第二批新工科研究与实践项目陕西师范大学基础教育课程研究中心项目陕西师范大学金课(算法设计与分析)建设项目(2019)

61877037E-RGZN202010452019-JCJY009

2022

10.3969/j.issn.1673-629X.2022.02.031

计算机技术与发展
陕西省计算机学会

计算机技术与发展

CSTPCD
影响因子：0.621
ISSN：1673-629X
年,卷(期)：2022.32(2)
  • 3
  • 7