中文摘要：

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

英文摘要：

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.