背包问题的一个k阶优化遗传算法

Approximation Algorithm for Knapsack Problem

背包问题是一个NP困难问题,该文在已有的性能比为(k+1)/k的k阶优化算法基础上,提出一个具有与k阶优化算法具有相同的近似性能比的启发式算法:将k阶优化法的结果加入遗传算法的初始种群使原本没有性能比保证的遗传算法具有近似性能比,在保证计算精度的同时大大降低算法的搜索次数,从而提高计算效率。这种算法也具有较高的适应性,可以根据计算速度或精度要求选择适当的正整数k。该文对提到的多种算法编程实现并加以分析,通过比较各种算法的程序输出结果和CPU时间,验证了结论的正确性。

The knapsack problem(KP) is a NP-hard problem,approximate algorithms is discussed in this paper.Based on k-optimal algorithm with performance ratio(k+1)/k,a heuristic combined k-optimal algorithm with genetic is proposed which keeps the same approximate rate of k-optimal,and the time complexity is largely decreased.k can be selected suitably upon the desired precision.CPU times and calculation results of deferent algorithm programs are compared to verify our conclusion.