肖 颜 潘大志，2 冯世强

（1.西华师范大学数学与信息学院 南充 637009）（2.西华师范大学计算方法与应用研究所 南充 637009）

1 引言

背包问题（Knapsack Problem，KP）［1］是组合优化问题中一种典型的优化难题，在整数规划领域、资源调度问题、材料切割问题等有着非常重要的理论意义和广泛的应用价值。背包问题的扩展形式有很多，折扣｛0-1｝背包问题（Discount｛0-1｝Knap⁃sack Problem，D｛0-1｝KP）［2～7］就是其中的一种，在超市促销活动、项目决策投资和预算控制等方面具有广阔应用［5～6］。2005 年Guder 最早提出了单目标D｛0-1｝KP 问题［2］；2007 年Guldan 在单目标折扣背包问题的基础上提出了一种多目标D｛0-1｝KP 问题［4］，并利用动态规划进行求解；Rong［8］等针对D｛0-1｝KP问题，提出了一种基于核问题动态规划的求解算法；Aiying Rong 等结合动态规划对D｛0-1｝KP 的核（coer）问题进行研究［5］；He 等［7］针对D｛0-1｝KP 问题提出了几种不同的算法进行求解，如：精确算法、近似算法和二进制粒子群算法等，贺毅朝等［6］利用精英保留策略对D｛0-1｝KP 进行求解，同时提出了第一遗传算法（FirEGA）和第二遗传算法（SecEGA）；刘雪静等［9］为求解D｛0-1｝KP，提出了两种该背包问题的数学模型，并利用细菌觅食的方法进行求解；杨洋等［10］通过对D｛0-1｝KP 建立简化新模型，并给出求解算法。

猴群算法（MA）［11］主要是通过模拟自然界猴子爬山过程设计的，由Zhao 和Tang 于2008 年首次提出。该算法是一种新兴的群智能优化算法，可用于求解大规模、多维多峰优化问题，其突出优点在于能够有效的求解多种优化问题，如：线性问题、非线性问题、非凸问题、高维问题等，同时不需要考虑函数是否存在可微或可导现象，只需通过对当前位置的伪梯度的计算，利用两个临近的位置即可确定猴子在爬过程中需要搜索的方向。……