本文關(guān)鍵詞：一維捆綁式箱子覆蓋問題

  更多相關(guān)文章： 箱子覆蓋問題 (漸進)近似算法 復(fù)雜性

【摘要】：本論文主要研究一維捆綁式箱子覆蓋問題,它是在一維箱子覆蓋問題的基礎(chǔ)上提出的一類新問題。具體問題描述如下：給定含有n個物品的序列I=(a1,a2,...,an)以及每個物品ai的尺寸s(ai),且s(ai)∈(0,1],這里i=1,2,…,n,提供尺寸為l的K-組裝箱若干,要求把Ⅰ中的所有物品裝入若干K-組裝箱中,目標(biāo)是被覆蓋的K-組裝箱個數(shù)達到最大,這里一個尺寸為l的K-組裝箱是由K個尺寸為l的小箱子捆綁組成,一個K-組裝箱被覆蓋是指該K-組裝箱中每個小箱子都被覆蓋。對于一維捆綁式箱子覆蓋問題,本論文設(shè)計了三個算法來解決該問題,即K-NF算法、K-FFD算法和K-T算法,并證明了它們的漸進近似值分別為2、3/2和2,時間復(fù)雜性分別為O(n)、O(nlogn)和O(n)。
【關(guān)鍵詞】：箱子覆蓋問題 (漸進)近似算法 復(fù)雜性
【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：O224
【目錄】：

• 摘要3-4
• Abstract4-6
• 第一章 引言6-9
• 1.1 理論背景6-7
• 1.2 主要結(jié)果7-8
• 1.3 論文結(jié)構(gòu)8-9
• 第二章 預(yù)備知識9-16
• 2.1 組合最優(yōu)化理論9-11
• 2.2 近似算法理論11-12
• 2.3 相關(guān)術(shù)語12-13
• 2.4 一維箱子覆蓋問題及經(jīng)典算法13-16
• 第三章 一維捆綁式箱子覆蓋問題及其算法設(shè)計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
• 結(jié)論31-32
• 附錄32-38
• 參考文獻38-40
• 致謝40

，

本文編號：1056403