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

• 作者: 揭安全 石海鹤 薛锦云
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 0-1背包问题 非递归算法 循环不变式
• 年，卷（期）: 2008,（17）
• 所属期刊栏目: 软件技术与数据库
• 页码范围: 37-38,49
• 页数: 3页
• 分类号: TP311
• 字数: 4059字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2008.17.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	石海鹤	江西师范大学计算机信息工程学院	18	111	6.0	10.0
3	薛锦云	江西师范大学计算机信息工程学院	77	745	15.0	23.0
7	揭安全	江西师范大学计算机信息工程学院	29	147	7.0	10.0