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