求解背包问题的一种新的近似算法

摘要：

给出了求解背包问题的一种新的近似算法,这一算法是一种改进的贪婪算法,即将部分枚举法与贪婪算法相结合.从而使其具有更好的性能保证.同时,从理论上证明了这一算法的可靠性.最后,通过具体算例验证了算法的有效性.

关键词：背包问题、贪婪算法、性能保证.

所属期刊栏目：26

分类号：O221.7(运筹学)

资助基金：甘肃省自然科学基金3ZS042-B25-039;光电技术智能控制教育部重点实验室兰州交通大学开放基金K04106

在线出版日期：2008-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：131-133