求解多背包约束下下模集函数最大值的近似算法及其性能保证

将部分穷举法与贪婪算法相结合,给出求解多背包约束下非减下模集函数最大值的近似算法．证明了该算法的性能保证是1-e^-1,算法的时间复杂性为O（3n^4）．     

双背包约束下下模函数最大值的贪婪算法

给出求解双背包约束下非减下模集函数最大值的近似算法,证明了该算法的性能保证是1-e^2-1。该算法结合了部分穷举法与贪婪算法,是对贪婪算法的一种改进。算法的时间复杂性为O（n^4）。