Journal of South China University of Technology (Natural Science Edition) ›› 2009, Vol. 37 ›› Issue (4): 42-45.

• Computer Science & Technology • Previous Articles     Next Articles

Fast Solution Algorithm of Multiple-Choice Knapsack Problem

Bao Jiang-hong  Yang Qi-gui   

  1. 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）

PDF

1167

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