C++常用經(jīng)典算法及其實現(xiàn)

C++常用經(jīng)典算法及其實現(xiàn)

(總20頁)-CAL-FENGHAI.-(YICAI)-CompanyOne1-CAL-本頁僅作為文檔封面，使用請直接刪除#qsort(1,t);//對t條邊按權值大小按從小到大的次序進行快速排序for(inti=1;i<=t;i++){intx1=getfather(elist[i].from);//取第i條邊的起點所在的樹的根intx2=getfather(elist[i].to);//取第i條邊的終點所在的樹的根if(x1!=x2){sum++;merge(x1,x2);ans十=elist[i].w;}//不在同一個集合，合并，即第i條邊可以選取。if(sum>n-1)break;//已經(jīng)確定了口-1條邊了，最小生成樹已經(jīng)生成了，可以提前退出循環(huán)了}if(sum<n-1)cout<<"Impossible"<<endl;//從t條邊中無法確定n-1條邊，說明無法生成最小生成樹elsecout<<ans<<endl;}克魯斯卡爾算法，只用了邊集數(shù)組，沒有用到圖的鄰接矩陣，因此當圖的結點數(shù)比較多的時候，輸入數(shù)據(jù)又是邊的信息時，就要考慮用Kruscal算法。對于島國問題，我們就要選擇此算法，如果用Prim算法，還要開一個二維的數(shù)組來表示圖的鄰接矩陣，對于10000個點的數(shù)據(jù)，顯然在空間上是無法容忍的。二十一、Floyed算法voidfloyed(void)//a[i][j]表示結點i到結點j的最短路徑長度，初始時值為<IJ>的權值。{for(intk=1;k<=n;k++)〃枚舉中間加入的結點不超過K時f[i][j]最短路徑長度，K相當DP中的階段for(inti=1;i<=n;i++)//i，j是結點i到結點J，相當于DP中的狀態(tài)for(intj=1;j<=n;j++)if(a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j];//這是決策，加和不加中間點，取最小的值}弗洛伊德算法適合于求沒有負權回路的圖的最短路徑長度，利用FLOYED算法，可寫出判斷結點i和結點J是否連通的算法。二十二、01背包問題n為物品的數(shù)量，w[i]表示第i個物品的重量，c[i]表示第i個物品的價值，v為背包的最大重量。有狀態(tài)轉移方程f[i]j]=max{f[i-1]j],f[i-1]j-w[i]]+c[i]}。f[i][j]表示前i個物品，在背包載重為j時獲得的最大價值。顯然f[n][v]即為所求。邊界條件為f[0][s]=0,s=0,1，…,v。for(inti=1;i<=n;i++)//枚舉階段for(int)=0力<=丫力++)//枚舉狀態(tài)，當然此處也可寫成：for(intj=v;j>=0;j--){f[i][j]=f[i-1][j];//不選第i個物品if(f[i][j]<f[iT][j-w[i]]+c[i])f[i][j]=f[iT][j-w[i]]+c[i];//選第i個物品}cout<<f[n][v]<<endl;//輸出結果。優(yōu)化：用一維數(shù)組實現(xiàn)，把第i-1階段和第i階段數(shù)據(jù)存在一塊。for(inti=1;i<=n;i++)//枚舉階段for(intj=丫力>=0力一)//枚舉狀態(tài)，當然此處也可寫成:for(intj=v;j>=0;j--){f[j]=f[j];//不選第i個物品，可省略此語句。if((j>w[i])&&(f[j]<f[j-w[i]]+c[i]))f[j]=f[j-w[i]]+c[i];〃選第i個物品}cout<<f[v]<<endl;//輸出結果。對比優(yōu)化前后，我們不難發(fā)現(xiàn)，優(yōu)化后的代碼實際上就是在原來基本的代碼基礎上，減少了階段這一維，同時在枚舉狀態(tài)時，為了保證結果的正確性，枚舉的順序只能是v到0，而不能是0到v。大家細想一下為什么？就是保證在求第i階段j狀態(tài)時，f[j-w[i]]為第i-1階段的值。進一步優(yōu)化，在上面代碼中，枚舉狀態(tài)時，還可以寫成for(intj=vj>=w[i]j--)，此時下面的判斷條件j>=w[i]就可以省略了。二十三、完全背包問題和01背包問題不同的是，完全背包，對于任何一個物品i,只要背包重量允許，可以多次選取，也就是在決策上，可以選0個，1個，2個，…，v/w[i]個。狀態(tài)轉移方程f[i][j]=max{f[i-1][j],f[i-1][j-w[i]]+c[i]，f[i-1][j-2*w[i]]+2*c[i]，…，f[i-1][j-k*w[i]]+k*c[i]}。k=0，1,2,…，v/w[i]。f[i][j]表示前i個物品，在背包載重為j時獲得的最大價值。顯然f[n][v]即為所求。邊界條件為f[0][s]=0,s=0,1，…,v。for(inti=1;i<=n;i++)//枚舉階段for(int)=0力<=丫力++)//枚舉狀態(tài)，當然此處也可寫成：for(intj=v;j>=0;j--){f[i][j]=f[i-1][j];//k=0的情況作為f[i][j]的初始值，然后在k=1,2，…,v/w[i]中找最大值for(intk=1;k<=v/w[i];k++)if(f[i][j]<f[i-1][j-k*w[i]]+k*c[i])f[i][j]=f[i-1][j-k*w[i]]+k*c[i];/選第i個物品}cout<<f[n][v]<<endl;//輸出結果。二十四、多屬性背包問題二十五、多背包問題二十六、最長不降(上升)子序列問題f[i]表示從第1個數(shù)開始，以第i個數(shù)結尾的最長遞增子序列。狀態(tài)轉移方程：f[i]=max{f[j]}+1(1WjWiT,1WiWn,a[i]三a[j])臨界狀態(tài)：f[1]=1；二十七、最長公共子序列問題f[i][j]表示第一個串前i