【doc】基于贪婪策略的0／1背包问题算法研究.doc

基于贪婪策略的0／1背包问题算法研究2007计算机与现代化JISUANJIYUXIANDAIHUA总第140文章编号:1006-2475(2007)04-0010-03基于贪婪策略的0/1背包问题算法研究(厦门大学计算机科学系,福建厦门361005)摘要:对求解0/1背包问题的贪婪策略进行了详细的讨论。在分析价值密度贪婪算法缺陷的基础上,提出了重做贪婪选择的改进算法,并从理论和实验两个方面证明了其求解质量的提高。本文还详细分阶优化算法,并证明了其近似比为k/(k+1),最后编程模拟了该算法的实现过程,并对结果进行了分析。关键词:0/1背包问题;贪婪策略;k阶优化算法;近似比中图分类号:TP301。6文献标识码:AStudyofGreedy--policy--basedAlgorithmfor0/1KnapsackProblemYOUWei(ComputerScienceDepartment,XiamenUniversity,Xiamen361005,China)Abstract:Thispaperdiscussesgreedy-policy-basedalgorithinfor0/1KnapsackProblemindetail。

Afteranalyzingthedefectofthevaluedensitygreedyalgorithm,thepaperproposesanimprovedalgorithmwhichrepeatsthegreedyselection。Theavailabilityoftheimprovedmethodisprovedbyboththeoryandexperiments。Thek-orderoptimizationalgorithmisalsoanalysedindetail。Thepaperalsoprovesthattheratiooftheapproximatesolutionandoptimalsolutionisk/(k+1)andimplementsthisalgorithin。Keywords:O/1knapsackproblem;greedypolicy;k-orderoptimizationalgorithm;approximateratio引言的整数规划问题:背包问题属于NP完全问题,直接的枚举搜索可能遍历问题的所有2"个解空间,即最坏情况下的时间复杂性为0(2")。

因此,设计算法来降低求解该问题过于庞大的计算量,具有重要的理论和实际意0/1背包问题的一般表述为:给定n个物品和一个背包。物品i的重量是w,其价值为vi,背包的容量为c。假定有wc,(1in)。问应如何选择装入背包的物品,使得在不超过容量的情况下,所装物品的总价值最大l3?背包问题可形式化描述为:给定c>0,W>0,>0,1in,要求找出一个n元0/1向量(l,2,,),{o,1),1in,使lc,并且两使芝v-x_达到最大。因此,0/1背包问题是一个特殊max。wixil1