摘要: 针对目前求解0-1 背包问题算法的优缺点,开发了一种新的非递归算法。从计算0-1 背包问题最优值的递归方程出发,使用形式推导技术及序列抽象数据类型。在开发出循环不变式的同时,归纳得到用抽象程序设计语言Apla描述的非递归算法,并形式化证明了其正确性,在相关工具及部件库的支持下进一步得到C++程序。理论分析和实验结果表明,该算法的时间耗费受背包容量变化的影响很小,是一种有效的方案。
关键词:
0-1背包问题,
非递归算法,
循环不变式
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.
Key words:
0-1 knapsack problem,
non-recursive algorithm,
loop invariant
中图分类号:
石海鹤;揭安全;薛锦云;. 0-1背包问题的一种新解法[J]. 计算机工程, 2008, 34(17): 37-38,4.
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.