10.3969/j.issn.1000-3428.2008.17.014
0-1背包问题的一种新解法
针对目前求解0-1背包问题算法的优缺点,开发了一种新的非递归算法.从计算0-1背包问题最优值的递归方程出发,使用形式推导技术及序列抽象数据类型.在开发出循环不变式的同时,归纳得到崩抽象程序没计语言Apla描述的非递归箅法,并形式化证明了其正确性,在相关工具及部件库的支持卜进一步得到C++程序.理论分析和实验结果表明,该算法的时间耗费受背包容量变化的影响很小,是一种有效的方案.
0-1背包问题、非递归算法、循环不变式
34
TP311(计算技术、计算机技术)
江两省教育厅科研基金资助项目GJJ08156
2008-12-15(万方平台首次上网日期,不代表论文的发表时间)
共3页
37-38,49