回溯法背包問(wèn)題課程設(shè)計(jì)報(bào)告

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