背包問(wèn)題數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

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

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

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

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

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

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

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

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

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

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

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

12、組成的一個(gè)狀態(tài)空間 E= (x1 , x2,，xn)1 xi Si , i=1 , 2,，n，給定關(guān)于n元組中的一個(gè)分量的一個(gè)約束集 D，要求E中滿足 D 的全部約束條件的所有 n 元組。其中 Si 是分量 xi 的定義域,且 |Si| 有限, i=1 , 2,，n。我們稱E中滿足D的全部約束條件的任一 n元組為問(wèn)題P 的一個(gè)解。若已有滿足約束條件的部分解，不妨設(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)，添加那些未考察過(guò)的x1屬于s1,看其是否滿足約束條件,為此反復(fù)進(jìn)行,直至得到解或證明無(wú)解。解問(wèn)題P的最樸素的方法就是枚舉法，即對(duì)E中的所有n元組逐一地 檢測(cè)其是否滿足D的全部約束，若滿足，則為問(wèn)題 P的一個(gè)解。但顯然, 其計(jì)算量是相當(dāng)大的。我們發(fā)現(xiàn)，對(duì)于許多問(wèn)題，所給定的約束集D具有完備性，即i元組（x1, x2,，xi）滿足D中僅涉及到x1，x2，xi的所有約束意味著j （ji） 元組（xi，x2，xj） 定也滿足D中僅涉及到xi，x2，xj的所有 約束，匸1，2，n。換句話說(shuō)，只要存在OWj 。因此，對(duì)于約束集D具有 完備性的問(wèn)題P, 旦檢測(cè)斷定某個(gè)j元組

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

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

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

17、示棧為空s-sum=0;return s;3.3 判斷?？読nt 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)/棧滿，無(wú)法入棧/順序表中第 i 個(gè)元素， 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; / 棧空，無(wú)元素輸出 else *x=s-datas-top; /x 指向棧頂元素s-sum=s-sum-l-datas-datas-top;/總和減去輸出的棧頂元素值 s-top-;/棧內(nèi)元素個(gè)數(shù)減 1return 1;3.6 輸入元素seqlist *init_seqlist()seqlist *l;int x=1; l=new seqlist;/定義一個(gè)順序表指針變量/動(dòng)態(tài)生成一個(gè)順序表l-last=-1;printf(n 請(qǐng)依次 輸入個(gè) 物品 的大小， 輸入

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

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

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

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

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

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