【摘 要】
：
0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究.研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差.虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可以找到问题的最优解.针对这些问题,提出一种融合贪心策略和剪枝策略的新型回溯算法.该算法将贪心算法得到的问题近似解用于剪枝策略的判断条件中,并在物品取舍时将当前的物品重量与背包的剩余容量进行比
【机 构】
：
现代教学技术教育部重点实验室,陕西 西安 710062;陕西省教学信息技术工程实验室,陕西 西安 710119;陕西师范大学 计算机科学学院,陕西 西安 710119
论文部分内容阅读
0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究.研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差.虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可以找到问题的最优解.针对这些问题,提出一种融合贪心策略和剪枝策略的新型回溯算法.该算法将贪心算法得到的问题近似解用于剪枝策略的判断条件中,并在物品取舍时将当前的物品重量与背包的剩余容量进行比较,以避免重复计算,减少迭代次数,提高算法的执行效率.大量的仿真实验结果表明,在一定问题规模下,与经典回溯算法相比,所提出的新型回溯算法仍能够在短时间内准确找到问题的最优解,且具有更高的执行效率.
其他文献
公司简介rn虎丘影像(苏州)股份有限公司,是一家专注于各类影像输出设备、耗材以及医疗影像信息化产品研发与生产的科技型公司,主营产品包含医用热敏胶片及医用胶片打印机,大幅面热敏工程图文打印机及打印耗材等,公司是国内医学影像和文化办公设备行业细分领域的头部企业.
台玻天津为北京冬奥会场馆提供高性能玻璃rn北京冬奥会期间,国家速滑馆成了新地标,因其外墙曲面由低到高盘旋成22条飘逸的丝带,宛如运动员在冰上划过的痕迹,因此又得昵称“冰丝带”.而环绕“冰丝带”幕墙所使用的3360块曲面玻璃原片,正是台玻天津玻璃有限公司生产的镀膜大板玻璃.
2021年是“十四五”规划开局之年,也是我国迈向第二个百年奋斗目标的新起点.面对复杂多变的国内外经济形势,机械工业全行业认真贯彻落实党中央国务院的决策部署,抢抓市场机遇、应对风险挑战,克服各种困难,经济运行稳定恢复,“十四五”开局迈出新的步伐.
随着教育越来越走向信息化,大量的教育数据会被保存,在海量教育数据中挖掘出学生的潜在信息是智能教育中非常值得研究的问题之一.针对目前大多数得分预测都是预测一个总分,无法具体到每一题得分预测的问题,对考试中存在的主要题型进行了研究,结合现有试题得分预测方法,指出其优势与不足,提出基于认知诊断和神经网络分别预测客观题和主观题得分的方法.该方法结合认知诊断理论计算出学生的知识状态,通过矩阵算法来预测学生在每道客观题上的得分,再将学生的知识状态作为特征,学生得分作为训练标签,使用卷积神经网络来训练并且预测学生在每道
色彩问题,是绝大多数企业常见的痛.色彩管理,可以说是印刷包装企业的刚需.最近不少朋友咨询,我们上了CIP3连线预放墨技术之后,是不是就万事大吉了?安装相关软硬件之后,只要简单调整出版补偿和放墨曲线,就能确保印刷效果?
绪论rn现实生活中有这样一个群体,他们的世界是一片漆黑,看不见世界的美丽,他们是盲人.最新的人口普查数据显示:中国是全世界盲人最多的国家之一,眼部疾病在中国也是一个主要的公共卫生问题.经不完全的数据统计,我国现有盲人1700万,占世界盲人总数的18％～20％,每年新增的盲人数量高达45万.这意味着,在我国每71个人中,就有1个盲人.
引言rn印刷电子技术是将传统印刷工艺应用于制造电子器件产品的新兴工艺,其大面积、成本低、柔性化、绿色环保的特点在电子器件制造领域广受关注,市场前景广阔.早期的传统材料已无法满足当前印刷电子产品的发展需求,而新兴材料如石墨烯、碳纳米管的出现,为印刷电子技术的发展提供了新的可能.印刷电子技术仅需要印刷和干燥烧结两步工艺.其关键技术也只有两步,一是制备各种功能性墨水,二是采取适当的印刷方式将特定的功能性油墨印刷在不同种类的基底材料上.利用印刷电子技术制备的电子器件如压力传感器、柔性超级电容器等,广泛应用于医疗能
根据Smithers最新的独家市场研究,新兴市场对更多可回收包装的需求和新需求将有助于推动饮料罐和其他金属包装迎来更大的发展.rn由于全球大流行,自2019年以来,金属包装发展取得了显著进展.2020～2021年期间,全球销量增加了107亿美元,原因是食品易拉罐销量强劲,饮料罐销量持续增长.这足以弥补非消费业态的损失,这些业态包括工业散装集装箱、工业桶和桶装桶,由于石油和其他大宗商品的需求暂时下降,这些业态受到船运量减少的影响.
为了利用单目视觉实时监测船舶行驶过程中与周围船舶之间的距离,首先分析单目视觉测距现状及其成功应用实例,基于小孔成像原理建立单目相机模型,通过几何推导,得到世界坐标系、相机坐标系、图像坐标系及像素坐标系之间三层坐标转换关系.随后通过实验验证pitch俯仰角与yaw水平角对单目视觉测距的影响程度,从而分析出动态船舶行驶场景下包括相机姿态、船舶在水面摇晃等实时单目测距误差.进而在引入包含俯仰角、水平角的相似三角形测距算法的基础上,采用高精度陀螺仪相机姿态补偿策略提出改进的基于单目视觉的相似三角形目标船舶测距算法
本地差分隐私(local differential privacy,LDP)可以对可穿戴装置(wearable devices)采集到的数据进行隐私保护,每个用户都会在本地扰乱自己的数据,并且将扰动后的数据发送给数据汇聚服务器,以保护用户免受私人信息泄漏的影响.可穿戴装置采集到的数据是多维的,但是现有的针对可穿戴装置多维数据的个性化本地差分隐私保护研究比较少而且不完善.针对现有个性化本地隐私方案存在的最坏情况下噪声方差大的问题,采用结合机制,结合随机响应机制和分段机制,对数值型数据进行扰动,提出了一种处理