摘要
0-1背包问题是组合优化领域里的一个典型问题,是属于易于描述却难于解决的NP难题,有效解决0-1背包问题具有重要意义。首先给出了0-1背包问题的描述,然后详细介绍了回溯法和分支限界法的算法思想和搜索策略,并对两种算法进行了比较和分析。
0-1 knapsack problem is a typical problem of combinatorial optimization,it＇s a NP-problem which is easy to describe but hard to be solved,so it has significance to solve the problem efficiently.The description of 0-1 knapsack problem is firstly introduced,then the algorithm idea and search strategy of backtracking and branch-bound algorithm are introduced,finally two algorithms are compared and analyzed.
出处
《信息技术》
2011年第2期27-29,共3页
Information Technology
基金
延安大学专项科研基金(YD2007-21)
关键词
0-1背包问题
回溯法
分支限界法
0-1 knapsack problem
backtracking
branch-bound algorithm
