摘要
给出了求解背包问题的一种新的近似算法,这一算法是一种改进的贪婪算法,即将部分枚举法与贪婪算法相结合.从而使其具有更好的性能保证.同时,从理论上证明了这一算法的可靠性.最后,通过具体算例验证了算法的有效性.
This paper presents a new approximation algorithm for knapsack problem. The algorithm is an improved greedy algorithm which combined the part of enumeration method with the greedy algorithm, thus to make it a better performance guarantee. At the same time, the reliability of this algorithm is theoretically proved. Finally,the effectiveness of the algorithm is verified by the specific example.
出处
《兰州交通大学学报》
CAS
2007年第6期131-133,共3页
Journal of Lanzhou Jiaotong University
基金
甘肃省自然科学基金项目(3ZS042-B25-039)
光电技术智能控制教育部重点实验室(兰州交通大学)开放基金资助项目(K04106)
关键词
背包问题
贪婪算法
性能保证
knapsack problem
greedy algorithm
performance guarantee
