周口师范学院学报
週口師範學院學報
주구사범학원학보
JOURNAL OF ZHOUKOU TEACHERS COLLEGE
2010年
5期
45-47
,共3页
赵杏利%雷习军%李小平%何尚录
趙杏利%雷習軍%李小平%何尚錄
조행리%뢰습군%리소평%하상록
组合优化%下模集函数%近似算法%性能保证
組閤優化%下模集函數%近似算法%性能保證
조합우화%하모집함수%근사산법%성능보증
给出了在实数范围内求解多背包约束条件下下模集函数最大值问题的一种改进的近似算法,是MaximSviridenko所给出的整数范围内求解单背包约束下下模集函数最大值的扩展.该算法的时间复杂性为:O(kn4),其性能保证为(1-e-1/D).
給齣瞭在實數範圍內求解多揹包約束條件下下模集函數最大值問題的一種改進的近似算法,是MaximSviridenko所給齣的整數範圍內求解單揹包約束下下模集函數最大值的擴展.該算法的時間複雜性為:O(kn4),其性能保證為(1-e-1/D).
급출료재실수범위내구해다배포약속조건하하모집함수최대치문제적일충개진적근사산법,시MaximSviridenko소급출적정수범위내구해단배포약속하하모집함수최대치적확전.해산법적시간복잡성위:O(kn4),기성능보증위(1-e-1/D).
