摘要
0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究.研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差.虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可以找到问题的最优解.针对这些问题,提出一种融合贪心策略和剪枝策略的新型回溯算法.该算法将贪心算法得到的问题近似解用于剪枝策略的判断条件中,并在物品取舍时将当前的物品重量与背包的剩余容量进行比较,以避免重复计算,减少迭代次数,提高算法的执行效率.大量的仿真实验结果表明,在一定问题规模下,与经典回溯算法相比,所提出的新型回溯算法仍能够在短时间内准确找到问题的最优解,且具有更高的执行效率.
基金项目
国家自然科学基金(61877037)
教育部第二批新工科研究与实践项目(E-RGZN20201045)
陕西师范大学基础教育课程研究中心项目(2019-JCJY009)
陕西师范大学金课(算法设计与分析)建设项目(2019)()
国家科技期刊平台
NSTL
维普
万方数据