摘要
"背包问题"是一个典型问题,其求解也是算法设计及验证的一个热点。在此分别采用优先策略、动态规划及递归三种不同方法对"背包问题"进行求解、算法设计及验证。实践证明了三种算法的正确性。在复杂度分析中,优先策略算法的空间及时间复杂度最低,而动态规划法具有明显的优势。
Knapsack problem is typical problem in computer science and its solution is a hot spot in algorithms design and verification. The solutions for the knapsack problems, algorithms design and verification with three different means：preference strategy, dynamic programming and recursion. Correctness of these three algorithms are proved, in the complexity analysis, the complexity of space and time in preference strategy is lowest, while the dynamic programming has obvious superiority.
出处
《现代电子技术》
2010年第2期128-130,共3页
Modern Electronics Technique
关键词
背包算法
优先策略
动态规划
栈操作
knapsack problem
preference strategy
dynamic programming
stack peration
