-
题名改进贪心算法求解扩展简化折扣{0-1}背包问题
被引量：2
- 1
-
-
作者
林洪
邓艳
-
机构
中国人民武装警察部队警官学院基础部
-
出处
《西南师范大学学报（自然科学版）》
CAS
2022年第11期63-71,共9页
-
文摘
扩展简化折扣{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%.
-
关键词
贪心算法
扩展折扣{0-1}背包问题(ESD{0-1}KP)
改进帕累托算法(ipa)
价值密度
多选择背包问题(MCKP)
-
Keywords
greedy algorithm
extended discounted{0-1}knapsack problem(ESD{0-1}KP)
improved pareto algorithm(ipa)
value density
multiple-choice knapsack problem(MCKP)
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-
