背包問題數(shù)據(jù)結(jié)構(gòu)實驗報告

1、淮陰工學(xué)院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告選題名稱：背包問題求解系（院）:計算機工程系專業(yè)：計算機科學(xué)與技術(shù)班級:網(wǎng)絡(luò)107姓名：蔣為維學(xué) 號:1071304110指導(dǎo)教師：張亞紅張勇軍學(xué)年學(xué)期：20082009學(xué)年 第 2 學(xué)期2009 年 6 月 20 日設(shè)計任務(wù)書課題 名稱背包問題求解設(shè)計 目的通過一周的課程設(shè)計，實現(xiàn)回溯法解決背包問題的方法，達到鞏固理論知 識、鍛煉實踐能力、構(gòu)建合理知識結(jié)構(gòu)的目的。實驗 環(huán)境Windows2000以上操作系統(tǒng)Visual C+6.0以上編譯環(huán)境任務(wù) 要求1. 搜集背包問題方面的資料；2. 編寫代碼，實現(xiàn)回溯法背包問題；3撰寫課程設(shè)計報告；4.參加答辯；工作進度計劃

2、序號起止日期工作內(nèi)容12009.06.08理論輔導(dǎo)，搜集資料22009.06.082009.06.10編寫代碼，上機調(diào)試32009.06.11撰寫課程設(shè)計報告42009.06.12答辯指導(dǎo)教師：2009年 6 月10日1. 任務(wù)書格式參照任務(wù)書范例”執(zhí)行。2. 范例中的紅色.文字應(yīng)根據(jù)你所選擇的具體課題，修改為對應(yīng)的內(nèi)容。范例中的其它內(nèi)容不變。摘要：組合優(yōu)化問題的求解方法研究已經(jīng)成為了當(dāng)前眾多科學(xué)關(guān)注的焦點， 這不僅 在于其內(nèi)在的復(fù)雜性有著重要的理論價值， 同時也在于它們能在現(xiàn)實生活中廣泛 的應(yīng)用。比如資源分配、投資決策、裝載設(shè)計、公交車調(diào)度等一系列的問題都可 以歸結(jié)到組合優(yōu)化問題中來。 但是

3、，往往由于問題的計算量遠遠超出了計算機在 有效時間內(nèi)的計算能力，使問題的求解變?yōu)楫惓５睦щy。尤其對于NP完全問題，如何求解其最優(yōu)解或是近似最優(yōu)解便成為科學(xué)的焦點之一。 背包問題是一個典型 的組合優(yōu)化問題，在計算理論中屬于NP-完全問題，其計算復(fù)雜度為（丫），傳 統(tǒng)上采用動態(tài)規(guī)劃來求解。設(shè)wi是經(jīng)營活動i所需要的資源消耗，M是所能提 供的資源總量，pi是人們經(jīng)營活動i得到的利潤或收益，則背包問題就是在資源 有限的條件下， 追求總的最大收益的資源有效分配問題。關(guān)鍵詞： 背包問題，堆棧，回溯法，遞歸目錄1需求分析 11.1課程設(shè)計（實踐周）題目 11.2課程設(shè)計（實踐周）任務(wù)及要求 11.3課程設(shè)計

4、（實踐周）思想 11.4軟硬件運行環(huán)境及開發(fā)工具 22概要設(shè)計22.1本課題設(shè)計所用數(shù)據(jù)結(jié)構(gòu)以及流程圖 .22.1.1 棧的原理 .22.1 .2溯法介紹 .32.1.3 包問題整體流程圖 . 52.2 本課題主要設(shè)計思想 .63代碼設(shè)計63.1 定義棧和順序表結(jié)構(gòu)體 .63.2 棧的初始化 . 73.3 判斷?？?. 73.4 入棧 73.5 出棧 83.6 輸入元素 . 84調(diào)試與操作說明 .95總結(jié) 116致謝127 參考文獻 . 131 需求分析1.1 本課程設(shè)計（實踐周）題目假設(shè)有一個能裝入總體積為T的背包和n件體積分別為w1 , w2 ,，wn的物品，能否從n件物品中挑選若干件恰好

5、裝滿背包，即使 w1 +w2 + wn=T，要求找出所有滿足上述條件的解。例如：當(dāng) T=10,各件物品的體積 1 ， 8， 4， 3， 5， 2 時，可找到下列 4組解：（1， 4， 3， 2）（1， 4， 5）（8， 2）（3， 5， 2）該問題的模型可以表示為下述 0/1整數(shù)規(guī)劃模型：目標函數(shù)： maxf (x1,x2n,xn)cixii1s.twi xipii1*）xi 0,1 (i 1,2,n)式中 xi 為 0-1 決策變量， xi1時表示將物品 i 裝入背包中，xi 0 時則表示不將其裝入背包中1.2 課程設(shè)計（實踐周）任務(wù)及要求1. 搜集背包問題方面的資料；2. 作為組長，我負責(zé)

6、設(shè)計數(shù)據(jù)結(jié)構(gòu)，編寫代碼；彭建鑫設(shè)計流程圖和回 溯法介紹3. 撰寫課程設(shè)計報告；4. 參加答辯。1.3 課程設(shè)計（實踐周）思想利用回溯法的設(shè)計思想來解決背包問題。首先將物品排列成一列，然后順序選取物品裝入背包，假設(shè)已選取了前 i 件物品后背包還沒裝滿，則繼續(xù) 選取第 i+1 件物品，若該件物品 “太大”不能裝入，則棄之而選取下一件，直 到背包裝滿為止。 但如果在剩余的物品中找不到合適的物品以填滿背包， 則 說明“剛剛”裝入背包的那見物品 “不合適”，應(yīng)該將它去出 “棄之一邊 ”，繼續(xù) 再從“它之后”的物品中選取， 如此重復(fù)，直到求得滿足條件的解， 或者無解。 由于回溯法求解的規(guī)則是 “后進先出

7、”因此自然要用到棧。1.4 軟硬件運行環(huán)境及開發(fā)工具Win dows2000以上操作系統(tǒng)Visual C+6.0 以上編譯環(huán)境2 概要設(shè)計2.1 本課題設(shè)計所用數(shù)據(jù)結(jié)構(gòu)以及流程圖2.1.1 棧的原理作為組長，我主要是負責(zé)該部分。 背包問題求解涉及到的數(shù)據(jù)結(jié)構(gòu)主要 是棧，下面我就詳細的介紹一下有關(guān)棧方面的知識。棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。當(dāng)用 一維數(shù)組存儲棧時，被稱為順序棧。（1）通常稱插入、刪除的這一端為棧頂（ Top） ，另一端稱為棧底（ Bottom） ；（2）當(dāng)表中沒有元素時稱為空棧，用 Top=-1 表示；（3）棧為后進先出（Last In First

8、 Out）的線性表，簡稱為LIFO表。棧的修改是按后進先出的原則進行。 每次刪除（退棧） 的總是當(dāng)前棧中 最新的元素，即最后插入（進棧）的元素，而最先插入的是被放在棧的底 部，要到最后才能刪除。棧為后進先出（Last In First Out ）的線性表，簡稱為LIFO表。棧的修 改是按后進先出的原則進行。每次刪除（退棧）的總是當(dāng)前棧中 最新的元 素，即最后插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最 后才能刪除。流程圖如下：a0 ala n-1Push進棧）top(棧頂)棧的基本運算：(1) InitStack (S)構(gòu)造一個空棧So(2) StackEmpty (S)判棧空。若

9、S為空棧，則返回TRUE，否則返回FALSEo(3) StackFull (S)判棧滿。若S為滿棧，則返回TRUE，否則返回FALSEo注意：該運算只適用于棧的順序存儲結(jié)構(gòu)。(4) Push (S，x)進棧。若棧S不滿，則將元素x插入S的棧頂。(5) Pop (S)退棧。若棧S非空，則將S的棧頂元素刪去，并返回該元素。(6) StackTop (S)取棧頂元素。若棧S非空，則返回棧頂元素，但不改變棧的狀態(tài)。2.1.2回溯法介紹此部分由彭建鑫設(shè)計。1.什么是回溯法回溯法也稱為試探法，該方法首先暫時放棄關(guān)于問題規(guī)模大小的限制， 并將問題的候選解按某種順序逐一枚舉和檢驗。當(dāng)發(fā)現(xiàn)當(dāng)前候選解不可能是解時

10、，就選擇下一個候選解；倘若當(dāng)前候選解除了還不滿足問題規(guī)模要求外， 滿足所有其他要求時， 繼續(xù)擴大當(dāng)前候選解的規(guī)模， 并繼續(xù)試探。 如果當(dāng)前 候選解滿足包括問題規(guī)模在內(nèi)的所有要求時，該候選解就是問題的一個解。 在回溯法中，放棄當(dāng)前候選解，尋找下一個候選解的過程稱為回溯?；厮莘ㄊ且粋€既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。 它在包含問題 的所有解的解空間樹中， 按照深度優(yōu)先的策略， 從根結(jié)點出發(fā)搜索解空間樹。 算法搜索至解空間樹的任一結(jié)點時， 總是先判斷該結(jié)點是否肯定不包含問題 的解。如果肯定不包含， 則跳過對以該結(jié)點為根的子樹的系統(tǒng)搜索， 逐層向 其祖先結(jié)點回溯。否則，進入該子樹，繼續(xù)按深度優(yōu)先的

11、策略進行搜索?；?溯法在用來求問題的所有解時， 要回溯到根， 且根結(jié)點的所有子樹都已被搜 索遍才結(jié)束。 而回溯法在用來求問題的任一解時， 只要搜索到問題的一個解 就可以結(jié)束。這種以深度優(yōu)先的方式系統(tǒng)地搜索問題的解的算法稱為回溯 法，它適用于解一些組合數(shù)較大的問題。2 基本思想回溯即是較簡單、 較常用的搜索策略。 全面訪問所有可能的情況， 分為 兩種：不考慮給定問題的特有性質(zhì)，按事先頂好的順序，依次運用規(guī)則，即 盲目搜索的方法； 另一種則考慮問題給定的特有性質(zhì)， 選用合適的規(guī)則， 提 高搜索的效率，即啟發(fā)式的搜索?？捎没厮莘ㄇ蠼獾膯栴}P,通常要能表達為：對于已知的由n元組(xl, x2,，xn)

12、組成的一個狀態(tài)空間 E= (x1 , x2,，xn)1 xi Si , i=1 , 2,，n，給定關(guān)于n元組中的一個分量的一個約束集 D，要求E中滿足 D 的全部約束條件的所有 n 元組。其中 Si 是分量 xi 的定義域,且 |Si| 有限, i=1 , 2,，n。我們稱E中滿足D的全部約束條件的任一 n元組為問題P 的一個解。若已有滿足約束條件的部分解，不妨設(shè)為(x1,x2,x3,xi,ln, 則添加x(i+1)屬于s(i+2),檢查(x1,x2,xi,x(i+1)是否滿足條件，滿足了 就繼續(xù)添加x(i+2)、s(i+2)，若所有的x(i+1)屬于s(i+1)都不能得到部分解， 就去掉xi

13、，回溯到(xi,x2, x(1)，添加那些未考察過的x1屬于s1,看其是否滿足約束條件,為此反復(fù)進行,直至得到解或證明無解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地 檢測其是否滿足D的全部約束，若滿足，則為問題 P的一個解。但顯然, 其計算量是相當(dāng)大的。我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組（x1, x2,，xi）滿足D中僅涉及到x1，x2，xi的所有約束意味著j （ji） 元組（xi，x2，xj） 定也滿足D中僅涉及到xi，x2，xj的所有 約束，匸1，2，n。換句話說，只要存在OWj 。因此，對于約束集D具有 完備性的問題P, 旦檢測斷定某個j元組

14、（xi , x2,，xj）違反D中僅 涉及xi, x2,，xj的一個約束，就可以肯定，以（xi, x2,，xj）為前 綴的任何n元組（xi, x2,，xj, xj+i ,，xn）都不會是問題P的解， 因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問 題的上述性質(zhì)而提出來的比枚舉法效率更高的算法。2.i.3包問題整體流程圖圖2-i整體流程圖2.2 本課題設(shè)計的思想本算法采用先進后出的算法來一個一個測試可行的全部解，所以很顯然 要用到棧。我通過建立順序表來錄入我要輸入的各個物體的體積，然后通過 結(jié)構(gòu)體類型定義棧，把順序表中的各個物體逐一入棧，如果各物體體積總和 sum 比我預(yù)定的

15、目標體積小，那就繼續(xù)入棧，有合適的組合則輸出，否則說 明剛才選入的物體體積即棧最頂端的那個不適合導(dǎo)致后面沒有合適的解，所 以把它 POP 掉，然后從它后面繼續(xù)選取所要考察的物體體積。當(dāng)?shù)谝粋€物體 做棧底的所有情況滿足后，我們就要考慮以第二個物體為棧底的情況，其實 我并沒有把第一個物體出棧，只是我讀的時候把第一個物體 “屏蔽 ”了，也就 是說它雖然在棧中，但是我不考慮它，而是考慮新的棧也就是總棧中截取的 我需要的那部分目標棧段， 依次類推， 當(dāng)順序表中所有物體都做過 “棧底”后， 那么就沒有物體可以作為參數(shù)入棧或出棧了，所有循環(huán)結(jié)束。本算法采用 3 重 while 循環(huán)嵌套來實現(xiàn)算出所有不重復(fù)的

16、解。3 代碼設(shè)計3.1 定義棧和順序表結(jié)構(gòu)體typedef structint last;int datamaxsize;seqlist;/定義一個順序表結(jié)構(gòu)體變量typedef structint top;int sum;int datamaxsize;/定義一個棧結(jié)構(gòu)體變量seqstack;3.2 棧初始化 seqstack *init_seqstack() seqstack *s;s=new seqstack;/ 動態(tài)生成一個結(jié)構(gòu)體變量 sif(!s)空間不足printf( 空間不足 );/若無法生成結(jié)構(gòu)體，則輸出 return null;elses-top=-1;/初始棧頂為 -1 表

17、示棧為空s-sum=0;return s;3.3 判斷棧空int empty_seqstack(seqstack *s)if (s-top=-1)return 1;/棧頂為 -1，表明棧為空elsereturn 0;3.4 入棧int push_seqstack(seqlist *l,int i,seqstack *s)if(s-top=maxsize-1)/棧滿，無法入棧/順序表中第 i 個元素， i 入棧/棧中 sum 加和return 0;elses-top+;s-datas-top=i; s-sum=s-sum+l-datai; return 1;3.5 出棧int pop_seqst

18、ack(seqlist *l,seqstack *s,int *x) if(empty_seqstack(s)return 0; / ?？?，無元素輸出 else *x=s-datas-top; /x 指向棧頂元素s-sum=s-sum-l-datas-datas-top;/總和減去輸出的棧頂元素值 s-top-;/棧內(nèi)元素個數(shù)減 1return 1;3.6 輸入元素seqlist *init_seqlist()seqlist *l;int x=1; l=new seqlist;/定義一個順序表指針變量/動態(tài)生成一個順序表l-last=-1;printf(n 請依次 輸入個 物品 的大小， 輸入

19、 0結(jié)束nn);sca nf(%d, &x);/格式化輸入元素while(x!=0)/輸入元素不為0時，元素輸入不結(jié)束l-last+;II沒輸入一個元素，下標自增l-datal-last=x;sca nf(%d, &x);return l;4調(diào)試與操作說明輸入背包體積n為15,各物體體積分別為1、2、3、4、5、6 7、8、9、10、11、12、13、14、15,輸入完畢按0結(jié)束輸入，運行結(jié)果如下：QI *C:Documents and Settings,jerry面：LCM13O4：L：LO?fJft程序代碼Debuq、諸包求編冃 _ 口 X|= AaVh-NWWkrmiNWWVMSirfe

20、HWHrhNMNVU%MVh-MWMWfaM%dgj | 占J 昂頁 李 囲料!KBt . :-制作人；蔣前維*彭嬋罐*謹輸入背包體積的大小.込“請依炭輸入牛物品的大小，愉入0結(jié)束。0123l4UG7 3eg-l一圖4-1輸入背包體積和物品體積圖4-2可行的解程序調(diào)試成功在課程設(shè)計代碼調(diào)試過程中也出了不少差錯，比如頭文件很容易忽略， 同學(xué)指出才發(fā)現(xiàn)；一些符號，像 ；”也很容易拉掉；甚至像0和0這種小 錯誤有時也會發(fā)生，在經(jīng)過調(diào)試和完善程序的過程中，這些毛病已經(jīng)基本上 克服了。在此過程中我學(xué)到了不少調(diào)試的技巧，極大得豐富了編程的知識， 這些在程序的優(yōu)化方面幫助很大?？偨Y(jié)通過此次課程設(shè)計的實踐，感

21、觸較深。不僅使我加深了對書本知識的理解， 而且鍛煉了我編寫程序、調(diào)試程序的能力，學(xué)習(xí)文檔編寫規(guī)范，培養(yǎng)獨立學(xué)習(xí)、 吸取他人經(jīng)驗、探索前言知識的習(xí)慣，樹立團隊協(xié)作精神。同時，課程設(shè)計也充 分彌補課堂教學(xué)及普通實驗中知識的缺陷。 這次課程設(shè)計由于時間有限， 對有些 地方考慮的還不夠周到。在本課題中，我們研究了如何用遺傳算法求解組合優(yōu)化問題中的背包問題，背包問題是一個典型的組合優(yōu)化問題，在計算理論中屬于NP-完全問題， 其計算復(fù)雜度為，傳統(tǒng)上采用動態(tài)規(guī)劃來求解。背包問題就是在資源有限的條件下， 追求總的最大收益的資源有效分配問題。 所以我們試著用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識以 及回溯法來解決普通的背包問題。

22、我們可以看出在求解背包問題上顯示了超出想 象、良好的搜索能力，它具有收斂快、搜索速度快的特點，在試驗中取得了比動 態(tài)規(guī)劃、遺傳法和貪心法等更好的求解效果。 然而在一般情況下， 使用基本回溯 算法解決背包問題時， 得到問題的近似解也不能滿足逼近最優(yōu)解的要求。 如何改 進基本回溯算法使它所求得的解逼近最優(yōu)解， 成為我們當(dāng)前亟待解決的問題， 也 是我們將來的學(xué)習(xí)中需要改進和加強的地方。還有就是我們做的背包問題其實是整個背包問題的其中一支， 本次的實驗就 做了其中的一種，其他的沒有嘗試，這是本次課程設(shè)計的遺憾之處。另外，就是 本次課程設(shè)計的流程圖也是不太完美， 張亞紅老師說我們設(shè)計的流程圖在計算總 體

23、積 T 時如果不夠返回在計算體現(xiàn)不出出棧的效果，但是我們確實設(shè)計不出更 好的流程圖來體現(xiàn)出棧，所以也算是其中的遺憾。致謝一周的課程設(shè)計終于告與段落了， 在這次課程設(shè)計的過程中， 本人順利完成 了課程設(shè)計的大部分任務(wù)。 在這其中，我也學(xué)會了很多東西所以要感謝那些在這 其中幫助過我的人。首先，要感謝淮陰工學(xué)院、計算機工程系能為我們提供這次課程設(shè)計的機會。 正因為有了這次機會， 才使得我們對數(shù)據(jù)結(jié)構(gòu)有了更深的了解， 并且能熟練掌握 其中的一些算法設(shè)計等等， 所以要感謝學(xué)校的精心安排。 同時也要感謝實驗室的 工作人員， 為我們提供了一個良好的實驗環(huán)境， 使我們能安心的完成課程設(shè)計的 內(nèi)容。在這期間我還

24、要特別的感謝張亞紅老師和張勇軍老師， 他們作為我們的知 道老師， 在他們的幫助下， 我們可以很快的解決程序上的一些包括語法、 邏輯算 法、數(shù)據(jù)結(jié)構(gòu)方面的問題， 同時還學(xué)到了除本次課程設(shè)計以外的知識， 如張亞紅 老師還跟我們提到了其他的一些數(shù)據(jù)結(jié)構(gòu)的知識， 其中包括線性表、 樹、圖等等， 是我獲益匪淺。我還要感謝我的同組成員彭建鑫同學(xué)。 他和我一開始就明確分工， 才開始我 們一起找材料， 然后一起商討如何去實現(xiàn)這個設(shè)計。 在編程的過程中， 他又給與 了我很大的幫助， 有的如出棧的編程我不會的， 他會幫助我一起完成。 當(dāng)編程結(jié) 束的時候，我們卻不能正常的運行，在他的幫助下，很順利的找到了錯誤所在， 然后就順利的完成了背包問題求解這個設(shè)計。 雖然這個設(shè)計看似簡單， 但對我們 來說卻是個不小的挑戰(zhàn)，但我們還是戰(zhàn)勝了挑戰(zhàn)。還有就是要感謝圖書館， 它提供了大量的書籍供我們參考， 也為我們本次課 程設(shè)計提供了理論基礎(chǔ)。參考文獻1 蘇仕華數(shù)據(jù)結(jié)構(gòu)課程設(shè)計北京：機械工業(yè)出版社，