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

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

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

2、

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

4、

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

6、一列或同一斜線上的任何其他棋子。二，實驗步驟對于0-1背包問題，有兩種假設去解決他。假設一：求每個物品的單位體積價值，再從大到小網體積C里裝，但問題是可能會裝不滿或者裝不下，所以假設一可以排除。假設二：用完全二叉樹去窮舉，但時間復雜度為指數級，也不可取?，F在，（1）設X1=0；A2到An選諾干物品體積之和不超過C，求最大價值之和。（2）設X2=1；A2到An選諾干物品體積之和不超過C-W1求最大價值之和。.---M【i】【j】=M【i+1】【j】Xi=0；M【i】【j】=M【i+1】【j-Wi】+PiXi=1取這兩個中較大的一個，出口：M【n】【j】=

7、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[n][i]=v[n];???}?for(i=n-1;i>1;i--)???{??????jMax=(w[i]-1??????for(j=0

8、;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+1][k]+v[i];?????????else????????????m[i][j]=m[i+1][j];??????}???}??m[1][c]=m[2][c];???if(c>=w[1])???{??

9、????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：不允許將任何兩個皇后放在同一列上；b)

10、j-i

11、≠

12、x[j]-x[i]

13、:不允許兩個皇后位于同一條斜線上。問題的解空間的形式為：要找出”四皇后”問題的解，最可靠的方法就是把各種情況全部檢核一遍，將符合條件A的解找出來。但這樣做，你要有相當耐心才行，這是很費時的。采用回溯算法進行求

14、解，在搜索的過程中，將不滿足條件要求的分支樹減去，可以有效的降低算法的時間復雜性。算法描述如下：classQueen{friendintnQueen(int);private:boolPlace(k);voidBacktrack(intt);intn;//皇后個數int*x;//當前解longsum;//當前已找到的可行方案數.---};boolQueen::Place(intk){for(intj=1;j

15、

16、(x[j]==x[k]))returnfalse;returntrue;}

17、voidQueen::Backtrack(intt){if(t>n)sum++;elsefor(inti=1;i<=n;i++){x[t]=i;if(Place(t))Backtrack(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皇后問題：.---.---四實驗心得這次實驗所做的都是老師上課講過的實例

18、，所以實現起來還是相對比較簡單的，但是在做的過程中，我對動態(tài)規(guī)劃法還不是特別的理解，要是讓我自