回溯法背包問題課程設(shè)計報告

-2-一概述問題：回溯法背包問題求解。問題描述：假設(shè)有一個能裝入總體積為T的背包和n件體積分別為w1,w2,…,wn的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使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）。主要解決點：遞歸函數(shù)的遞歸參數(shù)和遞歸內(nèi)容二設(shè)計的基本概念和原理式中x為0-1決策變量，x=1時表示將物品i裝入背包中，x=0時則表示不將其裝入背包中。棧的原理：棧（Stack）是限制僅在表的一端進行插入和刪除運算的線性表。當(dāng)用一維數(shù)組存儲棧時，被稱為順序棧。

(1)通常稱插入、刪除的這一端為棧頂（Top），另一端稱為棧底（Bottom）；

(2)當(dāng)表中沒有元素時稱為空棧，用Top=1表示；

(3)棧為后進先出（LastInFirstOut）的線性表，簡稱為LIFO表。棧的修改是按后進先出的原則進行。每次刪除（退棧）的總是當(dāng)前棧中"最新"的元素，即最后插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。棧為后進先出（LastInFirstOut）的線性表，簡稱為LIFO表。棧的修改是按后進先出的原則進行。每次刪除（退棧）的總是當(dāng)前棧中"最新"的元素，即最后插入（進棧）的元素，而最先插入的是被放在棧的底部，要到最后才能刪除。流程圖如下：Push(進棧)a0a1……an-1Pop(出棧)top(棧頂)回溯法：三總體設(shè)計使用語言：Java界面化展示：Android實現(xiàn)方法利用回溯法的設(shè)計思想來解決背包問題。首先將物品排列成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i件物品后背包還沒裝滿，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而選取下一件，直到背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明上一個裝入背包的物品在此種情況下不是最優(yōu)選擇，將其去掉形成新的棧，繼續(xù)再從他下一個物品中選取，如此重復(fù)，直到求得滿足條件的解，或者無解。由于回溯法求解的規(guī)則是“后進先出”因此自然要用到棧。（1）主要功能模塊實現(xiàn)遞歸參數(shù)確定:數(shù)據(jù)位置，當(dāng)前結(jié)果集總重量物品數(shù)據(jù)通過List方式存儲，每個物品都存在兩個屬性，“編號”和“是否用過”。那么，每次遞歸首先要記錄的就是本次操作執(zhí)行時，當(dāng)前的操作數(shù)編號。以編號方式代替數(shù)據(jù)，類似于數(shù)據(jù)庫中的數(shù)據(jù)id亦或是Map映射中的key與value的關(guān)系。其次，每次操作主要是重量的比較，那么，當(dāng)前結(jié)果集的重量和剩余重量都是重要參數(shù)，由于整體操作是向結(jié)果數(shù)據(jù)及棧中增加數(shù)據(jù)，每次操作是與背包容量進行比較，因此，選擇當(dāng)前結(jié)果集總重量。遞歸主體：得到當(dāng)前棧中的最后一個數(shù)的數(shù)據(jù)位置，和當(dāng)前結(jié)果集總重量，從上一個位置開始遍歷，遍歷剩余的產(chǎn)品，如果此數(shù)在備選項中且沒有被使用，同時，此物品重量小于或等于背包容量，則將此物品的序號計入相應(yīng)的位置數(shù)組中，繼續(xù)向下執(zhí)行，如果當(dāng)前結(jié)果集總重量加上此物品重量剛好等于背包容量，者通過位置數(shù)組輸出數(shù)據(jù)，這便是一組符合要求的結(jié)果，如果不等，設(shè)置此數(shù)據(jù)為被使用并將當(dāng)前結(jié)果總重量和位置加一遞歸此函數(shù)。遞歸堆棧演示圖：演示數(shù)據(jù)：背包重量5物品重量1，2，3，4得到第一組結(jié)果：（1，4）一次循環(huán)結(jié)束，進行下一次循環(huán)，第一次進入2作為結(jié)果集的第一個數(shù)。產(chǎn)生過程的樹狀圖：（2）Android界面展示設(shè)計在MainActivity中加入輸入框，讓用戶輸入背包總量和產(chǎn)生的隨機數(shù)個數(shù)，按鈕產(chǎn)生隨機數(shù)，通過ListView展示，以List數(shù)組方式存儲并傳遞給下一層。點擊產(chǎn)生結(jié)果跳轉(zhuǎn)到下一個Activity進行上訴功能模塊操作，并返回結(jié)果集給ListView展示。四詳細(xì)設(shè)計主要功能模塊詳細(xì)設(shè)計參數(shù)隨機數(shù)集：通過Random方法產(chǎn)生隨機數(shù)，用List接收產(chǎn)生的數(shù)據(jù)。在操作前將List從新排序，消除相同的數(shù)據(jù)，返回操作后的List的長度作為操作長度。循環(huán)給Site位置數(shù)組和disUsed使用標(biāo)記數(shù)組初始化。遍歷函數(shù)：通過if判斷nowSum+goodsList.get(j)==bound，（bound是總重量，nowSum是當(dāng)前結(jié)果集的總重量）滿足此種情況時，結(jié)果集滿足條件。Android展示模塊的詳細(xì)設(shè)計輸入框設(shè)計：第一個展示頁面顯示，加入兩個EditText，分別接受背包容量和產(chǎn)生數(shù)據(jù)量，添加內(nèi)容改變監(jiān)聽，在onTextChanged（內(nèi)容改變方法）中加入一個線程，當(dāng)內(nèi)容改變時，更新主線程，把產(chǎn)生結(jié)果按鈕隱藏，清楚產(chǎn)生的隨機數(shù)據(jù)。設(shè)置輸入框為只能輸入數(shù)字。隨機數(shù)產(chǎn)生設(shè)計：添加點擊事件監(jiān)聽，加入一個flag標(biāo)記，如果輸入框沒有輸入數(shù)據(jù)，展示一個Toast提示用戶，并把標(biāo)記設(shè)為false。當(dāng)flag為真時，且沒有被點擊過，進入產(chǎn)生隨機數(shù)函數(shù)，并顯示產(chǎn)生結(jié)果的跳轉(zhuǎn)按鈕。通過ListView展示參數(shù)的結(jié)果集。數(shù)據(jù)展示的界面設(shè)計：加入AsyncTask異步加載，在新的線程中進行數(shù)據(jù)結(jié)果產(chǎn)生操作，在開始時顯示dialog，完成時消失。產(chǎn)生的結(jié)果通過list方式存儲，并用listview展示。五系統(tǒng)調(diào)試過程測試數(shù)據(jù)：背包總量20產(chǎn)生隨機數(shù)個數(shù)10產(chǎn)生的隨機數(shù)：1,2,4,9,10,10,13,16,17,17輸出結(jié)果：(12413)(1217)(1910)(416)遞歸次數(shù)：39遞歸中間量變化：1nowSum01num12nowSum12num23nowSum33num34nowSum74num45nowSum165num56nowSum176num57nowSum127num48nowSum138num49nowSum169num410nowSum1910num411nowSum511num312nowSum1412num413nowSum1513num414nowSum1814num415nowSum1015num316nowSum1116num317nowSum1417num318nowSum1718num319nowSum1819num320nowSum220num221nowSum621num322nowSum1522num423nowSum1623num424nowSum1924num425nowSum1125num326nowSum1226num327nowSum1527num328nowSum1828num329nowSum1929num330nowSum430num231nowSum1331num332nowSum1432num333nowSum1733num334nowSum934num235nowSum1935num336nowSum1036num237nowSum1337num238nowSum1638num239nowSum1739num2六使用過程輸入數(shù)據(jù)點擊產(chǎn)生隨機數(shù)。點擊產(chǎn)生結(jié)果，跳轉(zhuǎn)產(chǎn)生的結(jié)果集。七總結(jié)