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