有序组合树法求解0-1背包问题初探  

On the Sequential Combination Tree Algorithm for 0-1 Knapsack Problem

作　　者：安晨[1] 付永军[1] 

机构地区：[1]兰州交通大学交通运输学院,甘肃兰州730070

出　　处：《温州大学学报（自然科学版）》2008年第1期10-14,共5页Journal of Wenzhou University(Natural Science Edition)

摘　　要：以0-1背包问题为研究对象,建立数学模型,采用有序组合树法对中小规模的背包问题进行求解.与传统的贪婪算法相比,该算法更容易找到最优解.并通过实例说明该算法对解决中小规模的0-1背包问题是行之有效的.With 0-1 knapsack problem being research object, this paper has set up a mathematical model for 0-1 knapsack problem. Planning to solve 0-1 knapsack problem for medium-sized and small scale by the sequential combination tree algorithm, through analysis and computation for the concrete example, it is proved that the sequential combination tree algorithm is feasible and effective for solving 0-1 knapsack problem for medium and small scale, compared to traditional greedy algorithm, the optimal solution is very easy to be found.

关 键 词：背包问题 有序组合树 算法 

分 类 号：O221.4[理学—运筹学与控制论]