资源描述：
《0_1背包问题的贪心局部搜索算法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第30卷第5期闽江学院学报Vol.30No.52009年10月JOURNALOFMINJIANGUNIVERSITYOct.20090-1背包问题的贪心局部搜索算法研究林宏(闽江学院物理学与电子信息工程系,福建福州350108)摘要:为了提高求解0-1背包问题的效率,提出了两种贪心局部搜索算法,分别称为固定候选算法和变化候选算法.算法都以有效的方式构造好的初始解,随后执行局部搜索对其进行解质量上的改进.实验结果表明了两种算法的有效性、可行性及与价值密度贪心算法相比的优越性,同时进一步看出两种算法中变化候选算法相
2、对较优,能够取得更好的结果.关键词:背包问题;NP问题;算法;贪心策略;局部搜索中图分类号:TP391文献标识码:A文章编号:1009-7821(2009)05-0066-05Thestudyongreedylocalsearchalgorithmof0-1knapsackproblemLINHong(DepartmentofPhysicsandElectronicsInformationEngineering,MinjiangUniversity,Fuzhou,Fujian350108,China)Abstr
3、act:Inordertoraisetheefficiencyofsolvingfor0-1KnapsackProblem,twokindsofgreedylocalsearchalgorithmof0-1KPareproposed,calledfixedcandidatealgorithmandvaryingcandidatealgo2rithm.Eachalgorithmisusedbyeffectivemethodtoconstructgoodinitialsolution,andthencarriedo
4、utlocalsearchtogainavailability.Theresultofexperimentsshowsthateachalgorithmiseffective,feasibleandpredominantwiththecomparativestandardofvaluedensitygreedyalgorithm.Further,varyingcandi2datealgorithmisrelativelyoptimizedamongthetwoalgorithmsandcanobtainbett
5、erresult.Keywords:knapsackproblem;NPproblem;algorithm;greedystrategy;localsearch背包问题(knapsackproblem,简称KP)是一类在给定约束条件的情况下,求最大值的组合优化问题,是典型的非确定多项式(non2deterministicpolynomial,NP)完全难题.解决该问题无论在理论上,还是在实际中都具有重要的意义.许多实际工程的优化问题都可以归结为背包问题,典型问题有:处理机和数据库在分布式计算机系统上的分配问题、
6、资源分配问题、厂址选择问题、货物装载问题、批量切割问题、项目选择决策问题、削减库存问题等.随着网络技术的不断发展,背包公钥密码在电子商务中的公钥设计中也起着重要的作[1]用.同时,在设计解决大量的复杂组合优化问题算法时,背包问题往往作为子问题出现.背包问题的算法改进,对复杂组合优化问题算法的改良是十分有益的.因此,在近几十年中,KP建模与算法的研究受到广泛的重视,研究前景十分广阔.随着背包问题的发展,产生了许多该问题的变形.其中0-1背包问题是最基础的背包问题,包含了背包问题的最基本思想,其他类型的背包问题往往
7、也可以转换成背包问题求解.1问题描述与数学模型[2]0-1背包问题的一般表述为:给定n个物品和一个背包.物品i的重量是wi,其价值为vi,背包的容量收稿日期:2009-03-10基金项目:闽江学院科技育苗基金项目(YKY08007B)作者简介:林宏(1976-),女,福建闽侯人,闽江学院物理学与电子信息工程系讲师.第5期林宏:0-1背包问题的贪心局部搜索算法研究67为c.问应如何选择装入背包的物品,使得在不超过容量的情况下,所装物品的总价值最大?在选择装入的物品时,对每种物品i只有两种选择,即装入背包或不装入背
8、包,不能将物品i装入背包多次,也不能只装入部分的物品i.0-1背包问题可形式化描述为:给定c>0,c≥wi>0,vi>0,1≤i≤n,要求找出一个n元0-1向量(x1,x2,⋯,xn),xi∈{0,1},1≤i≤n,使Σwixi≤c,并且使Σvixi达到最大.xi=1表示被放入背包,xi=0表示未放入背包.nn数学模型为:max∑vixi,约束条件:∑vixi≤c.i=1i=1从计算复
