多选择背包问题的快速求解算法

华南理工大学学报（自然科学版） ›› 2009, Vol. 37 ›› Issue (4): 42-45.

多选择背包问题的快速求解算法

鲍江宏杨启贵

华南理工大学数学系, 广东广州 510640

收稿日期:2008-03-18 修回日期:2008-08-27 出版日期:2009-04-25 发布日期:2009-04-25
通信作者: 鲍江宏（1971-），女，博士生，讲师，主要从事最优化算法、微分方程与动力系统研究． E-mail:majhbao@scut．edu．cn
作者简介:鲍江宏（1971-），女，博士生，讲师，主要从事最优化算法、微分方程与动力系统研究．
基金资助:
国家自然科学基金资助项目（10871074）

Fast Solution Algorithm of Multiple-Choice Knapsack Problem

Bao Jiang-hong Yang Qi-gui

Department of Mathematics, South China University of Technology, Guangzhou 510640, Guangdong, China

Received:2008-03-18 Revised:2008-08-27 Online:2009-04-25 Published:2009-04-25
Contact: 鲍江宏（1971-），女，博士生，讲师，主要从事最优化算法、微分方程与动力系统研究． E-mail:majhbao@scut．edu．cn
About author:鲍江宏（1971-），女，博士生，讲师，主要从事最优化算法、微分方程与动力系统研究．
Supported by:
国家自然科学基金资助项目（10871074）

摘要/Abstract

摘要： 背包问题属于组合优化中的经典问题，它有许多重要的变形，其中以多选择背包问题最为复杂．为更快地求解多选择背包问题，文中首先对该问题进行了理论分析，然后基于动态规划提出了一种新的求解算法，并对一个复杂的案例进行了测试．结果表明，这种新算法比遗传算法快9．4倍，比传统的0-1整数规划求解法快78倍．通过对数学模型的改进可大大降低问题的规模．更重要的是，所用方法可避免求解任何线性规划问题．

关键词: 背包问题, 组合优化, 动态规划

Abstract:

Knapsack problem is a classical combinatorial optimization problem. There are many important variations of the knapsack problem, among which the Multiple-Choice Knapsack Problem （MCKP） is the most complicated. In order to fast solve the MCKP, a theoretical analysis is performed in this paper, and a novel solution algorithm is proposed based on dynamic programming. Then, a complicated case is tested using the proposed algorithm. The re- sults indicate that （ 1 ） the proposed algorithm is 9.4 times faster than the genetic algorithm and 78 times faster than the conventional 0-1 integer programming method ; （2） the improvement of the mathematical model greatly reduces the solving scale of the knapsack problem ; and （ 3 ） the proposed algorithm makes it unnecessary to solve any linear programming problem.

Key words: knapsack problem, combinatorial optimization, dynamic programming

鲍江宏杨启贵. 多选择背包问题的快速求解算法[J]. 华南理工大学学报（自然科学版）, 2009, 37(4): 42-45.

Bao Jiang-hong Yang Qi-gui. Fast Solution Algorithm of Multiple-Choice Knapsack Problem[J]. Journal of South China University of Technology (Natural Science Edition), 2009, 37(4): 42-45.

[1]	赵克刚, 何坤阳, 黎杰, 等. 基于改进动态规划法的HEV多目标能量管理策略[J]. 华南理工大学学报(自然科学版), 2022, 50(9): 138-148.
[2]	任远马智亮向星磊. 集中管理下园区设备的维护策略决策模型及算法[J]. 华南理工大学学报（自然科学版）, 2020, 48(9): 51-60.
[3]	管超张则强李云鹏贾林. 一种求解双层过道布置问题的离散花授粉算法[J]. 华南理工大学学报（自然科学版）, 2019, 47(10): 60-74.
[4]	苗强孔凡敏孙强白书战李国祥. 基于动态规划的自适应等效最小燃油消耗策略[J]. 华南理工大学学报（自然科学版）, 2016, 44(12): 81-88.
[5]	王晨郭明林刘国志. 新型功率分流混合动力汽车的动力性优化[J]. 华南理工大学学报（自然科学版）, 2015, 43(11): 96-104.
[6]	于宏涛高立群韩希昌. 求解旅行商问题的离散人工萤火虫算法[J]. 华南理工大学学报（自然科学版）, 2015, 43(1): 126-131,139.
[7]	于丽敏熊会元宗志坚张庆. 基于动态规划的电动汽车加速过程优化控制[J]. 华南理工大学学报（自然科学版）, 2014, 42(8): 143-148.
[8]	冯小峰刘明波. 基于执行依赖启发式动态规划的紧急电压控制[J]. 华南理工大学学报（自然科学版）, 2014, 42(4): 19-25,58.
[9]	李拥军敖道敢. 一种快速模式近似匹配算法[J]. 华南理工大学学报(自然科学版), 2012, 40(6): 103-108.
[10]	徐玉滨丁哲沙学军. 基于遗传算法的可重配置系统动态规划和管理[J]. 华南理工大学学报（自然科学版）, 2010, 38(9): 13-19.
[11]	邓宇乔杜明辉梁亚玲廖冰. 基于背包问题的可纠错数字签名方案[J]. 华南理工大学学报（自然科学版）, 2010, 38(6): 46-49.
[12]	陈自郁何中市何静媛. 一种求解集合组合问题的离散粒子群优化模型[J]. 华南理工大学学报（自然科学版）, 2010, 38(4): 141-146.
[13]	李南希金连文. 脱机无约束手写体中文文本行的字符切分方法[J]. 华南理工大学学报（自然科学版）, 2010, 38(10): 74-78.
[14]	张志毅文福栓刘敏忠. 电力系统负荷恢复优化的并行遗传算法实现[J]. 华南理工大学学报（自然科学版）, 2007, 35(6): 38-42.
[15]	高学. 基于动态规划的联机手写汉字分割方法[J]. 华南理工大学学报（自然科学版）, 2007, 35(1): 70-73,79.