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

摘要：

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

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

所属期刊栏目：47

分类号：TP18(自动化基础理论)

在线出版日期：2022-12-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：63-71