0－1背包问题多重分枝－限界算法的改进

An Improvement on the Multi-Branch-and-BoundAlgorithm for0-1Knapsack Problems

对０－ｌ背包问题多重分枝一限界算法［１］作了改进。经改进的算法仅用一棵状态空间树描述问题的解空间。引入了虚拟背包的概念，简化了限界函数的计算。新的算法较大地提高了搜索最优解的效率。

This paper has improved on the multi - branch-and-bound algorithmfor 0 - 1 knapsack problems[1].The method uses one state spacetree to describe thesolution space of the problem. A new concept, fictitious knapsack, is given tosimplify counting the upper bound function. This improved algorithm can solve 0 1 knapsack problems with more than one knapsack efficiently.