典型文献
改进贪心算法求解扩展简化折扣{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)
中图分类号：
作者姓名：
林洪;邓艳
作者机构：
中国人民武装警察部队警官学院基础部,成都610213
文献出处：
引用格式：
[1]林洪;邓艳-.改进贪心算法求解扩展简化折扣{0-1}背包问题)[J].西南师范大学学报（自然科学版）,2022(11):63-71
A类：
GSOR,多选择背包问题,MCKP,NGSOR
B类：
改进贪心算法,解扩,折扣,ESD,品数,解难,贪心策略,虚拟物,松弛,上证,等价,帕累托,IPA,价值密度
AB值：
0.154629
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
