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

Improved Greedy Algorithm to Solve Extended Simplified Discounted{0-1}Knapsack Problem

作　　者：林洪 邓艳 LIN Hong;DENG Yan(Department of Basic Courses,Officers College of PAP,Chengdu 610213,China)

机构地区：[1]中国人民武装警察部队警官学院基础部,成都610213

出　　处：《西南师范大学学报(自然科学版)》2022年第11期63-71,共9页Journal of Southwest China Normal University(Natural Science Edition)

摘　　要：扩展简化折扣{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%.The Extended Simplified Discount{0-1}Knapsack Problem(ESD{0-1}KP)is an extension of the Discounted{0-1}Knapsack Problem(D{0-1}KP).The ESD{0-1}KP increases the number of items in each item set in D{0-1}KP,which makes it more difficult to solve,and the existing Greedy Strategy Operator(GSOR)algorithm is not effective.Based on the ESD{0-1}KP model,a virtual item that value and weight of 0 is added to each item set,and the constraints in the ESD{0-1}KP model is relaxed.Moreover,we prove that the ESD{0-1}KP is equivalent to the Multiple Choice Knapsack Problem(MCKP)theoretically.A New Greedy Strategy Operator(NGSOR)is proposed by combining with the Improved Pareto Algorithm(IPA).NGSOR firstly expresses the selection of multiple items in the same item set by adding items,and then selects items in order of value density from highest to lowest.If the value of the selected item is more than the value of the selected item in the item set where the item is located,the item set is iterated.The simulation results show that,compared with GSOR,the NGSOR has an average improvement of 24.56%in solution accuracy and 44.95%in solution speed.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]