中文摘要：

目前,求解折扣{0-1}背包问题（D{0-1}KP）的主要算法是基于动态规划的具有伪多项式时间的确定性算法,当D{0-1}KP实例中各项的价值系数与重量系数在大范围内取值时缺乏实用性.文中基于杰出者保留策略遗传算法（EGA）求解D{0-1}KP,首先建立了D{0-1}KP的两个新的数学模型;然后,为了利用EGA和第一数学模型求解D{0-1}KP,提出了一种处理非正常编码个体的贪心修复与优化算法GROA,并将其与EGA相结合给出了求解D{0-1}KP的第一遗传算法FirEGA;紧接着,利用EGA和第二数学模型求解D{0-1}KP,提出了处理非正常编码个体的另一种有效算法NROA,并将其与EGA相结合给出了求解D{0-1}KP的第二遗传算法SecEGA;最后,利用四类大规模D{0-1}KP实例,确定了FirEGA和SecEGA的交叉概率与变异概率的合理取值,比较了两个算法的实际求解性能.对四类实例的计算结果表明：FirEGA和SecEGA都非常适于求解大规模的难D{0-1}KP实例,均能够得到一个近似比非常接近于1的近似解,并且FirEGA的平均求解性能比SecEGA的更优.

英文摘要：

At present, the deterministic algorithm based on dynamic programming is the main method for solving the discounted { 0-1} knapsack problem （D{ 0-1 } KP）. But its complexity is pseudo polynomial time, and when the value coefficients and the weight coefficients of the D{0-1 } KP instance are in a large range, the deterministic algorithm is no longer practical. In this paper, we use genetic algorithm with elitist reservation strategy （EGA） to solve the D{0-1 }KP. Firstly, we establish two new mathematical models of the D{0-1}KP. Secondly, in order to use EGA to solve the D {0-1 } KP based on the first mathematical model, we propose a greedy repair and optimization algorithm （GROA） to deal with the non-normal coding individual. Combining EGA with GROA, we give the first genetic algorithm （FirEGA） for solving the D{0-1 }KP. Thirdly, for solving the D{0-1 } KP by EGA and the second mathematical model, we propose another algorithm named NROA, which is an greedy repair and optimization algorithm too, to deal with the non-normal coding individual, and give the second genetic algorithm （SecEGA） for solving the D{0-1} KP based on EGA and NROA. Finally, we ascertain the reasonable values of the crossover probability and the mutation probability of the FirEGA and SecEGA on the basis of the computational results of four kinds instances of D{0-1 } KP. The computational results show that FirEGA and SecEGA are fit for solving the large instance of the hard D{ 0-1} KP, and they can obtain an approximation solution whose approximation rate is close to 1. Furthermore, the average performance of FirEGA is more efficient than SecEGA.