背包問題是一類經(jīng)典的組合優(yōu)化問題,它不僅是計(jì)算機(jī)科學(xué)中很多算法的重要組成部分,更是在商業(yè)、組合數(shù)學(xué)、計(jì)算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中有著重要應(yīng)用。背包問題的模型是已知一個(gè)固定容量的背包,以及一系列物品,每個(gè)物品有自己的尺寸和權(quán)重,目標(biāo)是在不超過背包容量的前提下,使裝入背包中的物品的總收益（權(quán)重）最大。經(jīng)典的背包問題為離線問題,即在最開始已知所有物品的信息。與離線所對(duì)應(yīng)的即為本文研究的在線背包問題,即物品是按照一定順序一個(gè)接著一個(gè)到來的,在決定當(dāng)前物品去留之前,無法知道未來物品的信息。對(duì)于在線背包問題,前人已經(jīng)做了一定的研究,并取得一定成果,例如線性函數(shù)下在線背包問題以及凸函數(shù)下在線背包問題,但是在此之前沒有人研究凹函數(shù)下在線背包問題。本文研究的主要內(nèi)容是物品的大小和權(quán)重之間滿足凹函數(shù)關(guān)系的在線背包問題,因?yàn)槭俏锲返膶傩灾g存在的函數(shù)關(guān)系,所以該模型下的在線背包問題并不是相應(yīng)凸函數(shù)問題的簡(jiǎn)單翻轉(zhuǎn),也無法用凸函數(shù)模型下的在線算法解決該模型下的問題。而在此之前沒有人研究過凹函數(shù)下的在線背包問題,同時(shí)這一類問題在很多領(lǐng)域中有重要應(yīng)用。本文主要工作是通過學(xué)習(xí)和研究其他類型背包問題,并結(jié)合... 

【文章來源】：大連理工大學(xué)遼寧省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：57 頁

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 背景
    1.2 中外研究現(xiàn)狀
    1.3 研究凹函數(shù)下在線背包問題的意義
    1.4 論文結(jié)構(gòu)
2 背景知識(shí)
    2.1 背包問題相關(guān)背景知識(shí)
        2.1.1 經(jīng)典背包問題
        2.1.2 在線背包問題
    2.2 在線問題相關(guān)背景知識(shí)
        2.2.1 競(jìng)爭(zhēng)分析
        2.2.2 競(jìng)爭(zhēng)比
    2.3 凹函數(shù)相關(guān)背景知識(shí)
    2.4 本章小結(jié)
3 凹函數(shù)模型下競(jìng)爭(zhēng)比下界
    3.1 一般情況的下界
    3.2 特殊情況的下界
    3.3 本章小結(jié)
4 凹函數(shù)模型下的在線算法
    4.1 競(jìng)爭(zhēng)比為f'(0)/f(1/q)的在線算法
    4.2 競(jìng)爭(zhēng)比為f'(0)/f(1)+1的在線算法
    4.3 分段線性實(shí)例的競(jìng)爭(zhēng)比
    4.4 本章小結(jié)
5 背包問題以及在線背包問題的應(yīng)用
    5.1 背包問題在最短路徑、VRP、定向問題中的應(yīng)用
        5.1.1 背包與帶有資源約束的基礎(chǔ)最短路徑問題
        5.1.2 背包問題與VRP問題
        5.1.3 背包與定向問題
    5.2 凹函數(shù)下的在線背包問題在經(jīng)濟(jì)學(xué)中的應(yīng)用
        5.2.1 效用
        5.2.2 在線背包與效用最大化
    5.3 凹函數(shù)下的在線背包問題在廣告投放中的應(yīng)用
        5.3.1 查詢競(jìng)價(jià)
        5.3.2 關(guān)鍵字拍賣
    5.4 本章小結(jié)
結(jié)論
參考文獻(xiàn)
攻讀碩士學(xué)位期間發(fā)表學(xué)術(shù)論文情況
致謝



本文編號(hào)：3193542