四川兵工学报
四川兵工學報
사천병공학보
SICHUAN ORDNANCE JOURNAL
2012年
12期
126-128
,共3页
组合最优化%背包约束%下模集函数%贪婪算法
組閤最優化%揹包約束%下模集函數%貪婪算法
조합최우화%배포약속%하모집함수%탐람산법
给出了求解多维背包约束下单调非减下模集函数最大值的近似算法,证明了该算法的性能保证是1-e-1。该算法结合了部分穷举法与贪婪算法,是对贪婪算法的一种改进,该算法的时间复杂性为O（n4）。
給齣瞭求解多維揹包約束下單調非減下模集函數最大值的近似算法,證明瞭該算法的性能保證是1-e-1。該算法結閤瞭部分窮舉法與貪婪算法,是對貪婪算法的一種改進,該算法的時間複雜性為O（n4）。
급출료구해다유배포약속하단조비감하모집함수최대치적근사산법,증명료해산법적성능보증시1-e-1。해산법결합료부분궁거법여탐람산법,시대탐람산법적일충개진,해산법적시간복잡성위O（n4）。
