0-1背包问题的预期效率和线性拟合求解

doi:10.11772/j.issn.1001-9081.2014.09.2581

计算机应用 ›› 2014, Vol. 34 ›› Issue (9): 2581-2584.DOI: 10.11772/j.issn.1001-9081.2014.09.2581

0-1背包问题的预期效率和线性拟合求解

张玲玲,张弘

北华大学计算机科学技术学院，吉林吉林 132013

收稿日期:2014-03-17 修回日期:2014-05-23 出版日期:2014-09-01 发布日期:2014-09-30
通讯作者: 张弘
作者简介:
张玲玲(1981-),女,吉林吉林人,讲师,硕士,主要研究方向:图形图像、软件工程;
张弘(1980-),男,吉林吉林人,助理研究员,硕士,主要研究方向:教育管理。

Solution of 0-1 knapsack problem based on expected efficiency and linear fitting

ZHANG Lingling,ZHANG Hong

College of Computer Science and Technology, Beihua University, Jilin Jilin 132013, China

Received:2014-03-17 Revised:2014-05-23 Online:2014-09-01 Published:2014-09-30
Contact: ZHANG Hong

摘要/Abstract

摘要：

为了进一步优化0-1背包问题的解，就背包容量、物体个数、物体重量、物体价格和物体性价比之间的关系进行深入的分析研究，构建了一个基于数学理论的线性拟合模型，与预期效率相结合，给出了一个解决0-1背包问题的混合算法。给出了三组实验，测试ρ<0.7时的算例，当背包容量改变时，与萤火虫群算法相比，该算法提高了目标函数值的收敛速度，同时节省了存储空间；与单纯的预期效率算法相比，该算法能够求得最优解，而单纯的预期效率算法则不能。实验结果表明，预期效率和线性拟合混合算法具有合理性及准确性，该算法能够应用于解决实际的0-1背包问题。

Abstract:

In order to do further optimization on 0-1 Knapsack Problem (KP), the relationship among the backpack capacity, the number of objects, the weight of object, the price of object and the cost performance of object were analyzed, a linear fitting model based on mathematical theory was determined, and a hybrid algorithm for 0-1 KP was proposed with the expected efficiency. Three groups of experiments were given. For those examples with ρ<0.7, when the backpack capacity was changed, in comparison with artificial glowworm swarm algorithm, the proposed algorithm improved convergence speed of the objective value and saved the storage space; In comparison with the algorithm of absolute greedy and expected efficiency, the proposed algorithm got the optimal solution. The results prove that this hybrid algorithm is reasonable and exact, and it can be used widely to solve 0-1 KP.

中图分类号:

张玲玲张弘. 0-1背包问题的预期效率和线性拟合求解[J]. 计算机应用, 2014, 34(9): 2581-2584.

ZHANG Lingling ZHANG Hong. Solution of 0-1 knapsack problem based on expected efficiency and linear fitting[J]. Journal of Computer Applications, 2014, 34(9): 2581-2584.

参考文献

［1］MERKLE R, HELLMAN M. Hiding information and signatures in trapdoor knapsacks ［J］. IEEE Transactions on Information Theory, 1978, 24(5): 525-530.

［2］WANG N, XIANG F, MAO J. Modified adaptive genetic algorithm for solving 0/1 knapsack problems ［J］. Journal of Computer Applications, 2012, 32(6): 1682-1684. (王娜,向凤红,毛剑琳.改进的自适应遗传算法求解0/1背包问题［J］. 计算机应用,2012,32(6):1682-1684.)

［3］COLORNI A, DORIGO M, MAFFIOLI F. Heuristics from nature for hard combinatorial problem ［J］. International Transcations in Operational Research, 1996, 3(1): 1-21.

［4］LE T. A summary of genetic algorithm on 0/1 knapsack problem ［J］. Journal of Zhejiang Ocean Uniersity: Nature Science Edition, 2013, 32(1): 71-74. (乐天.遗传算法求解0/1背包问题的综述［J］. 浙江海洋学院学报:自然科学版,2013,32(1):71-74.)

［5］ZOU D, GAO L, LI S, et al.Solving 0-1 knapsack problem by a novel global harmony search algorithm [J]. Applied Soft Computing, 2011, 11(2): 1556-1564.

［6］QIAN Q, CHENG M. Binary ant colony algorithm based on bug artificial life for 0/1 knapsack problem ［J］. Computer Technology and Development, 2013, 23(4): 43-46. (钱乾,程美英.人工生命Bug模型二元蚁群算法求解多0-1背包问题［J］. 计算机技术与发展,2013,23(4):43-46.)

［7］WANG H, WU H. MapReduce-based ant colony optimization algorithm for multi-dimensional knapsack problem ［J］. Computer Engineering, 2013, 39(4):248-253. (王会颖,吴昊. 求解多维背包问题的MapReduce蚁群优化算法［J］. 计算机工程,2013,39(4):248-253.)

［8］HE Y, TIAN H. Solving dynamic 0-1 knapsack problem based on dynamic programming algorithm ［J］. Computer Science, 2012, 39(7): 237-241. (贺毅朝,田海燕. 基于动态规划求解动态0-1背包问题［J］.计算机科学,2012,39(7):237-241.)

［9］CHENG K, MA L. Artificial glowworm swarm optimization algorithm for 0-1 knapsack problem ［J］. Application Research of Computers, 2013, 30(4): 993-999. (程魁,马良. 0-1背包问题的萤火虫群优化算法［J］. 计算机应用研究, 2013,30(4):993-999.)

［10］HUANG Z, LIU J. Prospect theory model for multiple criteria decision making alternative with interval number［J］. Systems Engineering and Electronics, 2012, 34(5): 977-981. (黄智力,刘健. 属性值为区间数的决策对象预期理论模型研究［J］.系统工程与电子技术,2012,34(5):977-981.)

［11］SHI L, ZHANG Y, LYU J. Optimization algorithm of 0-1 knapsack problem based on absolute greedy and expected efficiency［J］. Application Research of Computers, 2014, 31(3): 684-687. (史岚,张义宏,吕建辉. 基于绝对贪心和预期效率的0-1背包问题优化［J］. 计算机应用研究,2014,31(3):684-687.)

［12］PER M C. Efficient calculation of unbiased expectation values in diffusion quantum Monte Carlo ［J］. Physical Review B: Condensed Matter and Materials Physics, 2012, 86(20): 201-207.

[1]	杜航原郝思聪王文剑. 结合图自编码器与聚类的半监督表示学习方法[J]. 计算机应用, 0, (): 0-0.
[2]	陈露张晓霞于洪. 基于先验知识的非负矩阵半可解释三因子分解算法[J]. 计算机应用, 0, (): 0-0.
[3]	韩舒宁徐敏董学士林青沈凡凡. 混合伊藤算法求解多尺度着色旅行商问题[J]. 计算机应用, 0, (): 0-0.
[4]	李晓杰崔超然宋广乐苏雅茜吴天泽张春云. 基于时序超图卷积神经网络的股票趋势预测方法[J]. 计算机应用, 0, (): 0-0.
[5]	张建严珂马祥. 基于神经网络的复杂垃圾信息过滤算法分析[J]. 计算机应用, 0, (): 0-0.
[6]	邱云志汪廷华戴小路. 双重特征加权模糊支持向量机[J]. 计算机应用, 0, (): 0-0.
[7]	李宗正周恺卿丁雷欧云. 基于基因交换的自适应人工鱼群算法[J]. 计算机应用, 0, (): 0-0.
[8]	刘清华廖士中. 基于随机素描方法的在线核回归[J]. 计算机应用, 0, (): 0-0.
[9]	张小清王晨曦吕彦林耀进. 基于ReliefF的层次分类在线流特征选择算法[J]. 计算机应用, 0, (): 0-0.
[10]	于婉莹梁美玉王笑笑陈徵曹晓雯. 基于深度注意力网络的课堂教学视频中学生表情识别与智能教学评估[J]. 计算机应用, 0, (): 0-0.
[11]	黄勇康梁美玉王笑笑陈徵曹晓雯. 基于深度时空残差卷积神经网络的课堂教学视频中多人课堂行为识别[J]. 计算机应用, 0, (): 0-0.
[12]	康猛蒙祖强. 基于局部条件区分能力的高效属性约简算法[J]. 计算机应用, 0, (): 0-0.
[13]	谢鑫张贤勇王旋晔唐鹏飞. 变精度邻域等价粒邻域决策树构造算法[J]. 计算机应用, 0, (): 0-0.
[14]	刘忠慧王梓宥闵帆. 近似概念的遗传生成算法及其推荐应用[J]. 计算机应用, 0, (): 0-0.
[15]	潘仁志钱付兰赵姝张燕平. 基于卷积神经网络交互的用户属性偏好建模的推荐模型[J]. 计算机应用, 0, (): 0-0.

0-1背包问题的预期效率和线性拟合求解

Solution of 0-1 knapsack problem based on expected efficiency and linear fitting

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics