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

A New Approximate Algorithm for the Knapsack Problem

作　　者：张生[1] 梁国宏[1] 黄辉[1] 何尚录[1] 

机构地区：[1]兰州交通大学数理与软件工程学院,甘肃兰州730070

出　　处：《兰州交通大学学报》2007年第6期131-133,共3页Journal of Lanzhou Jiaotong University

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

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

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

分 类 号：O221.7[理学—运筹学与控制论]