摘要
本文对“0/1背包问题”采用贪婪算法、动态规划、回溯法、分枝限界四种不同方法进行求解和算法分析,并通过各种算法的实现,研究了0/1背包问题的实质。
This paper applies four different approaches,which are greedy method, dynamic programming,backtracking,branch and bound,respectively,to solve 0/1 knapsack problem and analyze algorithm efficiency,then discusses the essence of 0/1 knapsack problem based on the realization of each algorithm.
出处
《电脑知识与技术》
2006年第2期96-97,共2页
Computer Knowledge and Technology
关键词
背包问题
贪婪算法
动态规划
回溯法
分枝限界
Knapsack problem
Greedy method
Dynamic programming
Backtracking
Branch and bound
