摘要
0／1背包问题是实际当中经常遇到的一类经典NP—hard组合优化问题之一。本文分别从贪心方法、动态规划、回溯法、分枝-限界法．遗传算法这五种算法设计方法入手，概述了各种设计方法的基本原理，提出了求解0／1背包问题的算法思想，并对算法进行分析．提出了改进方法。
The 0/1 knapsack problem is a classic NP-hard problem in the combinational optimizationl which is often encountered in practice. This paper will introduce five algorithm design methods, which are Greedy method, Dynamic programming, Backtracking, Branch and bound, Genetic algorithm, summarize their basic tenets, give the solving algorithm thought to 0/1 knapsack problem, analyse the algorithms and put forward the improving methods.
作者
黄波
蔡之华
HUANG Bo, CAI Zhi-hua （Computer School, China University of Geosciences, Wuhan 430074, China）
出处
《电脑知识与技术》
2007年第4期229-231,共3页
Computer Knowledge and Technology
基金
湖北省人文基地资助项目（2004B0011）
关键词
0/1背包问题
贪心方法
动态规划
回溯法
分枝-限界法
遗传算法
0/1 knapsack problem
Greedy method
Dynamic programming
Backtracking
Branch and bound
Genetic algorithm
