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

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

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