算法分析與設(shè)計(jì)-課程設(shè)計(jì)報(bào)告(編輯修改稿)
2025-08-20 12:24 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 nextJ[i][j]=jj。 } } } } coutdp[1][n]endl。}// 重構(gòu)最優(yōu)解void rebuildSolution(){ vectorint stops。 int j=nextJ[1][n],topFloor=f[1]。 for(int i=2。i=topFloor。i++){ if(nextJ[i][j]!=j){ (i)。 j=nextJ[i][j]。 if(j==0) break。 } } cout()。 for(int i=0。i()。i++){ cout stops[i]。 } coutendl。}void solve(){ memset(dp,0,sizeof(dp))。 memset(nextJ,0,sizeof(nextJ))。 calculate()。 rebuildSolution()。} 題目2 切割木材一個(gè)木匠從木材公司買(mǎi)了一批木材，每塊木材的長(zhǎng)度均相同，但由于制作家具時(shí)所需的木塊長(zhǎng)度各不相同，因此需要把這些木材切割成長(zhǎng)度不同的木塊。同時(shí)每次切割時(shí)由于鋸子本身有一定的寬度，因此每切割一次就會(huì)浪費(fèi)掉一些木料。請(qǐng)?jiān)O(shè)計(jì)一個(gè)程序使木匠能夠用最少的木材切割出所需的木塊。輸入描述：輸入有若干個(gè)測(cè)試樣例，每個(gè)測(cè)試樣例占一行。每行由若干個(gè)整數(shù)構(gòu)成，第一個(gè)整數(shù)為所購(gòu)買(mǎi)的木塊的長(zhǎng)度L（0L=30000）,第二個(gè)整數(shù)為鋸子的寬度W（0W=1000）,其后的若干個(gè)整數(shù)分別表示制作家具時(shí)需要的木塊的長(zhǎng)度。輸出描述： 每個(gè)測(cè)試樣例輸出一行，為一個(gè)整數(shù)N，表示制作家具時(shí)需要購(gòu)買(mǎi)的木塊的數(shù)量。樣例輸入：1000 100 250 250 500 650 10001000 50 200 250 250 500 650 970樣例輸出：34此題目是裝載問(wèn)題的一個(gè)變種，與裝載問(wèn)題不同的是此問(wèn)題沒(méi)有給出“船”數(shù)量，但是給出了船的載重量，因此仍舊可以借鑒解裝載問(wèn)題的思路，即讓每一根原材料可以切出更多符合要求的木料，類似于裝載問(wèn)題中“將第一艘輪船盡可能地裝滿”，即保證切割以后剩余的原材料是最少的。算法具體描述如下：Step 1：聲明求解結(jié)果變量res=0，剩余未切割木料數(shù)量count=n，當(dāng)前已切割木料長(zhǎng)度和cw=0，目前最大切割長(zhǎng)度bestW=0，求解標(biāo)記數(shù)組visited[n]，當(dāng)前最優(yōu)求解數(shù)組nVisited[n]，問(wèn)題求解狀態(tài)記錄數(shù)組res_arr[n]，鋸口寬度sw；Step 2：當(dāng)剩余未切割木料數(shù)量count大于0時(shí)，利用回溯法進(jìn)行最大子集和求解。當(dāng)in1時(shí)，搜索左子樹(shù)的條件：當(dāng)前節(jié)點(diǎn)未被訪問(wèn)且cw+data[i]=w+sw，訪問(wèn)左子樹(shù)時(shí)第i層相應(yīng)節(jié)點(diǎn)時(shí)將相應(yīng)訪問(wèn)標(biāo)記visited[i]置為true，遞歸搜索該節(jié)點(diǎn)的左子樹(shù)；遞歸搜索右子樹(shù)時(shí)，將當(dāng)前節(jié)點(diǎn)訪問(wèn)標(biāo)記visited[i]置為false；Step 3：當(dāng)in1時(shí)，獲得一種切割方案，若此次求解結(jié)果優(yōu)于已得求解結(jié)果，即bestWcw，使用nVisited數(shù)組記錄當(dāng)前求解狀態(tài)，同時(shí)更新bestW的值；Step 4：利用回溯法完成1次木料切割后，更當(dāng)前問(wèn)題求解狀態(tài)res_arr數(shù)組，根據(jù)最新的求解狀態(tài)更新未切割木料數(shù)量count，同時(shí)res++，若count=0則求解結(jié)束，否則重復(fù)2,3,4直至count=0。圖 8 main函數(shù)流程圖圖 9 input函數(shù)流程圖圖 10 solve函數(shù)流程圖圖 11 backtrack函數(shù)流程圖 include include includecstring define MAX_SAMPLE_LENGTH 50/*回溯法求解*/int* in=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int))。int* data=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int))。bool* visited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool))。bool* nVisited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool))。bool* res_arr=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool))。int w。 // 原材料長(zhǎng)度 int n。 // 數(shù)據(jù)元素個(gè)數(shù) int sw。 // 鋸口寬度 int cw。 // 當(dāng)前已鋸木頭長(zhǎng)度和 int res。 // 求解結(jié)果 int bestW。 // 當(dāng)前求解最大值 bool input(){ bool flag=true。 //初始化數(shù)據(jù)保存數(shù)組 memset(in,0,MAX_SAMPLE_LENGTH
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1