计算机工程与应用2018，Vol.54Issue(2)：155-162,8.DOI:10.3778/j.issn.1002-8331.1608-0168
基于细菌觅食算法求解折扣{0-1}背包问题的研究
摘要
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 opti-mize 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.关键词
折扣{0-1}背包问题/细菌觅食算法/贪心策略/修复与优化Key words
discounted{0-1}knapsack problem/bacterial foraging optimization algorithm/greedy strategy/repair and optimization分类
信息技术与安全科学引用本文复制引用
刘雪静,贺毅朝,吴聪聪,才秀凤..基于细菌觅食算法求解折扣{0-1}背包问题的研究[J].计算机工程与应用,2018,54(2):155-162,8.基金项目
河北省高等学校科学研究计划项目(No.ZD2016005) （No.ZD2016005）
河北省自然科学基金(No.F2016403055). （No.F2016403055）
