摘要
为了提高求解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.
出处
《空军雷达学院学报》
2006年第4期301-303,共3页
Journal of Air Force Radar Academy
关键词
0-1背包
启发式算法
贪婪算法
最坏性能比
knapsack problem
heuristic algorithm
greedy algorithm
worst case ratio
