算法分析與設(shè)計-課程設(shè)計報告-文庫吧資料
2025-07-30 12:24本頁面
【正文】 最優(yōu)值 bestW=cw。) break。 if(ch==39。 n++。sw)。 if(0==w) flag=false。 // 讀取數(shù)據(jù)原材料(木頭)長度 scanf(%d,amp。 memset(nVisited,false,MAX_SAMPLE_LENGTH*sizeof(bool))。 memset(visited,false,MAX_SAMPLE_LENGTH*sizeof(bool))。 // 當前求解最大值 bool input(){ bool flag=true。 // 當前已鋸木頭長度和 int res。 // 數(shù)據(jù)元素個數(shù) int sw。int w。bool* nVisited=(bool *)malloc(MAX_SAMPLE_LENGTH*sizeof(bool))。int* data=(int *)malloc(MAX_SAMPLE_LENGTH*sizeof(int))。當in1時，搜索左子樹的條件：當前節(jié)點未被訪問且cw+data[i]=w+sw，訪問左子樹時第i層相應(yīng)節(jié)點時將相應(yīng)訪問標記visited[i]置為true，遞歸搜索該節(jié)點的左子樹；遞歸搜索右子樹時，將當前節(jié)點訪問標記visited[i]置為false；Step 3：當in1時，獲得一種切割方案，若此次求解結(jié)果優(yōu)于已得求解結(jié)果，即bestWcw，使用nVisited數(shù)組記錄當前求解狀態(tài)，同時更新bestW的值；Step 4：利用回溯法完成1次木料切割后，更當前問題求解狀態(tài)res_arr數(shù)組，根據(jù)最新的求解狀態(tài)更新未切割木料數(shù)量count，同時res++，若count=0則求解結(jié)束，否則重復(fù)2,3,4直至count=0。樣例輸入：1000 100 250 250 500 650 10001000 50 200 250 250 500 650 970樣例輸出：34此題目是裝載問題的一個變種，與裝載問題不同的是此問題沒有給出“船”數(shù)量，但是給出了船的載重量，因此仍舊可以借鑒解裝載問題的思路，即讓每一根原材料可以切出更多符合要求的木料，類似于裝載問題中“將第一艘輪船盡可能地裝滿”，即保證切割以后剩余的原材料是最少的。每行由若干個整數(shù)構(gòu)成，第一個整數(shù)為所購買的木塊的長度L（0L=30000）,第二個整數(shù)為鋸子的寬度W（0W=1000）,其后的若干個整數(shù)分別表示制作家具時需要的木塊的長度。請設(shè)計一個程序使木匠能夠用最少的木材切割出所需的木塊。} 題目2 切割木材一個木匠從木材公司買了一批木材，每塊木材的長度均相同，但由于制作家具時所需的木塊長度各不相同，因此需要把這些木材切割成長度不同的木塊。 calculate()。}void solve(){ memset(dp,0,sizeof(dp))。i++){ cout stops[i]。 for(int i=0。 if(j==0) break。i++){ if(nextJ[i][j]!=j){ (i)。 for(int i=2。}// 重構(gòu)最優(yōu)解void rebuildSolution(){ vectorint stops。 // jj以前的乘客均離開電梯 nextJ[i][j]=jj。jj++){ // 計算離開電梯的人和留在電梯里面的人中到達目的地最晚的 int tmp=max(tStay(i,j,jj),tLeave(i,jj+1,j))。 for(int jj=0。j=n。i=1。j++){ // 1,j表示?？空埱蟮木幪?編號越小表示編號?？繕菍釉礁? dp[topFloor][j]=tLeave(topFloor,1,j)。 for(int j=1。 // 一般情況，電梯在第i層停靠 else return dp[i+1][jj]+ve+st。}// 現(xiàn)在電梯在第i層, 電梯里面本來有j位乘客, 離開電梯的乘客剩下jj位int tStay(int i,int j,int jj){ // 沒有乘客離開,電梯不停 if(j==jj || i==1) return dp[i+1][jj] +ve。// 目前電梯在第currF層, 第L層到第R層乘客離開電梯// 函數(shù)返回這些離開電梯的乘客中最晚到達目的層所需時間int tLeave(int currF,int l,int r){ if(lr) return 0。 return true。i=1。 if(n==0) return false。int n,f[maxN+1]。const int maxN=30,maxF=31。第三步：根據(jù)計算最優(yōu)值時記錄的信息求解最優(yōu)解。具體求解過程：第一步：計算初始狀態(tài)f(topF
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1