【文章內(nèi)容簡(jiǎn)介】 碼 sort(int[] sort){ for(int i=0。i。i++){ key= sort[i]。 j=i1。 while(j=0amp。amp。sort[j]key){ sort[j+1] = sort[j]。 j。 } sort[j+1] = key }}基本思想這是最基礎(chǔ)的背包問(wèn)題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。用子問(wèn)題定義狀態(tài)：即f[i][v]表示前i件物品恰放入一個(gè)容量為v的背包可以獲得的最大價(jià)值。則其狀態(tài)轉(zhuǎn)移方程便是：f[i][v]=max{f[i1][v],f[i1][vc[i]]+w[i]這個(gè)方程非常重要，基本上所有跟背包相關(guān)的問(wèn)題的方程都是由它衍生出來(lái)的。所以有必要將它詳細(xì)解釋一下：“將前i件物品放入容量為v的背包中”這個(gè)子問(wèn)題，若只考慮第i件物品的策略（放或不放），那么就可以轉(zhuǎn)化為一個(gè)只牽扯前i1件物品的問(wèn)題。如果不放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i1件物品放入容量為v的背包中”，價(jià)值為f[i1][v]；如果放第i件物品，那么問(wèn)題就轉(zhuǎn)化為“前i1件物品放入剩下的容量為vc[i]的背包中”，此時(shí)能獲得的最大價(jià)值就是f[i1][vc[i]]再加上通過(guò)放入第i件物品獲得的價(jià)值w[i]。01背包問(wèn)題輸入：物品名,物品數(shù)量，物品重量，物品價(jià)值,物品名,物品數(shù)量，物品重量，物品價(jià)值,...輸出：物品名物品數(shù)量，物品名物品數(shù)量，物品名物品數(shù)量，...偽代碼public void putBag(Goods[] goods){ for(int i=len1。i=0。i) { //計(jì)算當(dāng)前物品可以放多少個(gè) num = (int)(背包重量/當(dāng)前物品重量)。 //如果當(dāng)前物品無(wú)法放進(jìn)背包則進(jìn)行下一次循環(huán) if(num==0) continue。 //若當(dāng)前物品的數(shù)量大于可以放進(jìn)去的數(shù)量則放入num個(gè) else if(num當(dāng)前物品有的庫(kù)存) { (當(dāng)前物品，物品數(shù)量)。 bagWeight = 剩余背包空間當(dāng)前用去的空間。 } //若當(dāng)前物品數(shù)量小于可以放進(jìn)去的數(shù)量，則將所有的該物品全部放進(jìn)去 else if(num=當(dāng)前物品有的庫(kù)存) { (當(dāng)前物品，物品數(shù)量)。 bagWeight = 剩余背包空間當(dāng)前用去的空間。 } }}二項(xiàng)式系數(shù)計(jì)算基本思想1）怎么描述問(wèn)題，要把問(wèn)題描述為交疊的子問(wèn)題 2）交疊子問(wèn)題的初始條件（邊界條件） 3）動(dòng)態(tài)規(guī)劃在形式上往往表現(xiàn)為填矩陣的形式（在后面會(huì)看到，有的可以優(yōu)化空間復(fù)雜度，開一個(gè)數(shù)組即可，優(yōu)化也是根據(jù)遞推式的依賴形式的，后面有篇文章詳細(xì)說(shuō)明） 4）填矩陣的方式（或者說(shuō)順序）表明了什么？它表明了這個(gè)動(dòng)態(tài)規(guī)劃從小到大產(chǎn)生的過(guò)程，專業(yè)點(diǎn)的說(shuō)就是遞推式的依賴形式?jīng)Q定了填矩陣的順序。輸入：N二項(xiàng)式下標(biāo) K二項(xiàng)式項(xiàng)數(shù)輸出：當(dāng)前項(xiàng)數(shù)的值偽代碼Binomial(n,k) for i←0 to n do for j←0 to min(i,k) do if j=0 or j=k c[i,j]←1 else c[i,j]←c[i1,j1]+c[i1,j] return c(n,k) 迷宮問(wèn)題基本思想先將入口進(jìn)棧（初始方位設(shè)置為1），在棧不為空時(shí)循環(huán)：取棧頂方塊（不退棧），若是出口，則輸出棧中方塊即為路徑。否則，找下一個(gè)可走的相鄰方塊，若不存在這樣的方塊，則退棧。若存在，即將其方位保存到棧頂元素中，并將這個(gè)可走相鄰方塊進(jìn)棧（初始方位設(shè)置為1）輸入：迷宮長(zhǎng)和寬輸出：用戶給出迷宮的大小規(guī)格圖形偽代碼：findPath(int row,int col){ (board[row][col])。 //當(dāng)前方塊壓入棧 board[row][col].visit()。 //設(shè)置當(dāng)前棧已訪問(wèn) if(row==(heigth1)amp。amp。col==(width1)){ return true。 //當(dāng)前位置是否是出口 } if(當(dāng)前方塊的鄰接是否有路) findPath（鄰接方塊） else ()。 //將當(dāng)前方塊彈棧 }N皇后問(wèn)題基本思想要解決N皇后問(wèn)題，其實(shí)就是要解決好怎么放置這n個(gè)皇后，每一個(gè)皇后與前面的所有皇后不能在同一行、同一列、同一對(duì)角線，在這里我們可以以行優(yōu)先，就是說(shuō)皇后的行號(hào)按順序遞增，只考慮第i個(gè)皇后放置在第i行的哪一列，所以在放置第i個(gè)皇后的時(shí)候，可以從第1列判斷起，如果可以放置在第1個(gè)位置，則跳到下一行放置下一個(gè)皇后。如果不能，則跳到下一列...直到最后一列，如果最后一列也不能放置，則說(shuō)明此時(shí)放置方法出錯(cuò)，則回到上一個(gè)皇后向之前放置的下一列重新放置。此即是回溯法的精髓所在。當(dāng)?shù)趎個(gè)皇后放置成功后，即得到一個(gè)可行解，此時(shí)再回到上一個(gè)皇后重新放置尋找下一個(gè)可行解...如此后，即可找出一個(gè)n皇后問(wèn)題的所有可行解。 輸入：皇后的數(shù)量輸出：皇后的解數(shù)偽代碼public void backtrack(int i) { if(i n) { 記錄答案； } else { for(int j = 1。 j = n。 j++) { if(column[j] == 1 amp。amp。 rup[i+j] == 1 amp。amp。 lup[ij+n] == 1) { queen[i] = j。 column[j] = rup[i+j] = lup[ij+n] = 0。 backtrack(i+1)。 column[j] = rup[i+j] = lup[ij+n] = 1。 } } } }6 模塊二（知識(shí)學(xué)習(xí)模塊設(shè)計(jì)說(shuō)明） 模塊描述此模塊提供了直接方便的圖形化界面作為用戶接口，通過(guò)此模塊用戶可以對(duì)圖的遍歷知識(shí)學(xué)習(xí)、迷宮知識(shí)學(xué)習(xí)、01背包知識(shí)學(xué)習(xí)進(jìn)行操作。 功能 算法知識(shí)學(xué)習(xí)理解 輸入項(xiàng)在算法操作界面點(diǎn)擊“知識(shí)學(xué)習(xí)”按鈕 輸出項(xiàng)彈出一個(gè)新的窗口顯示該算法的學(xué)習(xí)知識(shí)內(nèi)容算法知識(shí)學(xué)習(xí)功能 知識(shí)學(xué)習(xí)時(shí)序圖7 模塊三（算法詳細(xì)演示模塊設(shè)計(jì)說(shuō)明） 模塊描述此模塊提供了直接方便的圖形化界面作為用戶接口，通過(guò)此模塊用戶可以對(duì)減治算法演示、動(dòng)態(tài)規(guī)劃演示、回溯算法演示進(jìn)行操作，此模塊主要用于算法演示。 功能初始化演示系統(tǒng)，提供算法演示選擇界面，用戶輸入數(shù)據(jù)，然后進(jìn)行算法的演示運(yùn)行 輸入項(xiàng)用戶在選擇完需要演示的算法后，再根據(jù)本系統(tǒng)給出的輸入提示輸入相應(yīng)的數(shù)據(jù)，然后點(diǎn)擊“演示”按鈕，在界面的運(yùn)行結(jié)果文本域中顯示算法演示的結(jié)果用戶選擇需要演示的算法，并顯示需要演示算法的界面，然后用戶根據(jù)系統(tǒng)給出的提示輸入相應(yīng)的數(shù)據(jù)。 接口用戶接口：本系統(tǒng)采用圖形接口。圖形用戶接口采用了圖形化的操作界面。內(nèi)部接口：此模塊采用數(shù)據(jù)耦合方式，通過(guò)參數(shù)表傳送數(shù)據(jù)、交換信息。減治、動(dòng)態(tài)規(guī)劃和回溯算法實(shí)驗(yàn)演示程序設(shè)計(jì)和實(shí)現(xiàn)測(cè)試用例說(shuō)明書編 制 陳鵬 審 核 邱建雄 批 準(zhǔn) 邱建雄 長(zhǎng)沙學(xué)院二零一四年五月二日測(cè)試用例說(shuō)明書1 引言 編寫的目的該系統(tǒng)在經(jīng)歷需求設(shè)計(jì)、軟件設(shè)計(jì)、數(shù)據(jù)庫(kù)設(shè)計(jì)、代碼設(shè)計(jì)之后開始編碼工作。完成編碼工作之后便可以按照本文檔進(jìn)行測(cè)試。本文檔為減治、動(dòng)態(tài)規(guī)劃和回溯算法實(shí)驗(yàn)演示程序設(shè)計(jì)與實(shí)現(xiàn)系統(tǒng)的系統(tǒng)測(cè)試活動(dòng)提供了范圍、方法方面的指導(dǎo)。本文檔覆蓋了各個(gè)功能流程和預(yù)期的輸入輸出。業(yè)務(wù)流程的詳細(xì)說(shuō)明有助于與客戶溝通。預(yù)期輸入輸出的詳細(xì)說(shuō)明有助于與開發(fā)人員的溝通，提高編寫符合要求的代碼。預(yù)期的讀者范圍包括：測(cè)試人員、用戶。 背景a. 系統(tǒng)名稱；減治、動(dòng)態(tài)規(guī)劃和回溯算法實(shí)驗(yàn)演示程序設(shè)計(jì)與實(shí)現(xiàn)b. 本項(xiàng)目提出者：邱建雄c. 開發(fā)者：陳鵬d. 用戶：算法初學(xué)者與算法愛(ài)好者e. 本軟件產(chǎn)品與其他有關(guān)軟件產(chǎn)品的關(guān)系：在myeclipse集成環(huán)境上進(jìn)行開發(fā)和調(diào)試 定義測(cè)試用例：為某個(gè)特殊目標(biāo)而編制的一組測(cè)試輸入、執(zhí)行條件以及預(yù)期結(jié)果，以便測(cè)試某個(gè)程序路徑或核實(shí)是否滿足某個(gè)特定需求。 參考資料[1] Anany Levitin著. 潘彥譯，算法設(shè)計(jì)與分析（第2版）［Ｍ］.北京：清華大學(xué)出版社,2007.[2] 王曉東編著，《算法設(shè)計(jì)與分析》［Ｍ］.電子工業(yè)出版社,2007.[3] 嚴(yán)蔚敏等. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）［Ｍ］.北京：清華大學(xué)出版社，2008.[4] 王鵬等. Java Swing 圖形界面開發(fā)與案例詳解［Ｍ］.清華大學(xué)出版社,2008.[5] ：C++語(yǔ)言描述［Ｍ］．北京：電子工業(yè)出版社，2006.2 測(cè)試用例(算法演示)詳細(xì)說(shuō)明環(huán)境要求硬件：PC機(jī)：一臺(tái)最低配置：可以穩(wěn)定運(yùn)行Windows7(中文)操作系統(tǒng)硬盤可用存儲(chǔ)空間至少50MB軟件：操作系統(tǒng)：Windows7(中文)，屏幕分辨率在1024*768（含）以上預(yù)置條件測(cè)試環(huán)境已搭建、軟件可測(cè)試。測(cè)試用例算法演示功能的測(cè)試。算法的測(cè)試用例。測(cè)試項(xiàng)目用例編號(hào)輸入條件操作步驟與測(cè)試數(shù)據(jù)預(yù)期結(jié)果實(shí)際結(jié)果插入排序算法演示進(jìn)入插入排序算法界面中測(cè)試數(shù)據(jù)：1,2,3，4,2,5,3,4,5,3,5操作步驟：點(diǎn)擊“使用已有數(shù)組排序”1 2 2 3 3 3 4 4 5 5 5同預(yù)期圖的深度優(yōu)先搜索算法演示進(jìn)入圖的遍歷界面中測(cè)試數(shù)據(jù)頂點(diǎn)集合：v1,v2,v3,v4,v5,v6,v7,v8 邊集合： v1v2,v1v3,v2v4,v4v8,v8v5,v3v6,v6v7開始頂點(diǎn)：v1操作步驟：點(diǎn)擊“深度優(yōu)先”v1 v2 v4 v8 v5 v3 v6 v7 同預(yù)期圖的廣度優(yōu)先搜索算法演示進(jìn)入圖的遍歷界面中測(cè)試數(shù)據(jù):頂點(diǎn)集合：v1,v2,v3,v4,v5,v6,v7,v8邊集合： v1v2,v1v3,v2v4,v4v8,v2v5,v3v6,v3v7 開始頂點(diǎn)：v1操作步驟：點(diǎn)擊“廣度優(yōu)先”v1v2v3 v4 v5v6 v7v8 同預(yù)期01背包算法演示進(jìn)入01背包界面中測(cè)試數(shù)據(jù)物品：蘋果52400，三星33210，背包負(fù)重：20步驟：點(diǎn)擊“開始計(jì)算”三星3 蘋果5同預(yù)期二項(xiàng)式算法演示進(jìn)入二項(xiàng)式界面中測(cè)試數(shù)據(jù)：N：8 k：5操作步驟：點(diǎn)擊“開始”56同預(yù)期N皇后算法演示進(jìn)入N皇后界面界面中測(cè)試數(shù)據(jù)：13操作步驟：點(diǎn)擊計(jì)算總數(shù)73712同預(yù)期迷宮算法演示進(jìn)入迷宮界面中測(cè)試數(shù)據(jù)：寬：14長(zhǎng)：15操作步驟：點(diǎn)擊“生成迷宮”彈出迷宮圖解界面同預(yù)期(知識(shí)學(xué)習(xí))詳細(xì)說(shuō)明環(huán)境要求硬件：PC機(jī)：一臺(tái)最低配置：可以穩(wěn)定運(yùn)行Windows7(中文)操作系統(tǒng)硬盤可用存儲(chǔ)空間至少50MB軟件：操作系統(tǒng)：Windows7(中文)，屏幕分辨率在1024*768（含）以上預(yù)置條件測(cè)試環(huán)境已搭建、軟件可測(cè)試。測(cè)試用例知識(shí)學(xué)習(xí)功能的測(cè)試。知識(shí)學(xué)習(xí)的測(cè)試用例。測(cè)試項(xiàng)目用例編號(hào)輸入條件操作步驟與測(cè)試數(shù)據(jù)預(yù)期結(jié)果實(shí)際結(jié)果插入排序知識(shí)學(xué)習(xí)進(jìn)入插入排序算法界面中點(diǎn)擊“知識(shí)學(xué)習(xí)”彈出算法知識(shí)學(xué)習(xí)界面同預(yù)期圖的遍歷知識(shí)學(xué)習(xí)進(jìn)入圖的遍歷界面中點(diǎn)擊“知識(shí)學(xué)習(xí)”彈出算法知識(shí)學(xué)習(xí)界面同預(yù)期01背包知識(shí)學(xué)習(xí)進(jìn)入01背包界面中點(diǎn)擊“知識(shí)學(xué)習(xí)”彈出算法知識(shí)學(xué)習(xí)界面同預(yù)期二項(xiàng)式知識(shí)學(xué)習(xí)進(jìn)入二項(xiàng)式界面中點(diǎn)擊“知識(shí)學(xué)習(xí)”彈出算法知識(shí)學(xué)習(xí)界面同預(yù)期N皇后知識(shí)學(xué)習(xí)進(jìn)入N皇后界面界面中點(diǎn)擊“知識(shí)學(xué)習(xí)”彈出算法知識(shí)學(xué)習(xí)界面同預(yù)期迷宮知識(shí)進(jìn)入迷宮界面中點(diǎn)擊“知識(shí)學(xué)習(xí)”彈出算法知識(shí)學(xué)習(xí)界面同預(yù)期(詳細(xì)演示)詳細(xì)說(shuō)明環(huán)境要求硬件：PC機(jī)：一臺(tái)最低配置：可以穩(wěn)定運(yùn)行Windows7(中文)操作系統(tǒng)硬盤可用存儲(chǔ)空間至少50MB軟件：操作系統(tǒng)：Windows7(中文)，屏幕分辨率在1024*768（含）以上預(yù)置條件測(cè)試環(huán)境已搭建、軟件可測(cè)試。測(cè)試用例知識(shí)學(xué)習(xí)功能的測(cè)試。詳細(xì)演示的測(cè)試用例。測(cè)試項(xiàng)目用例編號(hào)輸入條件操作步驟與測(cè)試數(shù)據(jù)預(yù)期結(jié)果實(shí)際結(jié)果插入排序詳細(xì)演示進(jìn)入插入排序算法界