资源描述：
《广义多维多选择背包问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第26卷第9期贵州师范学院学报Vo.l26.No.92010年9月JournalofGuizhouNormalCollegeSep.2010*广义多维多选择背包问题12吴刚,赖志柱(毕节学院数学系,贵州毕节551700)摘要:在分析多维背包问题和多选择背包问题的基础上,提出一种广义的多维多选择背包问题,给出了该问题的数学模型并改进传统的贪婪算法对其进行了求解。该算法以价值密度为准则,并对每个约束条件先后执行贪婪优化,从而得到问题的近似最优解。关键词:背包问题;贪婪算法;多维多选择背包中图分类号:TP301.6文献
2、标识码:A文章编号:1674-7798(2010)09-0017-03Onthegeneralizedmultidimensionandmultiple-choiceofknapsack12WUGang,LAIZhi-zhu(DepartmentofMathematics,BijieCollege,Bijie,Guizhou,551700China)Abstract:Basedontheanalysisofthemultidimensionalknapsackproblemandthemultiple-choiceknapsackprobl
3、em,theGeneralizedMultidimensionalMultiple-choiceKnapsackProblem(GMMKP)anditsmathematicalmodelandimprovedgreedyalgorithmforthesolutionareproposed.Thealgorithmisbasedonthevaluedensitycrite-riaandhasexecutedthegreedysearchfromoneconstrainttoanotherconstraint,henceweobtaintheapp
4、roximateop-timalsolution.Keywords:KnapsackProblem;greedyalgorithm;multidimensionalknapsackproblem有若干不同的项目。0引言多约束背包问题也称为多维背包问题(mult-i0-1背包问题是一类典型的组合优化问题,dimensionalknapsackproblem)或多背包问题它要求找出n个物体的一个子集使其尽可能地装(multiple-knapsackproblem),它是带有一组约[1,2]满容量为W的背包。它本质上是一个只有一个束(比如重量、
5、尺寸、可靠性等)的背包问题。约束条件(容量约束)的0-1规划问题,在计算该问题可以简单描述为n个物品要放入m个承理论上属于NP一完全问题,其计算的复杂性为重不同的背包,它与0-1背包问题不同的是,物nO(2)。随着该问题的发展,又产生了许多该问品放入不同背包的重量是不同的。显然,在多约题的变形,比如多选择背包问题(multiple-choice束背包向题中,除了确定每个物体是否被装入背knapsackproblem)、有界背包问题(boundedknap-包之外,还需要确定它将被装入哪个背包,显然对sackproblem)、无界背包问题(unb
6、oundedknap-于多背包问题的优化会比0-1背包问题复杂得sackproblem)和多约束背包问题(multiple-con-多。目前文献中已经针对这个NP难问题提出了[1]strainedknapsackproblem)。各种算法,如Raidl开发的改进遗传算法和虞[3]多选择背包问题定义为有附加约束的背包问安波等提出的改进遗传算法等。[1]题,该问题带有互不相关的多选择约束。该问多维多选择背包问题(MultidimensionalMu-l题的特点是只有一个承重有限的背包,将要放入tiple-choiceKnapsackProblem,
7、MMKP)是一类特背包的物品被分为相互排斥的若干类,而每类中殊的0-1背包问题,问题的描述如下:存在m个*收稿日期:2010-07-10作者简介:1吴刚(1966-),男,贵州纳雍人,毕节学院数学系教师,主要研究方向为多媒体教学,算法设计与优化。2赖志柱(1980-),男,江西赣州人,毕节学院数学系教师,主要研究方向为自然计算,算法设计与优化。17背包,其承重分别为Wk(k=1,2,,m)和n类xij{0,1}(i=1,2,,n.j=1,2,,li)物品,每类物品又分别有li(i=1,2,,n)个物模型中的第一个约束条件表
8、示m个背包的品,其价值分别为vij(j=1,2,,li),而对每一个承重约束,第二个约束条件表示第i类物品中装物品,由于其装入的背包不同而其重量(或
