Abstract: The Discounted {0-1} Knapsack Problem （D{0-1}KP） is an extension of the classical 0-1 Knapsack Problem（0-1KP）. In this paper, it uses Bacterial Foraging Optimization algorithm（BFO） to solve D{0-1}KP, Firstly, the two mathematical models of the D{0-1}KP are described, and then BFO is combined with the two mathematical models, the bacterial individual uses the binary vector and the four binary vector coding method, and the greedy strategy is used to optimize the initial solution and repair the non normal coding individuals, FirBFO and SecBFO algorithms for solving D{0-1}KP are given. The calculations of four instances show that, FirBFO and SecBFO are suitable for solving large scale hard D{0-1}KP. And they can also obtain the approximate solution whose approximation rate is almost equal to 1.

Key words: discounted {0-1} knapsack problem, bacterial foraging optimization algorithm, greedy strategy, repair and optimization

摘要： 折扣{0-1}背包问题（D{0-1}KP）是新型的0-1背包问题。提出了基于细菌觅食算法（BFO）求解D{0-1}KP的方法，首先描述了D{0-1}KP的两个数学模型，然后将BFO分别与两个数学模型相结合，即细菌个体分别采用二进制向量和四进制向量的编码方法，并利用贪心策略优化初始解和修复非正常编码个体，给出了求解D{0-1}KP的FirBFO和SecBFO算法。对四类实例的计算结果表明，FirBFO和SecBFO都非常适于求解大规模的D{0-1}KP实例，能得到最优解或近似比接近1的近似解。

关键词: 折扣{0-1}背包问题, 细菌觅食算法, 贪心策略, 修复与优化