改进贪心算法求解扩展简化折扣{0-1}背包问题

作者：林洪; 邓艳

来源：西南师范大学学报(自然科学版), 2022, 47(11): 63-71.

DOI：10.13718/j.cnki.xsxb.2022.11.009

• 贪心算法
• 扩展折扣{0-1}背包问题(ESD{0-1}KP)
• 改进帕累托算法(IPA)
• 价值密度
• 多选择背包问题(MCKP)

扩展简化折扣{0-1}背包问题(ESD{0-1}KP)是折扣{0-1}背包问题(D{0-1}KP)的拓展.ESD{0-1}KP增加了D{0-1}KP中单个项集中的物品数量，导致其求解难度增加，并且现有贪心策略算子(GSOR)算法效果不理想.基于ESD{0-1}KP模型，在每个项集中增加一个价值为0,质量为0的虚拟物品，同时对ESD{0-1}KP模型中的约束进行松弛，从理论上证明了ESD{0-1}KP与多选择背包问题(MCKP)等价.结合改进帕累托算法(IPA),提出新的贪心策略算子(NGSOR).NGSOR首先将同一项集多个物品的选择情况通过在项集内增加物品来表示，按从价值密度从高到低顺序选择物品，若被选择物品的价值比物品所在项集已选择物品的价值更大，则对该项集进行迭代.仿真实验结果表明：NGSOR相比于GSOR,求解精度平均提升24.56%,求解速度平均提升44.95%.

• 单位
  中国人民武装警察部队警官学院