论文部分内容阅读
背包问题是组合最优化理论研究中的一个经典问题,也是一个重要问题。近些年,背包问题及其各种变形与推广问题都是研究热点。经典背包问题及其推广形式都是NP-难的,它们在存储空间的分配、项目选择以及下料等实际问题上有很好的应用。本文研究了背包问题的几类变形问题,并且设计出了解决相应问题的一些近似算法或者最优算法。全文分为七章内容：在第一章中,介绍了图论与运筹学的一些相关背景、背包问题,以及本文得到的主要研究成果。在第二章中,介绍了图论、组合最优化的相关概念和几类相关的优化问题。在第三章中,介绍了匹配的一些基本知识,特别是介绍了匈牙利算法的基本思想方法。对于一般图的最优k匹配问题,设计了一个时间复杂性是O(n3)的最优算法,这里n为图中顶点数。在第四章中,研究了k元素限制的广义多重背包问题(简记为k-GMK),根据所求目标形式不同,分别研究了Max-Sum k-GMK问题以及Max-Min k-GMK问题。两个问题都是NP-难的,对于Max-Sum k-GMK问题(k≥4),设计了一个1/2-近似算法,对于Max-Min k-GMK问题(k≥4)设计了一个1/(k-1)-近似算法。当k=2时,我们分别给出了时间复杂性是O(n4)和O(n1/2m2)的最优算法来解决这两个问题,这里n为物品数量,m为背包数量。在第五章中,研究了限制在图上的多重背包问题(简记为k-MKRG)。根据目标形式不同,分别研究了Max-Sum k-MKRG问题和Max-Min k-MKRG问题。k-MKRG问题(k≥2)在上述两种目标下都是NP-难的,当k=2时,对于这两个问题,我们分别设计了1/2-近似算法。在第六章中,考虑了在背包容量一致情况下的k-MKRG问题,称为统一背包限制问题(简记为k-UKRG)。根据目标形式不同,分别研究了Max-Sum k-UKRG问题和Max-Min k-UKRG问题,证明了它们都是NP-难的。对于Max-Sum 3-UKRG问题和Max-Min 3-UKRG问题均设计了2/3-近似算法。对于Max-Sum 2-UKRG问题与Max-Min 2-UKRG问题,分别设计了时间复杂性为O(n3)和O(n(|E|+n log n) log n)的最优算法,这里n为物品数量,E为限制图的边集。在第七章,总结了全文,并对未来工作进行了展望。