【摘 要】
：
在Max-sum形式的多重背包问题的基础上，研究了最小效益尽可能大的多重背包问题。我们得到了如下的结果；（1）通过三划分问题的归约证明了即使所有背包的容量均相同，该问题是强NP-难
论文部分内容阅读
在Max-sum形式的多重背包问题的基础上，研究了最小效益尽可能大的多重背包问题。我们得到了如下的结果；（1）通过三划分问题的归约证明了即使所有背包的容量均相同，该问题是强NP-难的，并且对（）>0，不存在近似值为2/3+ε的近似算法，除非P=NP；（2）当所有物品的效益均为1,以及所有背包的容量均相等时，给出了与最优值至多差1的两个近似算法，其时间复杂度均为（）（nlog2n）；（3）当背包的容量不相等，且所有物品的效益均为1时，设计了两种情形下的两个启发式算法，算法的时间复杂度均为（）（nlog2n）。
其他文献
Weibull分布是可靠性理论与生存分析中应用最广泛的产品寿命分布之一，本文主要介绍不同情况下对双参数Weibull分布的参数估计，着重引进在完全数据下对其尺度参数的改进后的MLE
本文目的是研究指数Diophantine方程nx+(3n2-1)y=(4n2-1)z的解和解数问题。全文共分二章。第一章为综述,介绍了指数Diophantine方程的研究意义、目的和国内外研究的背景和现
智能算法由于其操作简单,易于实现的良好特性,被广泛应用到现实生活的各个领域,并且在解决复杂的全局优化问题方面已经取得了成功,相对于传统的优化算法,智能算法得到了广泛
作为数学规划研究中的热点之一，互补问题在工程设计、经济均衡、运输问题和博弈论等诸多方面有着十分重要的应用。在实际问题中，一些条件通常受到诸如天气、路况、需求等不确定
对于给定的正整数s与m，关于路的Ramsey-Schur数PRS(s，m)指具有下述性质的最小正整数n：对于完全图Kn的任意一个2着色(绿，红)，要么包含一条绿色的有s+1个顶点的路P8，要么包含一些顶点
本文研究奇点指数理论在Fano流形上Kahler-Einstein度量存在性问题中的应用。特别地，我们将研究田刚教授在一系列文章（[39]，[40]，[41]和[42]）中所定义的α-不变量，αm-不变量，以及α
随着如今时代的发展与教育理念的不断更新,更为符合社会发展规律与人们的个人发展需求的终身学习意识,在慢慢的得到一个深化.在体育教学方面,我们开始提倡培养一种终身体育的
近年来,混合效应状态空间模型在稀疏纵向数据下的研究,已经引起了来自不同领域的研究人员的关注.状态空间模型是一个基于动态数据的时域分析模型,以时间为独立变量,是时间序
设Γ为一个图，Aut（Γ）为Γ的全体自同构群。如果存在X≤Aut（Γ）使得X在Γ的边集EΓ上传递，则称Γ为X-边传递图。设G为一个群，一个图Γ称为群G上的Cayley图，如果存在G的一个非空子集S，
将信息技术与高中数学课程进行整合是教学发展的必然趋势,其主要就是把以信息技术为中心的各种资源同高中数学课程内容结合在一起的新型教学方法,该方法的优点就在于,可以为