张玉州，陶 朗

（安庆师范大学计算机与信息学院，安徽安庆246133）

背包问题[1]（knapsack problem，KP）于20世纪50年代由Dantzing提出，作为一类经典的组合优化问题，属于NP-hard问题。该问题具有众多的变种，包括0-1背包问题[2]、有界背包问题、多背包问题、多维背包问题[3]、二次背包问题和折扣0-1背包问题[4]等。背包问题的约束条件一般都是背包的额定容量，即便是较为复杂的折扣0-1背包问题，除了需要考虑编码结构的可行性，其约束条件也同样是背包的额定容量。但在实际生活中，不仅需要考虑问题本身的约束，决策者的自身需求同样值得考虑。

目前，针对背包问题的研究算法主要有贪心算法[5]、动态规划算法、穷举法等精确算法和遗传算法[6]、蚁群算法[7]、和声搜索算法[8]、蝙蝠算法[9]、狮群算法[10]等近似算法。贪心算法局部收敛性太强，学者通常是将其与其他近似算法结合使用，以求达到提高算法收敛性能和防止陷入局部最优的目的。模拟退火算法[11]、禁忌搜索算法[12]和果蝇算法[13]等全局搜索能力较弱，对初始解的要求十分严格。因此，贪心算法通常会以算子的形式与其他近似算法结合，用来修补优化初始解以期提升算法的全局收敛性能和解的质量。文献[13]就将贪心算法作为果蝇算法的修复补偿策略，修复非法解和优化可行解，有效提升了果蝇算法的求解质量。文献[14]针对背包问题的特点在遗传算法中引入贪心算子，提升了种群中解的质量和算法的收敛性能。在一些较新的背包问题上，遗传算法同样展现出了极强的适用性，文献[15]借鉴启发式搜索思想，设计了3种交叉算子与1种变异算子，有效解决了折扣0-1背包问题的无效编码结构，保证了算法进化中解的可行性。……