【正文】 then inc(c[j+now],a[j])。 a:=c。 end[9]。 20 3 解 01 背包問題的算法比較與分析 這 四 種算法都得到 了 驗(yàn)證，運(yùn)行結(jié)果證明了算法設(shè)計(jì)是可行的，正確的。通過對 O1 背包問題的算法設(shè)計(jì)及時(shí)間復(fù)雜度分析可以看出 。 無論采用貪婪法還是動(dòng)態(tài)規(guī)劃法，都是在已知約束條件下求解最大值建立數(shù)學(xué)模型算法實(shí)現(xiàn)的過程；但算法具體實(shí)現(xiàn)和數(shù)據(jù)結(jié)構(gòu)的建立要用到遞歸和棧操作。比較貪婪法和動(dòng)態(tài)規(guī)劃法。前者的時(shí)間復(fù)雜度低于后者，從耗 費(fèi)上而言優(yōu)于后者。但后者的實(shí)現(xiàn)算法可讀性要優(yōu)于前者。 動(dòng)態(tài)規(guī)劃算法的基本思想是把原問題分解為一系列子問題，然后從這些子問題中求出原問題的解?；厮萜鋵?shí)就是窮舉，窮舉所有的解，找出解中最優(yōu)的值?；厮莘ㄔ诎瑔栴}的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。回溯法的基本思路是：確定解空間，建立解空間樹，用深度優(yōu)先搜索算法遞歸搜索解空間樹，并同時(shí)注意剪枝 ,常用的分枝一限界法有最小耗費(fèi)法，最大收益法 。 FIFO(先進(jìn)先出 )法等。 01背包問題的分枝一限界算法可以使用最大收益算法。該算法跟回溯法類似 。但分枝限界法需要 O( n2 )的解空間。故該算法不常用在背包問題求解。 遺傳算法 是計(jì)算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法 ，是一種進(jìn)化算法。 對于一個(gè)最優(yōu)化問題，一定數(shù)量的候選解（稱為個(gè)體）的抽象表示（稱為染色體）的種群向更好的解進(jìn)化。 通常解用二進(jìn)制 0 和 1 表示，進(jìn)化從一個(gè)個(gè)體發(fā)生，然后一代一代發(fā)生。在每 一代中，該種群的價(jià)值被評估，從當(dāng)前種群中隨機(jī)地選擇多個(gè)個(gè)體（基于它們的適應(yīng)度），通過自然選擇 。 回溯法比分枝限界在占用內(nèi)存方面具有優(yōu)勢。回溯法占用的內(nèi)存是 0(解空間的最大路徑長度 )，而分枝限界所占用的內(nèi)存為 0(解空間大小 )。對于一個(gè)子集空間，回溯法需要 0(n)的內(nèi)存空間，而分枝限界則需要 0(2n)的空間。雖然最大收益或最小耗費(fèi)分枝限界在直覺上要好于回溯法，并且在許多情況下可能會比回溯法檢查更少的結(jié)點(diǎn)，但在實(shí)際應(yīng)用中，它可能會在回溯法超出允許的時(shí)間限制之前就超出了內(nèi)存的限制。 為了更直觀更有效地分析動(dòng)態(tài)規(guī)劃法 回溯 法兩 種算法，下面分別對它們的計(jì)算時(shí)間進(jìn)行測試。測試中 ,每個(gè) 01 背包問題的效益和重量分別為隨機(jī)產(chǎn)生的兩組數(shù)據(jù) ,其取值范圍為 [0,999],背包容量定為 1125。為便于各算法間進(jìn)行比較，測試之前首先把物品按價(jià)值重量比的非增順序排序。每次測試將程序運(yùn)行 100 21 次所得時(shí)間為運(yùn)行 100 次的平均值。測試結(jié)果如下表所示 [18]。 問題規(guī)模 平均計(jì)算時(shí)間 動(dòng)態(tài)規(guī)劃法 回溯法 5 10 15 20 25 50 100 200 從表中的測試結(jié)果可以看出 當(dāng)問題規(guī)模較小時(shí)，三種方法都有較好的穩(wěn)定性， 計(jì)算時(shí)間都相差不多。隨著問題規(guī)模的增大，各算法的計(jì)算時(shí)間都在增大， 其中遞歸法的計(jì)算時(shí)間增長速度最快，當(dāng)問題規(guī)模為 50， 100 和 200時(shí)，其計(jì)算時(shí)間太長以致失去利用該法求解的意義，而動(dòng)態(tài)規(guī)劃法與回溯法則相對穩(wěn)定且計(jì)算時(shí)間也相 差不多，但是當(dāng)問題規(guī)模大到一定程度，回溯法要優(yōu)于動(dòng)態(tài)規(guī)劃法。 通過以上對 01背包問題的求解分析，我們可以看到各種算法設(shè)計(jì)方法有各內(nèi)不同的特點(diǎn)，針對不同的問題領(lǐng)域，它們有不同的效率，對于求解 01背包問題，各算法的時(shí)問復(fù)雜度、優(yōu)缺點(diǎn)以及改進(jìn)方法的比較如下表所示 [19]: 動(dòng)態(tài)規(guī)劃 O(min{nc, n2 }） 可求得最優(yōu)決 策序列 速度較慢 建立動(dòng)態(tài)規(guī)劃 遞歸方程 回溯法 O(n n2 ） 能夠獲得最優(yōu) 解 時(shí)間復(fù)雜度較 高 判斷右子樹時(shí)，按效率密度 vi/wi 對剩余對象排序 分枝 限界法 O( n2 ） 速度較快，易求解 占用的內(nèi)存較大，效率不高 最大收益或最小消耗分枝 限界法， FIFO法 遺傳算法 O(n n2 ） 能夠解決傳統(tǒng)算法不能解決的問題，能夠獲得最優(yōu)解 速度較慢，算法不成熟 基于懲罰函數(shù)修正方法和譯碼方法 22 4 總結(jié)與展望 本文就 回溯法 ， 分枝 限界法 ，遺傳算法這 4種求解 01背包問題的方法進(jìn)行研究比較，全方位的了解背包問題在實(shí)現(xiàn)的方法 ,以及各方法的優(yōu)勢和劣勢，通過比較，了解哪種方法是在什么樣的情況下是最實(shí)用的方法，然后在以后的實(shí)際運(yùn)用中針對實(shí)際問題，找到最簡單的方法解決 01背包問題。 當(dāng)然目前存在越來越多的算法來研究 01 背包問題，比如 蟻群算法、微粒群算法等群體智能算法在 01 背包問題求解方面具有的較好收斂速度、健壯性、穩(wěn)定性、算法簡單等優(yōu)點(diǎn) .最后 ,針對群體智能算法在求解 01背包問題過程中所出現(xiàn)的缺陷 ,提出了群體智能算法在 01 背包問題 ，還有一寫混合的多有算法來解決 01背包問題等等 01 背包 問題的求解方法研究已經(jīng)成為了當(dāng) 前眾多科學(xué)關(guān)注的焦點(diǎn)，這不僅在于其內(nèi)在的復(fù)雜性有著重要的理論價(jià)值，同時(shí)也在于它們能在現(xiàn)實(shí)生活中廣泛的應(yīng)用。比如資源分配、投資決策、裝載設(shè)計(jì)、公交車調(diào)度等一系列的問題都可以歸結(jié)到組合優(yōu)化問題中來。但是，往往由于問題的計(jì)算量遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)在有效時(shí)間內(nèi)的計(jì)算能力，使問題的求解變?yōu)楫惓５睦щy。尤其對于 NP 完全問題，如何求解其最優(yōu)解或是近似最優(yōu)解便成為科學(xué)的焦點(diǎn)之一。 23 參考文獻(xiàn) [1] 王曉東 .《計(jì)算機(jī)算法研究與分析》 .電子工業(yè)出版社 . [2] 著，吳偉昶，方世昌等譯 .《算法設(shè)計(jì)技巧與分析》 . 電子工業(yè)出版社 , 2021. [3] 胡運(yùn)權(quán)，運(yùn)籌學(xué)教程（第二版），清華大學(xué)出版社 ， 2021 年 . [4] 曹新譜 .《算法設(shè)計(jì)與分析》 .湖南科技出版社 ， 1984 年 11月第 1 版 . [5] 余祥宣 . 崔國華 . 鄒海明 . 計(jì)算機(jī)算法 [M].華中科技大學(xué)出版社 ，2021. [6] 李鳴山 .鄭海虹 . 01 背包間題的多重分枝 限界算法 .武漢側(cè)繪科技大學(xué)學(xué)報(bào) ， 1995 . 20 (1). [7] 霍紅衛(wèi) .許進(jìn) .保錚 .基于遺傳算法的 01 背包問題求解 .西安 電子科技大學(xué)學(xué)報(bào) ， （ 4） . [8] 劉西奎 .李艷 .許進(jìn) .背包問題的遺傳算法求解研究陰 .華中科技大學(xué)學(xué)報(bào) (自然科學(xué)版 )， 2021， 30(6)： 8990. [9] Mark Allen weiss 著 .馮舜璽譯 . 數(shù)據(jù)結(jié)構(gòu)與算法分析 — C 語言描述[M].北京 : 機(jī)械工業(yè)出版社 ， 2021. 1. [10] 盧開澄 .計(jì)算機(jī)算法引導(dǎo) 設(shè)計(jì)與分析 (第 2 版 )[M]=.北京 :清華大學(xué)出版社 ， 2021. [11] 鄭宗漢 .鄭曉明 . 算法設(shè)計(jì)與分析 [M].北京 :清華大學(xué)出版社 ， 2021. [12] 陳瑩 .廖利 .01 背包問題 [J].電腦知識與技術(shù) _研究開發(fā) ，:9697. [13] 朱紅 .算法設(shè)計(jì)與分析 [M].上海：上海科學(xué)技術(shù)文獻(xiàn)出版社 ， 1989． [14] 張文修 .梁怡 .遺傳算法的數(shù)學(xué)基礎(chǔ) [M].西安 :西安交通犬學(xué)出版社 ，2021. [15] COILEM TH， LEISERSON CE Introducetion to Algorithms[M]。Massachusetts： The MIT Press， 2021. [16] 曾國清 .0l 背包問題的遺傳算法求解 [J]．科技信 息 ,2021(3):242一 243． [17] 黃波 .蔡之華 . 0/1 背包問題及其解法研究 0/1 Knapsack Problem and Its Solution Methods Study 期刊電腦知識與技術(shù) (學(xué)術(shù)交流 )COMPUTER 24 KNOWLEDGE AND TECHNOLOGY ， 2021 年 第 07 期 . [18] 雷鵬 , 朱大銘 , 馬紹漢 , 0/1 背包問題算法研究新趨勢 2021 年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)會議 2021 年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)會議論文集 ， 2021年 . [19] 張景成 ,戴光明 基于 0/1 背包問題的算法探究 On the Algorithm of the 0/1 Knapsack Problem 期刊 電腦知識與技術(shù)（學(xué)術(shù)交流） COMPUTER KNOWLEDGE AND TECHNOLOGY， 2021 年 第 11 期 . 25 致 謝 彈指一揮間，四年的大學(xué)學(xué)習(xí)即將結(jié)束。在此，我要感謝華中師范大學(xué)漢口分校信息科學(xué)與技術(shù)學(xué)院的各位領(lǐng)導(dǎo)和老師們，感謝關(guān)心幫助過我的同學(xué)們。本文之得以完成，要特別感謝我的指導(dǎo)老師 賓云峰、楊健 老師。從論題的選擇、資料的收集、系統(tǒng)的研發(fā)到論文的寫作，都是在 賓云峰、楊健 老師的悉心指導(dǎo)和殷切關(guān)懷下完成的。他 們 嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神、淵博的理論知識和豐富的實(shí)踐經(jīng)驗(yàn)使我受益匪淺。在此，我向尊敬的 賓云峰、楊健 老師 致以崇高的敬意和衷心的感謝 ! 同時(shí)，向參加論文 審閱和答辯的各位專家和老師表示衷心的感謝。