算法分析與設(shè)計(jì)課程設(shè)計(jì)報(bào)告-展示頁
2025-01-27 23:42本頁面
【正文】 /物品單位價(jià)值double total_price。 //物品重量 double Price[MAX]。 //背包容量double X[MAX]。四、算法實(shí)現(xiàn)普通背包問題1）聲明變量、函數(shù)// 聲明變量int N。則將殘缺棋盤三格板編號的存儲(chǔ)在數(shù)組board[ ][ ]的對應(yīng)位置中，這樣輸出數(shù)組內(nèi)容就是問題的解。? size:棋盤的行數(shù)或列數(shù)3）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：用二維數(shù)組board[ ][ ]，模擬棋盤。? dr 殘缺方塊所在行。? tr 棋盤中左上角方格所在行。 從以上例子還可以發(fā)現(xiàn)，當(dāng)殘缺方格在第1個(gè)子棋盤，用①號三格板覆蓋其余三個(gè)子棋盤的交界方格，可以使另外三個(gè)子棋盤轉(zhuǎn)化為獨(dú)立子問題；同樣地（如下圖49所示），當(dāng)殘缺方格在第2個(gè)子棋盤時(shí)，則首先用②號三格板進(jìn)行棋盤覆蓋，當(dāng)殘缺方格在第3個(gè)子棋盤時(shí)，則首先用③號三格板進(jìn)行棋盤覆蓋，當(dāng)殘缺方格在第4個(gè)子棋盤時(shí)，則首先用④號三格板進(jìn)行棋盤覆蓋，這樣就使另外三個(gè)子棋盤轉(zhuǎn)化為獨(dú)立子問題。因?yàn)楫?dāng)如圖48中的殘缺方格在左上部時(shí)，第1個(gè)子問題與原問題相似，而右上角、左下角和右下角三個(gè)子棋盤（也就是圖中標(biāo)識為4號子棋盤），并不是原問題的相似子問題，自然也就不能獨(dú)立求解了。棋盤覆蓋問題1）問題分解過程如下： 以k=2時(shí)的問題為例，用二分法進(jìn)行分解，得到的是如下圖48，用雙線劃分的四個(gè)k=1的棋盤。 price[]存儲(chǔ)物品價(jià)值。這樣四個(gè)子棋盤就分別都和原來的大棋盤類似，我們就可以用遞歸算法解決。如果是：左上的子棋盤（若不存在特殊方格）則將該子棋盤右下角的那個(gè)方格假設(shè)為特殊方格；右上的子棋盤（若不存在特殊方格）則將該子棋盤左下角的那個(gè)方格假設(shè)為特殊方格；左下的子棋盤（若不存在特殊方格）則將該子棋盤右上角的那個(gè)方格假設(shè)為特殊方格；右下的子棋盤（若不存在特殊方格）則將該子棋盤左上角的那個(gè)方格假設(shè)為特殊方格。 因?yàn)榛厮萸蠼獾囊?guī)則是后進(jìn)先出，所以要用到棧來存儲(chǔ)符合條件的解，在存儲(chǔ)過程中，利用數(shù)組來存儲(chǔ)各個(gè)物品的體積，然后用深度優(yōu)先的搜索方式求解，將符合條件的數(shù)組元素的下標(biāo)存入棧里，最后得到符合條件的解并且實(shí)現(xiàn)輸出。利用回溯算法來解決01背包，首先是將可供選擇的物品的個(gè)數(shù)輸入程序，將物品排成一列，計(jì)算總物品的重量weight，然后輸入背包的實(shí)際重量weight，如果背包的重量小于0或者大于物品的總重量weight，則判斷輸入的背包重量錯(cuò)誤，否則開始順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品太大不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。如果肯定不包含，則跳過對以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其原先結(jié)點(diǎn)回溯。它在包含問題的所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。01背包問題回溯法：是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的的搜索算法。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋。xi=1表示物品i裝入背包中，xi=0表示物品i不裝入背包。約束條件 =c和 。從n個(gè)物品中選取裝入背包的物品，每件物品i的重量為wi, 價(jià)值為pi。物品可以拆分，利用貪心算法解決。算法分析與設(shè)計(jì)課程設(shè)計(jì)報(bào)告目 錄一、問題描述 1普通背包問題 101背包問題 1棋盤覆蓋問題 1二、問題分析 2普通背包問題 201背包問題 2棋盤覆蓋問題 3三、算法設(shè)計(jì) 3普通背包問題 301背包問題 4棋盤覆蓋問題 4四、算法實(shí)現(xiàn) 6普通背包問題 601背包問題 8棋盤覆蓋問題 10五、測試分析 11普通背包問題 1101背包問題 13棋盤覆蓋問題 15六、結(jié)論 16七、源程序 17普通背包問題 1701背包問題 20棋盤覆蓋問題 24八、參考文獻(xiàn) 26一、問題描述普通背包問題有一個(gè)背包容量為C，輸入N個(gè)物品，每個(gè)物品有重量S[i]，以及物品放入背包中所得的收益P[i]。求選擇放入的物品，不超過背包的容量，且得到的收益最好。01背包問題在0/1背包問題中，需對容量為c的背包進(jìn)行裝載。對于可行的背包裝載，背包中的物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即 取得最大值。在這個(gè)表達(dá)式中，需求出xi的值。棋盤覆蓋問題在一個(gè)2k2k 個(gè)方格組成的棋盤中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。二、問題分析普通背包問題貪心算法的基本思想是：從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的求得更好的解。背包問題用貪心算法來解決，先求出每件物品的平均價(jià)值即p[i]/s[i]，然后每次選擇利潤p[i]/s[i]最大的物品裝進(jìn)背包，這樣就使得目標(biāo)函數(shù)增加最快，當(dāng)最后一種物品放不下時(shí)，選擇一個(gè)適當(dāng)?shù)牟鸱?，使物品裝滿背包，使得總的價(jià)值最大。其基本思想是在搜索嘗試中找問題的解，當(dāng)不滿足條件就”回溯”返回，嘗試別的路徑。算法搜索至解空間樹的任一結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明剛剛裝入背包的那件物品不合適，應(yīng)將它取出棄之一邊，繼續(xù)再從它之后的物品中選取，如此重復(fù)，直至求得滿足條件的解。 棋盤覆蓋問題將2^k x 2^k的棋盤，先分成相等的四塊子棋盤，其中特殊方格位于四個(gè)中的一個(gè)，構(gòu)造剩下沒特殊方格三個(gè)子棋盤，將他們中的也假一個(gè)方格設(shè)為特殊方格。當(dāng)然上面四種，只可能且必定只有三個(gè)成立，那三個(gè)假設(shè)的特殊方格剛好構(gòu)成一個(gè)L型骨架，我們可以給它們作上相同的標(biāo)記。三、算法設(shè)計(jì)普通背包問題1）基本思路：首先，按物品單位價(jià)值由大到小將物品排序；(為了貪心選擇準(zhǔn)備)然后，依次將單位價(jià)值大的物品放入背包（貪心選擇），直到背包放滿為止；在向背包放置物品的過程中，如果正在考慮裝入的物品不能全部放進(jìn)去，則可以將物品的部分放入背包； 2）算法設(shè)計(jì)：用一維數(shù)組x[n] (x[i]∈{1,2, … ,n})，保存問題的解；weight[]存儲(chǔ)物品重量。01背包問題1）基本思路： ①確定問題的解空間，并將解空間組織成易于搜索的子集樹的形式；②以深度優(yōu)先的方式搜索整個(gè)解空間，遇到不滿足約束要求的節(jié)點(diǎn)就回溯，沿另一個(gè)分支繼續(xù)搜索；約束函數(shù)剪枝，不能超載，超載就回溯。但要注意這四個(gè)棋盤，并不都是與原問題相似且獨(dú)立的子問題。當(dāng)使用一個(gè)①號三格板（圖中陰影）覆蓋4號三個(gè)子棋盤的各一個(gè)方格后，如48右圖所示，我們把覆蓋后的方格，也看作是殘缺方格（稱為“偽”殘缺方格），這時(shí)的4號子問題就是獨(dú)立且與原問題相似的子問題了。 ：2）棋盤的識別： 棋盤的規(guī)模是一個(gè)必要的信息，有了這個(gè)信息，只要知道其左上角的左上角方格所在行、列就可以唯一確定一個(gè)棋盤了，殘缺方格或“偽”殘缺方格直接用行、列號記錄。? tc 棋盤中左上角方格所在列。? dl 殘缺方塊所在列。覆蓋殘缺棋盤所需要的三格板(L牌)數(shù)目為：( size2 1 ) / 3；將這些三格板編號為1到( s i z e21 ) / 3。理解算法。 //物品數(shù)量int M。 //背包問題最優(yōu)解double Weight[MAX]。 //物品價(jià)值double unit_price[MAX]。 //背包總價(jià)值 //聲明函數(shù)
高考資料相關(guān)推薦
鄂ICP備17016276號-1