计算机工程
計算機工程
계산궤공정
COMPUTER ENGINEERING
2008年
17期
37-38,49
,共3页
0-1背包问题%非递归算法%循环不变式
0-1揹包問題%非遞歸算法%循環不變式
0-1배포문제%비체귀산법%순배불변식
针对目前求解0-1背包问题算法的优缺点,开发了一种新的非递归算法.从计算0-1背包问题最优值的递归方程出发,使用形式推导技术及序列抽象数据类型.在开发出循环不变式的同时,归纳得到崩抽象程序没计语言Apla描述的非递归箅法,并形式化证明了其正确性,在相关工具及部件库的支持卜进一步得到C++程序.理论分析和实验结果表明,该算法的时间耗费受背包容量变化的影响很小,是一种有效的方案.
針對目前求解0-1揹包問題算法的優缺點,開髮瞭一種新的非遞歸算法.從計算0-1揹包問題最優值的遞歸方程齣髮,使用形式推導技術及序列抽象數據類型.在開髮齣循環不變式的同時,歸納得到崩抽象程序沒計語言Apla描述的非遞歸箄法,併形式化證明瞭其正確性,在相關工具及部件庫的支持蔔進一步得到C++程序.理論分析和實驗結果錶明,該算法的時間耗費受揹包容量變化的影響很小,是一種有效的方案.
침대목전구해0-1배포문제산법적우결점,개발료일충신적비체귀산법.종계산0-1배포문제최우치적체귀방정출발,사용형식추도기술급서렬추상수거류형.재개발출순배불변식적동시,귀납득도붕추상정서몰계어언Apla묘술적비체귀폐법,병형식화증명료기정학성,재상관공구급부건고적지지복진일보득도C++정서.이론분석화실험결과표명,해산법적시간모비수배포용량변화적영향흔소,시일충유효적방안.
