《2022年完整word版,C++常用經(jīng)典算法及其實(shí)現(xiàn)要點(diǎn)》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《2022年完整word版,C++常用經(jīng)典算法及其實(shí)現(xiàn)要點(diǎn)（22頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、常用算法經(jīng)典代碼（C+版）一、快速排序void qsort(int x,int y)/待排序的數(shù)據(jù)存放在a1.an數(shù)組中int h=x,r=y;int m=a(x+y)1;/取中間的那個(gè)位置的值while(hr)while(ahm)r-;/比中間那個(gè)位置的值大，循環(huán)直到找一個(gè)比中間那個(gè)值小的if(h=r)int temp=ah;/如果此時(shí)hx)qsort(x,r);/注意此處，尾指針跑到前半部分了 if(hy)qsort(h,y);/注意此處，頭指針跑到后半部分了 調(diào)用：qsort(1,n)即可實(shí)現(xiàn)數(shù)組a 中元素有序。適用于n 比較大的排序二、冒泡排序void paopao(void)/待排序

2、的數(shù)據(jù)存放在a1.an數(shù)組中for(int i=1;in;i+)/控制循環(huán)（冒泡）的次數(shù)，n 個(gè)數(shù)，需要n-1 次冒泡for(int j=1;j=n-i;j+)/相鄰的兩兩比較if(ajaj+1)int temp=aj;aj=aj+1;aj+1=temp;或者void paopao(void)/待排序的數(shù)據(jù)存放在a1.an數(shù)組中精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 1 頁(yè)，共 22 頁(yè)for(int i=1;i=1;j-)/相鄰的兩兩比較if(ajaj+1)int temp=aj;aj=aj+1;aj+1=temp;調(diào)用：paopao()，適用于n 比較小的排序三、桶排序void bucketso

3、rt(void)/a的取值范圍已知。如a=cmax。memset(tong,0,sizeof(tong);/桶初始化for(int i=1;ia;tonga+;/相應(yīng)的桶號(hào)計(jì)數(shù)器加1 for(int i=1;i0)/當(dāng)桶中裝的樹(shù)大于0，說(shuō)明 i 出現(xiàn)過(guò) tongi 次，否則沒(méi)出現(xiàn)過(guò)i while(tongi!=0)tongi-;couti ;桶排序適用于那些待排序的關(guān)鍵字的值在已知范圍的排序。四、合（歸）并排序void merge(int l,int m,int r)/合并 l,m 和m+1,r兩個(gè)已經(jīng)有序的區(qū)間 int b101;/借助一個(gè)新的數(shù)組B，使兩個(gè)有序的子區(qū)間合并成一個(gè)有序的區(qū)間，

4、b 數(shù)組的大小要注意精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 2 頁(yè)，共 22 頁(yè)int h,t,k;k=0;/用于新數(shù)組B 的指針h=l;t=m+1;/讓 h 指向第一個(gè)區(qū)間的第一個(gè)元素，t 指向第二個(gè)區(qū)間的第一個(gè)元素。while(h=m)&(t=r)/在指針 h 和 t 沒(méi)有到區(qū)間尾時(shí)，把兩個(gè)區(qū)間的元素抄在新數(shù)組中k+;/新數(shù)組指針加1 if(ahat)bk=ah;h+;/抄第一個(gè)區(qū)間元素到新數(shù)組elsebk=at;t+;/抄第二個(gè)區(qū)間元素到新數(shù)組 while(h=m)k+;bk=ah;h+;/如果第一個(gè)區(qū)間沒(méi)有抄結(jié)束，把剩下的抄在新數(shù)組中while(t=r)k+;bk=at;t+;/如果第二個(gè)區(qū)

5、間沒(méi)有抄結(jié)束，把剩下的抄在新數(shù)組中for(int o=1;o=y)return;mid=(x+y)/2;/求x,y 區(qū)間，中間的那個(gè)點(diǎn)mid,mid把 x,y 區(qū)間一分為二mergesort(x,mid);/對(duì)前一段進(jìn)行二路歸并mergesort(mid+1,y);/對(duì)后一段進(jìn)行二路歸并merge(x,mid,y);/把已經(jīng)有序的前后兩段進(jìn)行合并 歸并排序應(yīng)用了分治思想，把一個(gè)大問(wèn)題，變成兩個(gè)小問(wèn)題。二分是分治的思想。精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 3 頁(yè)，共 22 頁(yè)五、二分查找int find(int x,int y,int m)/在x,y 區(qū)間查找關(guān)鍵字等于m 的元素下標(biāo) int he

6、ad,tail,mid;head=x;tail=y;mid=(x+y)/2);/取中間元素下標(biāo)if(amid=m)return mid;/如果中間元素值為m 返回中間元素下標(biāo)mid if(headtail)return 0;/如果 xy，查找失敗，返回0 if(mamid)/如果 m 比中間元素大，在后半?yún)^(qū)間查找，返回后半?yún)^(qū)間查找結(jié)果return find(mid+1,tail);else/如果 m 比中間元素小，在前半?yún)^(qū)間查找，返回后前區(qū)間查找結(jié)果return find(head,mid-1);六、高精度加法#include#include using namespace std;int m

7、ain()string str1,str2;int a250,b250,len;/數(shù)組的大小決定了計(jì)算的高精度最大位數(shù)int i;memset(a,0,sizeof(a);memset(b,0,sizeof(b);cinstr1str2;/輸入兩個(gè)字符串a(chǎn)0=str1.length();/取得第一個(gè)字符串的長(zhǎng)度f(wàn)or(i=1;i=a0;i+)/把第一個(gè)字符串轉(zhuǎn)換為整數(shù)，存放在數(shù)組a 中ai=str1a0-i-0;b0=str2.length();/取得第二個(gè)字符串長(zhǎng)度f(wàn)or(i=1;ib0?a0:b0);/取兩個(gè)字符串最大的長(zhǎng)度f(wàn)or(i=1;i1)len-;for(i=len;i=1;i-)

8、coutai;return 0;注意：兩個(gè)數(shù)相加，結(jié)果的位數(shù)，應(yīng)該比兩個(gè)數(shù)中大的那個(gè)數(shù)多一位。七、高精度減法#include using namespace std;int compare(string s1,string s2);int main()string str1,str2;int a250,b250,len;int i;memset(a,0,sizeof(a);memset(b,0,sizeof(b);精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 5 頁(yè)，共 22 頁(yè)cinstr1str2;a0=str1.length();for(i=1;i=a0;i+)ai=str1a0-i-0;b0=st

9、r2.length();for(i=1;i=b0;i+)bi=str2b0-i-0;if(compare(str1,str2)=0)/大于等于，做按位減，并處理借位。for(i=1;i=a0;i+)ai-=bi;if(ai1)a0-;for(i=a0;i=1;i-)coutai;coutendl;else cout-;/小于就輸出負(fù)號(hào)for(i=1;i=b0;i+)/做按位減，大的減小的bi-=ai;if(bi1)b0-;精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 6 頁(yè)，共 22 頁(yè)for(i=b0;i=1;i-)coutbi;couts2.length()return 0;/先比較長(zhǎng)度，哪個(gè)字符串長(zhǎng)

10、，對(duì)應(yīng)的那個(gè)數(shù)就大if(s1.length()s2.length()return 1;for(int i=0;is2i)return 0;if(s1is2i)return 1;return 0;/如果長(zhǎng)度相同，每一位也一樣，就返回0，說(shuō)明相等 做減法時(shí)，首先要判斷兩個(gè)字符串的大小，決定是否輸出負(fù)號(hào)，然后就是按位減法，注意處理借位。八、高精度乘法#include#include using namespace std;int main()精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 7 頁(yè)，共 22 頁(yè) string str1,str2;int a250,b250,c500,len;/250位以?xún)?nèi)的兩個(gè)數(shù)相

11、乘int i,j;memset(a,0,sizeof(a);memset(b,0,sizeof(b);cinstr1str2;a0=str1.length();for(i=1;i=a0;i+)ai=str1a0-i-0;b0=str2.length();for(i=1;i=b0;i+)bi=str2b0-i-0;memset(c,0,sizeof(c);for(i=1;i=a0;i+)/做按位乘法同時(shí)處理進(jìn)位，注意循環(huán)內(nèi)語(yǔ)句的寫(xiě)法。for(j=1;j1)len-;/為什么此處要len1?for(i=len;i=1;i-)coutci;return 0;精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 8 頁(yè)，

12、共 22 頁(yè)注意：兩個(gè)數(shù)相乘，結(jié)果的位數(shù)應(yīng)該是這兩個(gè)數(shù)的位數(shù)和減1。優(yōu)化：萬(wàn)進(jìn)制#include#include using namespace std;void num1(int s,string st1);int a2501,b2501,c5002;/此處可以進(jìn)行2500 位萬(wàn)進(jìn)制乘法，即 10000 位十進(jìn)制乘法。Int main()string str1,str2;int len;cinstr1str2;memset(a,0,sizeof(a);memset(b,0,sizeof(b);memset(c,0,sizeof(c);num1(a,str1);/把 str1 從最低位開(kāi)始，每

13、4 位存放在數(shù)組a 中num1(b,str2);/把 str2 從最低位開(kāi)始，每4 位存放在數(shù)組b 中for(int i=1;i=a0;i+)/作按位乘法并處理進(jìn)位，此處是萬(wàn)進(jìn)制進(jìn)位for(int j=1;j1)len-;/去掉高位的0，并輸出最高位 cout=1;i-)/把剩下來(lái)的每一位還原成4 位輸出精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 9 頁(yè)，共 22 頁(yè) if(ci1000)cout 0;if(ci100)cout 0;if(ci10)cout 0;coutci;cout=0;i-)/從最低位開(kāi)始，處理每一位 if(count%4=0)sk+=(st1i-0)*1000;if(i!=0)k

14、+;if(count%4=1)sk=(st1i-0);if(count%4=2)sk+=(st1i-0)*10;if(count%4=3)sk+=(st1i-0)*100;count+;s0=k;/存放數(shù)組的位數(shù)，就是按4 位處理后的萬(wàn)進(jìn)制數(shù)的位數(shù)。Return;九、高精度除法（沒(méi)講）十、篩選法建立素?cái)?shù)表void maketable(int x)/建立 X 以?xún)?nèi)的素?cái)?shù)表prim，primi 為 0，表示 i 為素?cái)?shù)，為1 表示不是質(zhì)數(shù)精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 10 頁(yè)，共 22 頁(yè) memset(prim,0,sizeof(prim);/初始化質(zhì)數(shù)表 prim0=1;prim1=1;p

15、rim2=0;/用篩選法求X 以?xún)?nèi)的質(zhì)數(shù)表 for(int i=2;i=x;i+)if(primi=0)int j=2*i;while(j=x)primj=1;j=j+i;對(duì)于那些算法中，經(jīng)常要判斷素?cái)?shù)的問(wèn)題，建立一個(gè)素?cái)?shù)表，可以達(dá)到一勞永逸的目的。十一、深度優(yōu)先搜索void dfs(int x)以圖的深度優(yōu)先遍歷為例。coutx ;訪(fǎng)問(wèn) x 頂點(diǎn)作已訪(fǎng)問(wèn)的標(biāo)記對(duì)與頂點(diǎn)x 相鄰而又沒(méi)訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)k 進(jìn)行深度優(yōu)先搜索。if(axk=1)&(visitedk=0)dfs(k);十二、廣度優(yōu)先搜索void bfs(void)/按廣度優(yōu)先非遞歸遍歷圖G，n 個(gè)頂點(diǎn)，編號(hào)為1.n。注：圖不一定是連通的/

16、使用輔助隊(duì)列Q 和訪(fǎng)問(wèn)標(biāo)記數(shù)組visited。for(v=1;v=n;v+)visitedv=0；/標(biāo)記數(shù)組初始化for(v=1;v=n;v+)精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 11 頁(yè)，共 22 頁(yè)if(visitedv=0)/v 尚未訪(fǎng)問(wèn)int h=1,r=1;/置空的輔助隊(duì)列q visitedv=1；/頂點(diǎn) v,作訪(fǎng)問(wèn)標(biāo)記coutv ;/訪(fǎng)問(wèn)頂點(diǎn)v qr=v；/v 入隊(duì)列while(h=r)/當(dāng)隊(duì)列非空時(shí)循環(huán) int tmp=qh;/隊(duì)頭元素出隊(duì)，并賦值給tmp for(int j=1;j=n;j+)if(visitedj=0)&(atmpj=1)/j為 tmp 的尚未訪(fǎng)問(wèn)的鄰接頂點(diǎn) v

17、isitedj=1;對(duì) j 作訪(fǎng)問(wèn)標(biāo)記coutj ;訪(fǎng)問(wèn) j r+;/隊(duì)尾指針加1 qr=j;/j入隊(duì) /end-if h+;/end-while 十三、二叉樹(shù)的前序、中序和后序遍歷void preorder(int x)/二叉樹(shù)的先序遍歷 if(x=0)return;coutx;/先訪(fǎng)問(wèn)根preorder(ax.ld);/再先序遍歷根的左子樹(shù)preorder(ax.rd);/最后先序遍歷根的右子樹(shù) 精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 12 頁(yè)，共 22 頁(yè)void inorder(int x)/二叉樹(shù)的中序遍歷 if(x=0)return;preorder(ax.ld);/先中序遍歷根的左子樹(shù)

18、coutx;/再訪(fǎng)問(wèn)根preorder(ax.rd);/最后中序遍歷根的右子樹(shù) void reorder(int x)/二叉樹(shù)的后序遍歷 if(x=0)return;preorder(ax.ld);/先后序遍歷根的左子樹(shù)preorder(ax.rd);/再后序遍歷根的右子樹(shù)coutx;/最后訪(fǎng)問(wèn)根 十四、樹(shù)轉(zhuǎn)換為二叉樹(shù)算法十五、二叉排序樹(shù)十六、哈夫曼樹(shù)void haff(void)/構(gòu)建哈夫曼樹(shù) for(int i=n+1;i=2*n-1;i+)/依次生成 n-1 個(gè)結(jié)點(diǎn)int l=fmin(i-1);/查找權(quán)值最小的結(jié)點(diǎn)的編號(hào)l ai.lchild=l;/把 l 作為結(jié)點(diǎn)i 的左孩子al.f

19、ather=i;/把 l 的父結(jié)點(diǎn)修改為i 精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 13 頁(yè)，共 22 頁(yè)int r=fmin(i-1);/查找次小權(quán)值的編號(hào)r ai.rchild=r;/把 l 作為結(jié)點(diǎn)i 的右孩子ar.father=i;/把 r 的父結(jié)點(diǎn)修改為i ai.da=al.da+ar.da;/合并 l,j 結(jié)點(diǎn)，生成新結(jié)點(diǎn)i int fmin(int k)/在 1 到 K 中尋找最小的權(quán)值的編號(hào) int mins=0;for(int s=1;sas.da)&(as.father=0)/as.father=0,說(shuō)明這個(gè)結(jié)點(diǎn)還不是別個(gè)結(jié)點(diǎn)mins=s;/的孩子，不等于0 說(shuō)明這個(gè)結(jié)點(diǎn)已經(jīng)用過(guò)

20、。return mins;void inorder(int x)/遞歸生成哈夫曼編碼 if(ax.father=0)ax.code=”“;/根結(jié)點(diǎn)if(aax.father.lchild=x)ax.code=aax.father.code+0;if(aax.father.rchild=x)ax.code=aax.father.code+1;if(ax.lchild!=0)inorder(ax.lchild);/遞歸生成左子樹(shù)if(ax.lchild=0)&(ax.rchild=0)/輸出葉子結(jié)點(diǎn)coutax.da:ax.codeendl;if(ax.rchild!=0)inorder(ax.r

21、child);/遞歸生成右子樹(shù) 十七、并查集int getfather(int x)/非遞歸求 X 結(jié)點(diǎn)的根結(jié)點(diǎn)的編號(hào)while(x!=fatherx)精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 14 頁(yè)，共 22 頁(yè)x=fatherx;return x;int getfather(int x)/遞歸求 X 結(jié)點(diǎn)的根結(jié)點(diǎn)的編號(hào)if(x=fatherx)return x;else return getfather(fatherx);int getfather(int x)/非遞歸求 X 結(jié)點(diǎn)的根結(jié)點(diǎn)編號(hào)同時(shí)進(jìn)行路徑壓縮int p=x;while(p!=fatherp)/循環(huán)結(jié)束后，P即為根結(jié)點(diǎn)p=fath

22、erp;while(x!=fatherx)/從 X 結(jié)點(diǎn)沿 X 的父結(jié)點(diǎn)進(jìn)行路徑壓縮int temp=fatherx;/暫存 X沒(méi)有修改前的父結(jié)點(diǎn)fatherx=p;/把 X 的父結(jié)點(diǎn)指向P x=temp;return p;int getfather(int x)/遞歸求 X 結(jié)點(diǎn)的根結(jié)點(diǎn)編號(hào)同時(shí)進(jìn)行路徑壓縮if(x=fatherx)return x;else int temp=getfather(fatherx);fatherx=temp;return temp;精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 15 頁(yè)，共 22 頁(yè) void merge(int x,int y)/合并 x,y 兩個(gè)結(jié)點(diǎn)

23、int x1,x2;x1=getfather(x);/取得 X 的父結(jié)點(diǎn)x2=getfather(y);/取得 Y 的父結(jié)點(diǎn)if(x1!=x2)fatherx1=x2;/兩個(gè)父結(jié)點(diǎn)不同的話(huà)就合并，注意：合并的是X，Y 兩個(gè)結(jié)點(diǎn)的根。十八、Prime算法void prime(void)/prim算法求最小生成樹(shù)，elisti 是邊集數(shù)組，aij 為 的權(quán)值。edge為結(jié)構(gòu)體類(lèi)型。for(int i=1;i=n-1;i+)/初始化結(jié)點(diǎn)1 到其它 n-1 個(gè)結(jié)點(diǎn)形成的邊集elisti.from=1;elisti.to=i+1;elisti.w=a1i+1;for(int i=1;i=n-1;i+)/

24、依次確定n-1 條邊int m=i;for(int j=i+1;j=n-1;j+)/確定第 i 條邊時(shí)，依次在i+1 至 n-1 條邊中找最小的那條邊if(elistj.welistm.w)m=j;if(m!=i)/如果最小的邊不是第i 條邊就交換edge tmp=elisti;elisti=elistm;elistm=tmp;for(int j=i+1;jaelisti.toelistj.to)elistj.w=aelisti.toelistj.to;for(int i=1;i=n-1;i+)/求最小生成樹(shù)的值精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 16 頁(yè)，共 22 頁(yè)ans=ans+elist

25、i.w;如果要求出哪些邊構(gòu)成最小生成樹(shù)，在更新第i+1至 n-1 條邊到已經(jīng)生成的樹(shù)中最小距離時(shí)(上面代碼中加粗的部分)，還要加上elistj.from=elisti.to;語(yǔ)句，即在更新權(quán)值時(shí)，還應(yīng)該更新起點(diǎn)。Prime算法適用于頂點(diǎn)不是太多的稠密圖，如果對(duì)于頂點(diǎn)數(shù)較多的稀疏圖，就不太適用了。十九、Dijkstra算法void dijkstra(int x)/求結(jié)點(diǎn) x 到各個(gè)結(jié)點(diǎn)的最短路徑 memset(vis,0,sizeof(vis);/初始化，visi 0 表示源點(diǎn)到結(jié)點(diǎn)i 未求，否則已求visx=1;prex=0;/初始化源點(diǎn)。for(int i=1;i=n;i+)/對(duì)其它各點(diǎn)初始

26、化。if(i!=x)disi=gxi;prei=x;for(int i=1;i=n-1;i+)/對(duì)于 n 個(gè)結(jié)點(diǎn)的圖，要求x 到其它 n-1 個(gè)結(jié)點(diǎn)的最短距離 int m=big;/虛擬一個(gè)最大的數(shù)big=99999999;int k=x;for(int j=1;jdisj)m=disj;k=j;精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 17 頁(yè)，共 22 頁(yè) visk=1;/思考：如果k=X 說(shuō)明什么？說(shuō)明后面的點(diǎn)，無(wú)解。for(int j=1;j=n;j+)/用當(dāng)前找的結(jié)點(diǎn)更新未求結(jié)點(diǎn)到X 的最短路徑 if(visj=0)&(disk+gkj1.w;while(hr)while(elisth.wm

27、)r-;if(h=r)edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-;if(xr)qsort(x,r);if(hy)qsort(h,y);int getfather(int x)/找根結(jié)點(diǎn)，并壓縮路徑，此處用遞歸實(shí)現(xiàn)的。if(x=fatherx)return x;else int f=getfather(fatherx);精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 18 頁(yè)，共 22 頁(yè)fatherx=f;return f;void merge(int x,int y)/合并 x,y 結(jié)點(diǎn)，在此題中的x,y 為兩個(gè)根結(jié)點(diǎn)。fatherx=y;void kru

28、scal(void)int sum=0,ans=0;qsort(1,t);/對(duì) t 條邊按權(quán)值大小按從小到大的次序進(jìn)行快速排序for(int i=1;in-1)break;/已經(jīng)確定了n-1條邊了，最小生成樹(shù)已經(jīng)生成了，可以提前退出循環(huán)了 if(sumn-1)coutImpossibleendl;/從 t 條邊中無(wú)法確定n-1條邊，說(shuō)明無(wú)法生成最小生成樹(shù)else coutansendl;克魯斯卡爾算法，只用了邊集數(shù)組，沒(méi)有用到圖的鄰接矩陣，因此當(dāng)圖的結(jié)點(diǎn)數(shù)比較多的時(shí)候，輸入數(shù)據(jù)又是邊的信息時(shí)，就要考慮用Kruscal算法。對(duì)于島國(guó)問(wèn)題，我們就要選擇此算法，如果用Prim算法，還要開(kāi)一個(gè)二維的數(shù)

29、組來(lái)表示圖的鄰接矩陣，對(duì)于10000個(gè)點(diǎn)的數(shù)據(jù)，顯然在空間上是無(wú)法容忍的。精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 19 頁(yè)，共 22 頁(yè)二十一、Floyed算法void floyed(void)/aij表示結(jié)點(diǎn)i 到結(jié)點(diǎn) j 的最短路徑長(zhǎng)度，初始時(shí)值為的權(quán)值。for(int k=1;k=n;k+)/枚舉中間加入的結(jié)點(diǎn)不超過(guò)K 時(shí) fij最短路徑長(zhǎng)度，K 相當(dāng)DP 中的階段 for(int i=1;i=n;i+)/i，j 是結(jié)點(diǎn) i 到結(jié)點(diǎn) J，相當(dāng)于DP 中的狀態(tài)for(int j=1;jaik+akj)aij=aik+akj;/這是決策，加和不加中間點(diǎn)，取最小的值 弗洛伊德算法適合于求沒(méi)有負(fù)權(quán)回路

30、的圖的最短路徑長(zhǎng)度，利用FLOYED 算法，可寫(xiě)出判斷結(jié)點(diǎn) i 和結(jié)點(diǎn) J 是否連通的算法。二十二、01 背包問(wèn)題n 為物品的數(shù)量，wi 表示第 i 個(gè)物品的重量，ci 表示第 i 個(gè)物品的價(jià)值，v 為背包的最大重量。有狀態(tài)轉(zhuǎn)移方程fij=maxfi-1j,fi-1j-wi+ci。fij表示前 i 個(gè)物品，在背包載重為 j 時(shí)獲得的最大價(jià)值。顯然fnv即為所求。邊界條件為f0s=0,s=0,1,v。for(int i=1;i=n;i+)/枚舉階段 for(int j=0;j=0;j-)fij=fi-1j;/不選第 i 個(gè)物品if(fijfi-1j-wi+ci)fij=fi-1j-wi+ci;/

31、選第 i 個(gè)物品 coutfnvendl;/輸出結(jié)果。優(yōu)化：用一維數(shù)組實(shí)現(xiàn)，把第i-1 階段和第i 階段數(shù)據(jù)存在一塊。for(int i=1;i=0;j-)/枚舉狀態(tài)，當(dāng)然此處也可寫(xiě)成:for(int j=v;j=0;j-)精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 20 頁(yè)，共 22 頁(yè) fj=fj;/不選第 i 個(gè)物品，可省略此語(yǔ)句。if(jwi)&(fjfj-wi+ci)fj=fj-wi+ci;/選第 i 個(gè)物品 coutfv=wi;j-)，此時(shí)下面的判斷條件j=wi就可以省略了。二十三、完全背包問(wèn)題和 01 背包問(wèn)題不同的是，完全背包，對(duì)于任何一個(gè)物品i，只要背包重量允許，可以多次選取，也就是在

32、決策上，可以選0 個(gè)，1 個(gè)，2 個(gè)，v/wi 個(gè)。狀態(tài)轉(zhuǎn)移方程fij=maxfi-1j,fi-1j-wi+ci，fi-1j-2*wi+2*ci，fi-1j-k*wi+k*ci。k=0，1，2，v/wi。fij表示前 i 個(gè)物品，在背包載重為j時(shí)獲得的最大價(jià)值。顯然fnv即為所求。邊界條件為f0s=0,s=0,1,v。for(int i=1;i=n;i+)/枚舉階段 for(int j=0;j=0;j-)fij=fi-1j;/k=0的情況作為fij的初始值，然后在 k=1,2,v/wi中找最大值for(int k=1;k=v/wi;k+)if(fijfi-1j-k*wi+k*ci)fij=fi

33、-1j-k*wi+k*ci;/選第 i 個(gè)物品 coutfnvendl;/輸出結(jié)果。二十四、多屬性背包問(wèn)題精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 21 頁(yè)，共 22 頁(yè)二十五、多背包問(wèn)題二十六、最長(zhǎng)不降（上升）子序列問(wèn)題 fi 表示從第1 個(gè)數(shù)開(kāi)始，以第i 個(gè)數(shù)結(jié)尾的最長(zhǎng)遞增子序列。狀態(tài)轉(zhuǎn)移方程：fi=maxfj+1（1j i-1，1i n，ai aj）臨界狀態(tài)：f1=1;二十七、最長(zhǎng)公共子序列問(wèn)題fij 表示第一個(gè)串前i 個(gè)字符和第二個(gè)串前j 個(gè)字符的最長(zhǎng)公共子序列數(shù)。狀態(tài)轉(zhuǎn)移方程：fi-1j-1 (若 ai=bj)fij=maxfi-1j,fij-1+1 (若 ai bj)臨界狀態(tài):f0j=0，fi0=0 精選學(xué)習(xí)資料 -名師歸納總結(jié)-第 22 頁(yè)，共 22 頁(yè)