0-1背包问题的一种新解法

作     者：石海鹤 揭安全 薛锦云 SHI Hai-he;JIE An-quan;XUE Jin-yun

作者机构：江西师范大学计算机信息工程学院 

基　　金：江西省教育厅科研基金资助项目(GJJ08156) 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2008年第34卷第17期

页      码：37-38,49页

摘      要：针对目前求解0-1背包问题算法的优缺点,开发了一种新的非递归算法。从计算0-1背包问题最优值的递归方程出发,使用形式推导技术及序列抽象数据类型。在开发出循环不变式的同时,归纳得到用抽象程序设计语言Apla描述的非递归算法,并形式化证明了其正确性,在相关工具及部件库的支持下进一步得到C++程序。理论分析和实验结果表明,该算法的时间耗费受背包容量变化的影响很小,是一种有效的方案。

主 题 词：0-1背包问题 非递归算法 循环不变式 

学科分类：08[工学] 0835[0835] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1000-3428.2008.17.014

馆 藏 号：203317348...