摘要
介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法。以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用。
The knapsack problem and 0-1 knapsack problem are introduced, the backtracking algorithm （one of the basic methods of the computer algorithm design） and the concept of state space are described, a backtracking algorithm based on dynamic state space tree which is useful for resolving linear programming is proposed. Take 0-1 knapsack problem for example, in contrast to static state space tree algorithm, the new algorithm spends less times and it helps to extend the application of backtracking algorithm.
出处
《计算机工程与设计》
CSCD
北大核心
2007年第4期755-756,759,共3页
Computer Engineering and Design
关键词
背包问题
状态空间
回溯
算法
树
knapsack problem
state space
backtracking
algorithm
tree
