貪心、回溯法實驗報告

西安郵電大學(xué)（計算機(jī)學(xué)院）算法設(shè)計與分析課內(nèi)實驗報告題目：貪心法、回溯法專業(yè)名稱：軟件工程班級：軟件1602學(xué)生姓名：張鑫學(xué)號（8位）：04163036指導(dǎo)教師：陳琳設(shè)計起止時間：2018.4.25----2018.5.9設(shè)計目的掌握動態(tài)規(guī)劃的算法的基本要素。掌握設(shè)計動態(tài)規(guī)劃算法的步驟。理解動態(tài)規(guī)劃算法的概念。設(shè)計內(nèi)容給定N中物品和一背包。物品i的重量是Wi,體積是Bi，其價值為Vi，背包的容量為c，容積為d。應(yīng)如何選擇裝入背包中，使裝入背包中物品的總價值最大？在選擇裝入背包的物品時，對每種物品i只有兩種選擇，裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。設(shè)計算法解決問題。設(shè)A和B是兩個字符串。要用最少的字符操作將字符串A轉(zhuǎn)換為字符串B。字符串操作包括：刪除一個字符、插入一個字符、將一個字符改為另一個字符。試設(shè)計算法解決問題。三．算法設(shè)計與分析1．算法設(shè)計思想1)相對于普通的背包問題，費用加了一維，只需狀態(tài)也加一維即可。設(shè)f[i][v][u]表示前i件物品付出兩種代價分別為v和u時可獲得的最大價值。方程就是：f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}?？梢灾皇褂枚S的數(shù)組：當(dāng)每件物品只可以取一次時變量v和u采用逆序的循環(huán)，當(dāng)物品有如完全背包問題時采用順序的循環(huán)。當(dāng)物品有如多重背包問題時拆分物品。2)首先定義這樣一個函數(shù)——edit(i,j)，它表示第一個字符串的長度為i的子串到第二個字符串的長度為j的子串的編輯距離。顯然可以有如下動態(tài)規(guī)劃公式：ifi==0且j==0，edit(i,j)=0ifi==0且j>0，edit(i,j)=jifi>0且j==0，edit(i,j)=iif

i≥1

且

j≥1，edit(i,j)==min{edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)+f(i,j)}，當(dāng)?shù)谝粋€字符串的第i個字符不等于第二個字符串的第j個字符時，f(i,j)=1；否則，f(i,j)=0主要模塊流程圖。開始開始背包是否超過容量背包是否超過容量是 否不裝裝不裝裝開始開始定義函數(shù)定義函數(shù)edit(i,j) edit(i,j)==min{edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)+f(i,j)}edit(i,j)=iedit(i,j)=jEdit(i,j)=0edit(i,j)==min{edit(i-1,j)+1,edit(i,j-1)+1,edit(i-1,j-1)+f(i,j)}edit(i,j)=iedit(i,j)=jEdit(i,j)=03．重點設(shè)計及編碼1.intpackage(){for(inti=1;i<=U;i++)for(intj=1;j<=V;j++)f[i][j]=INF;f[0][0]=0;for(inti=0;i<T;i++){for(intu=U;u>=a[i];u--){for(intv=V;v>=b[i];v--)f[u][v]=max(f[u-a[i]][v-b[i]]+w[i],f[u][v]);}}returnf[U][V];}2.intcalcDistance(char*A,char*B,intm,intn){if(m==0&&n==0)return0;if(m==0)returnn;if(n==0)returnm;intcaseA=calcDistance(A,B,m-1,n)+1;intcaseB=calcDistance(A,B,m,n-1)+1;intcaseC=calcDistance(A,B,m-1,n-1)+(A[m]!=B[n]);returngetMin(caseA,caseB,caseC);}五．測試數(shù)據(jù)及運行結(jié)果1．正常測試數(shù)據(jù)和運行結(jié)果1.22．異常測試數(shù)據(jù)及運行結(jié)果1.2.六．調(diào)試情況，設(shè)計技巧及體會1．改進(jìn)方案對于背包問題的那一塊，其核心代碼還有待改進(jìn)，進(jìn)行算法優(yōu)化，該程序的數(shù)據(jù)輸入可以羅列出來，不用寫死在程序里面。2．體會實驗剛開始時，由于動態(tài)規(guī)劃的基本思想掌握的不是很清楚，不知道改如何設(shè)計問題后來仔細(xì)復(fù)習(xí)了本節(jié)知識，才有了思緒。在掌握了動態(tài)規(guī)劃算法