| 0-1背包问题的一种新解法 |
| |
| 引用本文： | 石海鹤,揭安全,薛锦云.0-1背包问题的一种新解法[J].计算机工程,2008,34(17):37-38,4. |
| |
| 作者姓名： | 石海鹤 揭安全 薛锦云 |
| |
| 作者单位： | 1. 江西师范大学计算机信息工程学院,南昌,330022;中国科学院软件研究所计算机科学国家得点实验室,北京,100080
2. 江西师范大学计算机信息工程学院,南昌,330022 |
| |
| 摘 要： | 针对目前求解0-1 背包问题算法的优缺点，开发了一种新的非递归算法。从计算0-1 背包问题最优值的递归方程出发，使用形式推导技术及序列抽象数据类型。在开发出循环不变式的同时，归纳得到用抽象程序设计语言Apla描述的非递归算法，并形式化证明了其正确性，在相关工具及部件库的支持下进一步得到C++程序。理论分析和实验结果表明，该算法的时间耗费受背包容量变化的影响很小，是一种有效的方案。
|
| 关 键 词： | 0-1背包问题 非递归算法 循环不变式 |
| 修稿时间： | |
New Algorithm of 0-1 Knapsack Problem |
| |
| SHI Hai-he,JIE An-quan,XUE Jin-yun.New Algorithm of 0-1 Knapsack Problem[J].Computer Engineering,2008,34(17):37-38,4. |
| |
| Authors: | SHI Hai-he JIE An-quan XUE Jin-yun |
| |
| Affiliation: | (1. College of Computer Information and Engineering, Jiangxi Normal University, Nanchang 330022; 2. National Key Laboratory for Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080) |
| |
| Abstract: | According to the features of the existed algorithms of 0-1 knapsack problem, a new non-recursive algorithm is formally derived in the paper. From the recursive equations for computing optimal value of 0-1 knapsack problem, by employing the formal derivation technique and abstract data type, sequence, achieves loop invariant and non-recursive Apla abstract algorithm. The Apla algorithm is verified formally, and further transformed to C++ program by related tool and component library. The theoretical analysis and experimental results show that the time complexity of new algorithm is little affected by bag capacity. |
| |
| Keywords: | 0-1 knapsack problem non-recursive algorithm loop invariant |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
|
