摘要
0/1背包问题是运筹学中的著名问题,有重要的使用价值,是算法研究的热点,目前较成熟的常用算法有贪心算法、动态规划、回溯法、分枝-限界法等。本文探讨动态规划的向前处理法。与教材不同的是,本文结合实例,给出递推关系式的具体递推过程,用图例表示背包问题的向前处理法求解过程;最后,用浅显的实例验证向前处理法算法所得最优解的正确性。
0/1 knapsack problem is a famous task of operational research, it has the important value of using and is the hot issue of algorithm research, for the being time, there are some mature algorithms, suehas greedy algorithm, dynamic design, baektraeking, braneh-and-bound,etc. This paper explored the going-ahead method of dvnamic design and offered the conerete solution. It is different part from text that this paper use diagram to express the course of solution. At last, it use plain example to verify the correction of going ahead method.
出处
《现代计算机》
2005年第12期106-107,共2页
Modern Computer
关键词
0/1背包
动态规划
图解背包
最优性原理
0/1 Knapsack
Dynamic Design
Knapsack Diagram, Principle of Optimality
