0-1背包问题的一种新的启发式算法  

A Novel Heuristic Algorithm for the Knapsack Problem

作　　者：谈群[1] 夏敏学[2] 钱建刚[3] 彭飞[1] 

机构地区：[1]空军雷达学院研究生管理大队,武汉430019 [2]空军雷达学院机电工程系,武汉430019 [3]空军雷达学院预警探测指挥系,武汉430019

出　　处：《空军雷达学院学报》2006年第4期301-303,共3页Journal of Air Force Radar Academy

摘　　要：为了提高求解0-1背包问题的效率,提出了这类问题的一种基于贪婪算法的启发式近似算法,通过寻找尽可能大的可行解和尽可能小的上界,从而求出近似最优解,该算法最大的优点是可以给出计算误差,算法的最坏性能比是2,通过编程计算证明该算法具有良好的性能.In order to raise the efficiency of solving for knapsack problem, a heuristic approximate algorithm of knapsack problem was put forward in terms of the greedy algorithm. By looking for the utmost available solution and a probably small upper-bound, the approximate optimum solution can be found. The greatest feature of this method is that the calculation error can be deduced, and the worst case ratio is 2. By programming calculation it proves that this algorithm proposed works better.

关 键 词：0-1背包 启发式算法 贪婪算法 最坏性能比 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]