【摘 要】
：
本文对一维装箱问题进行了推广,提出了一个新的问题,称为一维捆绑式装箱问题。一维捆绑式装箱问题的具体描述如下：给定n个物品的序列I=(a1,a2,...,an),每个物品尺寸为s(ai)∈(
论文部分内容阅读
本文对一维装箱问题进行了推广,提出了一个新的问题,称为一维捆绑式装箱问题。一维捆绑式装箱问题的具体描述如下：给定n个物品的序列I=(a1,a2,...,an),每个物品尺寸为s(ai)∈(0,l],这里i=1,2,...,n,提供若干个K-组装箱,把I中的物品装入若干个K-组装箱中,要求每个小箱子所装物品的尺寸之和不超过l,目标是使得所使用的K-组装箱的数目达到最小,其中一个K-组装箱由K个尺寸为l的箱子捆绑组成,K-组装箱的尺寸为l。为了解决一维捆绑式装箱问题,本文设计了K-NF算法、]K-FFD算法和K-SFOF算法三个离线算法,其中K-NF算法的近似值为2,复杂性为O(n)；K-FFD算法和K-SFOF算法的渐进近似值都为3/2,时间复杂性分别为O(n2)和O(n)。同时本文设计一个在线渐进近似算法-K-SFON算法,该算法的渐进近似值为7/4,时间复杂性为O(n)。
其他文献
针对向家坝水电站大坝混凝土浇筑施工工程量大、工期长、设备多、关系复杂等特点以及提高施工管理与决策科学性和效率的现实需求出发,以虚拟现实和人工智能领域的知识工程为
浙商作为改革开放以来的中国大地快速崛起的代表性商帮,造就了“浙江奇迹”的出现。从中国伦理文化与浙商兴起的关联分析,浙商的崛起及浙江经济繁荣发展的背后,源起于浙江的
本文是观摩了全国第四届高中物理名师赛之后,对魏华老师执教的《伽利略对自由落体运动的研究》进行赏析,以期更好地学习、借鉴名师的课堂教学艺术.
<正>初看"断舍离"三个字,是一组听起来有点奇怪的字眼吧?这是什么?又能做些什么?如果,要非常简洁明快地回答这个问题,"断舍离"就是"通过舍弃、整理物品,将心中无用之物整理得
总结了国外关于事故数据记录仪数据的3个标准或法规,解读了事故数据记录仪记录的非点爆事件和点爆事件2类事件。整理了常见的42个数据,分析了车速、发动机转速、节气门开度及
以摄像头采集的视频图像为输入,以ADSP-BF609微处理器为运算处理核心,详细描述了汽车前向防撞主动安全辅助系统的硬件平台架构和各个模块电路设计,并研制了样机。实验表明,电