一维捆绑式箱子覆盖问题

发布时间：2017-10-18 18:15

  本文关键词：一维捆绑式箱子覆盖问题

  更多相关文章： 箱子覆盖问题 (渐进)近似算法 复杂性

【摘要】：本论文主要研究一维捆绑式箱子覆盖问题,它是在一维箱子覆盖问题的基础上提出的一类新问题。具体问题描述如下：给定含有n个物品的序列I=(a1,a2,...,an)以及每个物品ai的尺寸s(ai),且s(ai)∈(0,1],这里i=1,2,…,n,提供尺寸为l的K-组装箱若干,要求把Ⅰ中的所有物品装入若干K-组装箱中,目标是被覆盖的K-组装箱个数达到最大,这里一个尺寸为l的K-组装箱是由K个尺寸为l的小箱子捆绑组成,一个K-组装箱被覆盖是指该K-组装箱中每个小箱子都被覆盖。对于一维捆绑式箱子覆盖问题,本论文设计了三个算法来解决该问题,即K-NF算法、K-FFD算法和K-T算法,并证明了它们的渐进近似值分别为2、3/2和2,时间复杂性分别为O(n)、O(nlogn)和O(n)。
【关键词】：箱子覆盖问题 (渐进)近似算法 复杂性
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O224
【目录】：

• 摘要3-4
• Abstract4-6
• 第一章 引言6-9
• 1.1 理论背景6-7
• 1.2 主要结果7-8
• 1.3 论文结构8-9
• 第二章 预备知识9-16
• 2.1 组合最优化理论9-11
• 2.2 近似算法理论11-12
• 2.3 相关术语12-13
• 2.4 一维箱子覆盖问题及经典算法13-16
• 第三章 一维捆绑式箱子覆盖问题及其算法设计16-31
• 3.1 问题描述16
• 3.2 K-NF算法16-19
• 3.3 K-FFD算法19-24
• 3.4 K-T算法24-28
• 3.5 算例28-31
• 结论31-32
• 附录32-38
• 参考文献38-40
• 致谢40

，

本文编号：1056403