計算機算法設計與分析實驗報告

《計算機算法設計與分析實驗報告》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、華北電力大學科技學院實驗報告

2、

3、實驗名稱算法設計與分析課程名稱算法設計與分析

4、

5、專業(yè)班級：計算機10k1學生姓名：孫剛學號：101909010121成績：指導教師：牛為華實驗日期：2012-11華北電力大學實驗報告一,實驗內(nèi)容0-1背包問題問題描述：假設有n個物品，用Xi表示第i個物品入選與否，諾等于1表示入選，要是等于0，則表示不入選。用Pi表示物品的價值，Wi表示物品的體積，背包的體積為C，求：在不超過背包體積的前提下，讓背包的所裝物品的價值最大。N后問題問題描述：要求在一個n*n的棋盤上放置n個皇后，使

6、得它們彼此不受攻擊。一個皇后可以攻擊與之處在同一行或同一列或同一斜線上的任何其他棋子。二，實驗步驟對于0-1背包問題，有兩種假設去解決他。假設一：求每個物品的單位體積價值，再從大到小網(wǎng)體積C里裝，但問題是可能會裝不滿或者裝不下，所以假設一可以排除。假設二：用完全二叉樹去窮舉，但時間復雜度為指數(shù)級，也不可取。現(xiàn)在，（1）設X1=0；A2到An選諾干物品體積之和不超過C，求最大價值之和。（2）設X2=1；A2到An選諾干物品體積之和不超過C-W1求最大價值之和。第頁共頁華北電力大學實驗報告M【i】【j】=M【i+

7、1】【j】Xi=0；M【i】【j】=M【i+1】【j-Wi】+PiXi=1取這兩個中較大的一個，出口：M【n】【j】=PnWn≤jM【n】【j】=0Wn＞j算法描述如下：voidKnapsack(intv[],intw[],intc,intn,intm[6][N]){???inti,j,jMax,k;???jMax=(w[n]-1???for(i=0;i<=jMax;i++)???{??????m[n][i]=0;???}for(i=w[n];i<=c;i++)???{??????m[

8、n][i]=v[n];???}?for(i=n-1;i>1;i--)???{??????jMax=(w[i]-1??????for(j=0;j<=jMax;j++)??????{?????????m[i][j]=m[i+1][j];??????}??????for(j=w[i];j<=c;j++)??????{?????????k=j-w[i];?????????if(m[i+1][j]????????????m[i][j]=m[i+

9、1][k]+v[i];?????????else????????????m[i][j]=m[i+1][j];??????}???}??m[1][c]=m[2][c];???if(c>=w[1])???{??????k=c-w[1];?????第頁共頁華北電力大學實驗報告?m[1][c]=(m[2][c]>m[2][k]+v[1])?m[2][c]:m[2][k]+v[1];???}}對與n皇后問題問題的解可表示為x[1:n]，表示皇后i放在棋盤的第i行的第x[i]列。a)x[i]≠x[j],i≠j：不允許將任

10、何兩個皇后放在同一列上；b)

11、j-i

12、≠

13、x[j]-x[i]

14、:不允許兩個皇后位于同一條斜線上。問題的解空間的形式為：要找出”四皇后”問題的解，最可靠的方法就是把各種情況全部檢核一遍，將符合條件A的解找出來。但這樣做，你要有相當耐心才行，這是很費時的。采用回溯算法進行求解，在搜索的過程中，將不滿足條件要求的分支樹減去，可以有效的降低算法的時間復雜性。算法描述如下：classQueen{friendintnQueen(int);private:boolPlace(k);voidBacktrack(intt);i

15、ntn;//皇后個數(shù)int*x;//當前解longsum;//當前已找到的可行方案數(shù)第頁共頁華北電力大學實驗報告};boolQueen::Place(intk){for(intj=1;j

16、

17、(x[j]==x[k]))returnfalse;returntrue;}voidQueen::Backtrack(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtr

18、ack(t+1);}}intnQueen(intn){Queenx;x.n=n;x.sum=0;int*p=newint[n+1];for(inti=0;i<=n;i++)p[i]=0;x.x=p;x.Backtrack(1);delete[]p;returnx.sum;}三，實驗結果0-1背包第頁共頁華北電力大學實驗報告N皇后問題：第頁共頁華北電力大學實驗報告第頁共頁華北電力大學實驗報告四實驗心得