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

来源：计算机技术与发展杂志2022年第02期北京时间：

作者：孙佳宁;';马海龙;';张立臣;';李鹏;'*

单位：1. 现代教学技术教育部重点实验室,陕西 西安 710062;2. 陕西省教学信息技术工程实验室,陕西 西安 710119;3. 陕西师范大学 计算机科学学院,陕西 西安 710119

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

关键词：0-1 背包问题;贪心算法;回溯算法;剪枝策略;递归算法