【摘 要】
：
背包问题是组合优化问题中的经典问题之一,该问题经常出现在资源分配中,决策者必须在规定的时间或者预算下,在一组不可分割的物品或者任务中进行选择。背包问题已经被研究了一个多世纪,最早的文献作品可以追溯到1896年。在经典的0-1背包问题中,给定一个容量固定的背包和若干物品,每个物品都有收益属性和重量属性,目标是选出若干物品放入到背包中（每个物品最多只能选择一次）,满足背包中所有物品的重量之和不超过背包
论文部分内容阅读
背包问题是组合优化问题中的经典问题之一,该问题经常出现在资源分配中,决策者必须在规定的时间或者预算下,在一组不可分割的物品或者任务中进行选择。背包问题已经被研究了一个多世纪,最早的文献作品可以追溯到1896年。在经典的0-1背包问题中,给定一个容量固定的背包和若干物品,每个物品都有收益属性和重量属性,目标是选出若干物品放入到背包中（每个物品最多只能选择一次）,满足背包中所有物品的重量之和不超过背包的容量,并且最大化背包中所有物品的收益之和。本文研究的带有冲突图的背包问题是0-1背包问题的扩展,通过一个冲突图,预先定义了物品与物品之间不相容的属性,即存在某些物品不能同时放入到背包中。该问题的目标是在满足背包容量约束和冲突图不相容约束的前提下,选出若干物品放入到背包中（每个物品最多只能选择一次）,最大化背包中所有物品的收益之和。本文在前人的研究基础上,提出了一种新的计算上界的算法。提出的新算法的时间复杂度为O（θn2）,其中θ与输入有关。可以看出这是一个伪多项式时间复杂度的算法。根据文献资料显示,目前最新的算法的时间复杂度为O（n3）,当θ<n时,本文提出的新算法的时间复杂度要低于目前最新的算法。本文将提出的上界算法嵌入到分支定界算法框架中,并进行了大量的数值实验。实验结果表明,对于密度大于或等于0.1的冲突图,在随机实例（物品的收益为随机生成）上,基于新的上界算法的分支定界算法比目前最新的算法平均快1.6458倍;在相关实例（物品的收益与重量相关）上,基于新的上界算法的分支定界算法比目前最新的算法平均快1.6352倍。此外,基于新的上界算法的分支定界算法分别在96.5278%的随机实例上和在92.5694%的相关实例上是最快的。并且,在指定的求解时间内,基于新的上界算法的分支定界算法与目前最新算法相比,可以求解更多的实例。
其他文献
脑肿瘤分为恶性脑肿瘤和良性脑肿瘤,前者是癌性的,容易扩散到大脑的其他部位,后者则不然。然而,在这两种情况下,脑肿瘤在刚性脑部空间的生长都可能导致人体功能障碍,甚至危及生命。脑肿瘤的发病率正在逐年增加,对公共卫生造成了极大的负担。诊断脑肿瘤的主要方法为利用脑部核磁共振成像图（MRI）对脑肿瘤区域进行分割,然而目前对脑肿瘤进行分割仍由脑外科医生手动进行。以这种方式分割需要花费脑外科医生大量的时间进行标
图像语义分割技术是计算机视觉领域中的一项重要的研究内容,在无人驾驶、医学影像、场景理解等领域中都有着不可或缺的作用。近几年随着深度学习的飞速发展,图像语义分割技术的整体性能得到了巨大提升,但深度学习模型对于大规模高精度数据集的依赖也成为了很多算法在泛化性和鲁棒性上的主要瓶颈。高精度的语义标注需要大量的人力和时间成本,如何在短时间内实现准确的数据标注,是图像语义分割技术面临的主要挑战之一。针对这一问
随着科学技术的不断发展,无人机航拍技术被广泛应用到农业、工业、军事等领域。但是受到相机视角的限制,单张航拍图像中所涵盖的内容,无法满足研究人员对信息获取的需要,因此,为了获得大比例尺、信息全面的图像需要对采集的航拍图像进行拼接。针对航拍图像具有易受光照、尺度和旋转等特性变化影响,以及图像不连续、存在视差的特点,本文以特征提取和图像扭曲变形两个阶段为切入点,致力于研究能够适应航拍图像特点的特征提取算
由于司法流程公开与共享的不断推进,我国的司法大数据公开化已趋于成熟,蕴含于法律文书中的丰富法律信息成为了值得深入研究的珍贵资源。但由于法律文书以自然语言形式进行记录,机器难以直接对文档内容进行理解和分析。因此,通过文本挖掘技术对非结构化的司法领域文本进行信息提取和结构化存储,对司法领域信息化发展以及司法效率的进一步提高都具有积极意义和深远影响。文本挖掘中的实体识别和关系抽取技术对于法律文书中关键信
随着软硬件技术的飞速发展,大规模知识图谱的构建和存储成为了可能,并为问答系统、药物发现等人工智能应用提供了知识基础。问答系统作为人工智能领域一项前景广阔的落地应用受到人们的广泛关注。与通过搜索引擎获取知识的方式相比,问答系统能更加智能和高效地给出确切的答案。基于知识图谱的问答系统（Knowledge Based Question Answering,KBQA）结合二者的优势,将用户的查询解析为逻辑
随着信息时代的到来,人们在网上获取知识的渴望越来越高。传统的基于搜索引擎的信息检索方式会返回大量与问题相关的网页,这不仅对网页的排序准确率有较高的要求,还需要人工的去点击链接筛选信息,这无疑会耗费一定时间。因此,问答系统应运而生。问答系统可以直接理解用户的问题,返回简洁正确的答案,降低用户查询成本。知识图谱是一种新型的数据库,可以看作是巨大的语义关系网,表示客观世界实体之间的关系,其以图结构存储知
汽车工业和计算机深度学习等技术的进步使无人驾驶汽车（Automatic Vehicle,AV）逐渐成为一种不可替代的交通方式。自主代客泊车（Autonomous Valet Parking,AVP）功能作为无人驾驶汽车的重要功能之一,使汽车能自主完成导航和泊车任务。在自主代客泊车领域,分为短程自主代客泊车（Short-range Autonomous Valet Parking,SAVP）和远程自
当前是一个信息爆炸的时代,人们都在创作或者接受各种各样的文本资讯。让机器学会生成文本在一定程度可以避免人们机械重复的信息生产过程,在提高效率的同时还可以为人类创作提供灵感或者辅助。文本的内容通常会围绕特定的主题进行展开,如果文本内容松散,缺乏明确的主题,文本可读性就会下降。当前的许多文本生成研究也较少对于主题信息进行建模研究,因此,本文主要探究融合主题信息的文本生成技术。首先,本文对主题模型的主题
幽默是人类交流中一种独特的表达方式,它能够创造轻松愉快的氛围,促进人与人之间的沟通。幽默饱含智慧与创造力,研究幽默的产生机理,使用计算机对幽默建模,识别和生成幽默有助于计算机模拟人类的认知,对人工智能的发展至关重要。近年来已有许多基于文本的幽默识别研究,但是随着社交媒体的发展,幽默识别的对象不再局限于文本,音频、视频等多模态信息中也包含着丰富的幽默。多模态幽默识别成为该领域新兴的研究课题,它需要挖
高维、复杂的生物数据中潜藏着大量与生命健康密切相关的信息,生物数据往往具有样本量小、维数高的特点,因此如何对其进行有效降维并提取重要信息,对疾病诊断、药物研发、个性化医疗等具有重要意义。由于生物体自身的复杂性导致分子间存在错综复杂的交互作用,对此,本文分别从特征选择与特征提取两个角度出发,利用分子间的关联关系从复杂的生物数据中提取出具有重要意义的信息,具体研究内容如下:1.提出了基于协同作用网络的