【摘 要】
:
背包问题是经典的NP hard组合优化问题之一 ,由于其难解性 ,该问题在信息密码学和数论研究中具有极重要的应用 基于求解背包问题著名的二表算法和动态二表算法 ,利用归并原理
【机 构】
:
华中科技大学计算机科学与技术学院,华中科技大学计算机科学与技术学院,湖南大学计算机科学与通讯学院
【基金项目】
:
国家自然科学基金项目 ( 60 2 73 0 75 ) ;国家“八六三”高技术研究发展计划基金项目 ( 863 3 0 6ZD 11 0 1 0 6)
论文部分内容阅读
背包问题是经典的NP hard组合优化问题之一 ,由于其难解性 ,该问题在信息密码学和数论研究中具有极重要的应用 基于求解背包问题著名的二表算法和动态二表算法 ,利用归并原理和 4个非平衡的子表 ,提出一种求解该问题的自适应算法 ,算法可根据计算资源和问题实例规模的大小 ,允许使用O (2 n/ 2 -ε)的存储空间 (1≤ε≤n/ 4 ) ,在O(ε(2 n/ 2 ) )的时间内求解背包问题 对算法性能的理论分析和数值实验结果表明 ,自适应算法可显著扩大背包实例的求解规模 ,从时间和空间上改进背包问题现有算法的性能
其他文献
采用自制相控阵超声探头对薄板铝合金搅拌摩擦焊接头进行无损检测,通过金相试验分析,验证焊接接头存在隧道、孔洞和未焊透等典型缺陷。结果表明,自制相控阵超声探头能较好地
由 Si O2 胶体颗粒的三维有序自组装可以得到面心立方三维结构 ,它具有折射率周期性变化的特点。它的制备涉及胶体化学、材料科学等学科的前沿领域。其自组装方法包括胶体颗
在城市建设过程中排水系统规划占有重要地位,直接影响了城市基础设施的应用。随着我国城市和乡村的快速发展,城乡统筹建设速度逐渐加快,在城乡建设过程中排水系统占有重要地
针对城市基础设施建设中遇到的融资困境问题,以ABS融资、PPP融资以及BOT融资三种创新融资模式的分析为基础,通过对融资成本、融资风险、融资范围、融资能力、以及产生的社会
马克思关于人的自由而全面发展的理论是马克思主义理论的核心和灵魂。自由是人的本性、本质得以确证、肯定、实现的状态。人的类特性得以实现的自由活动是物质生产劳动,但物质
老视是一种正常的生理现象,我们眼睛在年轻的时候,调节力非常强,这样可以保证我们轻松地看清远近不同的物体。随着年龄的增长,眼睛的调节力逐渐下降,视近出现模糊,这时就需要
政局新动向和人文新因素使明清之际士人质疑和救治了传统政治秩序,其主要成果集中在《明夷待访录》和《天下郡国利病书》。《明夷待访录》通过历史理性探讨皇权专制中君臣的权
论文一改良腹腔镜腹膜阴道成形术的临床研究中文摘要目的:分析改良腹腔镜腹膜阴道成形术的手术技巧和围手术期的管理,评估其可行性、有效性、实用性,以探讨其临床应用价值。方
电机作为重要的电气设备广泛应用于生产制造及运输等领域。滚动轴承是电机中重要的组成部件,其运行状态直接影响电机,甚至整个系统的性能。电机轴承内外圈相对旋转并且承受径