算法設(shè)計(jì)與分析

1、算法分析與設(shè)計(jì)20132014年度 第1學(xué)期課程學(xué)習(xí)報(bào)告院系：學(xué)號(hào)： 姓名： 任課老師： 成果評(píng)定： 完成日期：2013年 12月 30 日第1章 遞歸與分治在任何可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。問題的規(guī)模越小，解題所需要的計(jì)算時(shí)間也就越少從而比較簡潔處理。要想直接解決一個(gè)較大的問題，有時(shí)是相當(dāng)困難的。分治法的設(shè)計(jì)思想是，講一個(gè)難以解決的大問題，分割成規(guī)模較小的相同問題，以便各個(gè)擊破，分而治之。假如原問題可分割成k個(gè)子問題，1kn，且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使用遞歸技

2、術(shù)供應(yīng)了便利。在這種狀況下，反復(fù)應(yīng)用分之手段，可以使子問題與原問題的類型全都而其規(guī)模卻不斷縮小，最終使子問題縮小到很簡潔求出其解。由此自然導(dǎo)出遞歸算法。并以其為基礎(chǔ)，可以產(chǎn)生了很多高效算法。1.1遞歸的概念直接或間接的調(diào)用自身的算法稱為遞歸算法。用函數(shù)自身給出定義的函數(shù)稱為遞歸函數(shù)。在計(jì)算機(jī)算法設(shè)計(jì)與分析中，遞歸技術(shù)是格外有用的。使用遞歸技術(shù)往往使函數(shù)的定義和算法的描述簡潔且易于理解。1.1.1整數(shù)劃分問題將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+nk，其中n1n2nk1，k1。正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不同劃分個(gè)數(shù)。 例如正整數(shù)6有如下11種不同的劃分： 6；

3、 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。在本例中，假如設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)?？梢越(n,m)的如下遞歸關(guān)系。(1) q(n,1)=1,n³1;當(dāng)最大加數(shù)n1不大于1時(shí)，任何正整數(shù)n只有一種劃分形式，即(2) q(n,m)=q(n,n),mn;最大加數(shù)n1實(shí)際上不能大于n。因此，q(1,m)=1。(3) q(n,n)=1+q(n,n-1);正整數(shù)n的劃分由n1=n的劃分和n1n

4、-1的劃分組成。(4) q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;正整數(shù)n的最大加數(shù)n1不大于m的劃分由n1=m的劃分和n1n-1 的劃分組成。在本例中，假如設(shè)p(n)為正整數(shù)n的劃分?jǐn)?shù)，則難以找到遞歸關(guān)系，因此考慮增加一個(gè)自變量：將最大加數(shù)n1不大于m的劃分個(gè)數(shù)記作q(n,m)。可以建立q(n,m)的如下遞歸關(guān)系。據(jù)此，設(shè)計(jì)計(jì)算去q（n，m）的遞歸算法如下。public static int q(int n ,int m )if(n<1)|(m<1) return 0;if(n=1)|(m=1) return 1;if(n<m) return

5、 q(n,n);If(n=m) return q(n,m- 1)+1;return q(n,m-1)+q(n-m,m) ;1.1.2遞歸小結(jié)優(yōu)點(diǎn)：結(jié)構(gòu)清楚，可讀性強(qiáng)，而且簡潔用數(shù)學(xué)歸納法來證明算法的正確性，因此它為設(shè)計(jì)算法、調(diào)試程序帶來很大便利。缺點(diǎn)：遞歸算法的運(yùn)行效率較低，無論是耗費(fèi)的計(jì)算時(shí)間還是占用的存儲(chǔ)空間都比非遞歸算法要多。1.2分治法的基本思想分治法的基本思想是將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題，這些子問題相互獨(dú)立且與原問題相同。人們從大量實(shí)踐中發(fā)覺，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同。即將一個(gè)問題分成大小相等的k個(gè)子問題的處理方法是行之有效的。這種使子問題

6、規(guī)模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。1.2.1分治法的適用條件分治法所能解決的問題一般具有以下幾個(gè)特征：該問題的規(guī)模縮小到肯定的程度就可以簡潔地解決；該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)利用該問題分解出的子問題的解可以合并為該問題的解；該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題。 這條特征涉及到分治法的效率，假如各子問題是不獨(dú)立的，則分治法要做很多不必要的工作，重復(fù)地解公共的子問題，此時(shí)雖然也可用分治法，但一般用動(dòng)態(tài)規(guī)劃較好。分治法的基本步驟divide-and-c

7、onquer(P) if ( | P | <= n0) adhoc(P); /解決小規(guī)模的問題 divide P into smaller subinstances P1,P2,.,Pk；/分解問題 for (i=1,i<=k,i+) yi=divide-and-conquer(Pi); /遞歸的解各子問題 return merge(y1,.,yk); /將各子問題的解合并為原問題的解 人們從大量實(shí)踐中發(fā)覺，在用分治法設(shè)計(jì)算法時(shí)，最好使子問題的規(guī)模大致相同。即將一個(gè)問題分成大小相等的k個(gè)子問題的處理方法是行之有效的。這種使子問題規(guī)模大致相等的做法是出自一種平衡(balancing)

8、子問題的思想，它幾乎總是比子問題規(guī)模不等的做法要好。1.3 問題描述在一個(gè)2k×2k （k0）個(gè)方格組成的棋盤中，恰有一個(gè)方格與其他方格不同，稱該方格為特殊方格。明顯，特殊方格在棋盤中可能消滅的位置有4k種，因而有4k種不同的棋盤，所示是k=2時(shí)16種棋盤中的一個(gè)。棋盤掩蓋問題（chess cover problem）要求用4種不同外形的L型骨牌掩蓋給定棋盤上除特殊方格以外的全部方格，且任何2個(gè)L型骨牌不得重疊掩蓋。當(dāng)k>0時(shí)，將2k×2k棋盤分割為4個(gè)2k-1×2k-1 子棋盤(a)所示。特殊方格必位于4個(gè)較小子棋盤之一中，其余3個(gè)子棋盤中無特殊方格。為了

9、將這3個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤，可以用一個(gè)L型骨牌掩蓋這3個(gè)較小棋盤的會(huì)合處，如 (b)所示，從而將原問題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤掩蓋問題。遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。 用遞歸與分治求解下面算法中，用整數(shù)型數(shù)組board表示棋盤。board00是棋盤的左上角方格。tile是算法中的一個(gè)全局整形變量，用來表示L型骨牌的編號(hào)，其初始值為0.算法的輸入?yún)?shù)如下：tr：棋盤左上角方格的行號(hào)；tc：棋盤左上角方格的列號(hào)；dr：特殊方格所在的行號(hào)；size：，棋盤規(guī)格為2k×2k。設(shè)T(k)是算法chessBoard掩蓋一個(gè)2k×2k棋盤所需要的時(shí)

10、間。從算法的分割策略可知，T（k）滿足如下遞歸方程解此遞歸方程可得T(K)=O()。由于掩蓋2k×2k棋盤所需要的L型骨牌個(gè)數(shù)為（）/3，故此算法是一個(gè)在漸進(jìn)意義下最優(yōu)的算法。 程序代碼如下所示：public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌號(hào) s = size/2; / 分割棋盤 / 掩蓋左上角子棋盤 if (dr < tr + s && dc < tc + s) / 特殊方格在此棋盤中

11、 chessBoard(tr, tc, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號(hào)L型骨牌掩蓋右下角 boardtr + s - 1tc + s - 1 = t; / 掩蓋其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 掩蓋右上角子棋盤 if (dr < tr + s && dc >= tc + s) / 特殊方格在此棋盤中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盤中無特殊方格 / 用 t 號(hào)L型骨牌掩蓋左下角 boardtr + s - 1tc

12、+ s = t; / 掩蓋其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 掩蓋左下角子棋盤 if (dr >= tr + s && dc < tc + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc, dr, dc, s); else / 用 t 號(hào)L型骨牌掩蓋右上角 boardtr + stc + s - 1 = t; / 掩蓋其余方格 chessBoard(tr+s, tc, tr+s, tc+s-1, s); / 掩蓋右下角子棋盤 if (dr >= tr + s && d

13、c >= tc + s) / 特殊方格在此棋盤中 chessBoard(tr+s, tc+s, dr, dc, s); else / 用 t 號(hào)L型骨牌掩蓋左上角 boardtr + stc + s = t; / 掩蓋其余方格 chessBoard(tr+s, tc+s, tr+s, tc+s, s); 1.4課后習(xí)題設(shè)有N個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽，設(shè)計(jì)一個(gè)滿足以下要求的競賽日程表 （1） 每個(gè)選手必需與其他n-1個(gè)選手各賽一次（2） 每個(gè)選手一天只能賽一次（3） 當(dāng)n 是偶數(shù)，循環(huán)賽進(jìn)行n-1天，當(dāng)n是奇數(shù)，循環(huán)賽進(jìn)行n天分治策略：我們可以將全部的選手分為兩半，則n個(gè)選手的競賽日程表可

14、以通過n/2個(gè)競賽日程表來打算。遞歸地用這種一分為二的策略對(duì)選手進(jìn)行劃分，直選手的到只剩下兩個(gè)選手時(shí)，競賽日程表的制定就變得很簡潔。這時(shí)只要讓這兩個(gè)選手進(jìn)行競賽就可以了。按分治策略，我們可以將全部的選手分為兩半，則n個(gè)選手的競賽日程表可以通過n/2個(gè)選手的競賽日程表來打算。遞歸地用這種一分為二的策略對(duì)選手進(jìn)行劃分，直到只剩下兩個(gè)選手時(shí)，競賽日程表的制定就變得很簡潔。這時(shí)只要讓這兩個(gè)選手進(jìn)行競賽就可以了。代碼部分#include<stdlib.h>#include<stdio.h>int *A; /int *指針數(shù)組，int *schedule; /int數(shù)組，一維數(shù)組保

15、存二維數(shù)組的數(shù)據(jù)int N =1; /問題的規(guī)模。初始化時(shí)會(huì)設(shè)定/isodd:推斷x是否奇數(shù)，是則返回1，否則0int isodd(int x) return x&1;/print:打印賽程void print() int i,j, row, col; if(isodd(N) row=N; col=N+1; else row=N; col=N; printf("第1列是選手編號(hào)n"); for(i=0;i<row; i+) for(j=0;j<col; j+) printf("%4d", Aij); printf("n&qu

16、ot;); /*init：初始化，設(shè)置問題規(guī)模N值，安排內(nèi)存，用schedule指向； 把A構(gòu)造成一個(gè)二維數(shù)組*/void init() int i, n; char line100='0' printf("請(qǐng)輸入選手人數(shù)："); fgets(line,sizeof(line), stdin); N=atoi(line); if(N<=0) exit(-1); if(isodd(N) n=N+1; else n=N; /schedule是行化的二維數(shù)組 schedule=(int *)calloc(n*n, sizeof(int); A=(int *)

17、calloc(n, sizeof(int *); if(!schedule | A=NULL) exit(-2); for(i=0;i<n;i+) /把A等價(jià)為二維數(shù)組 Ai=schedule+i*n; Ai0=i+1;/初始化這個(gè)數(shù)組的第一列 return;/*replaceVirtual:把第m號(hào)虛的選手去掉（換做0）*/void replaceVirtual(int m) int i,j; for(i=0;i<m-1;i+) /行：對(duì)應(yīng)選手號(hào)1m-1 for (j=0;j<=m;j+) /列: 比行要多1 Aij = (Aij=m)?0:Aij; return;/*co

18、pyeven:m為偶數(shù)時(shí)用,由前1組的m位選手的支配，來構(gòu)成第2組m位選手 的賽程支配，以及兩組之間的競賽支配 */void copyeven(int m) if(isodd(m) return; int i,j; for (j=0;j<m;j+) /1. 求第2組的支配（+m） for (i=0;i<m;i+) Ai+mj=Aij+m; for (j=m;j<2*m;j+)/兩組間競賽的支配 for (i=0;i<m;i+) /2. 第1組和第2組 Aij=Ai+mj-m; /把左下角拷貝到右上角 for (i=m;i<2*m;i+) /3. 對(duì)應(yīng)的，第2組和第

19、1組 Aij=Ai-mj-m; /把左上角拷貝到右下角 return;/*copyodd:m為奇數(shù)時(shí)用,由前1組的m位選手的支配，來構(gòu)成第2組m位選手 的賽程支配，以及兩組之間的競賽支配。這時(shí)和m為偶數(shù)時(shí)的 處理有區(qū)分。*/void copyodd(int m) int i,j; for (j=0;j<=m;j+) /1. 求第2組的支配(前m天) for (i=0;i<m;i+)/行 if (Aij!=0) Ai+mj=Aij+m; else /特殊處理：兩個(gè)隊(duì)各有一名選手有空，支配他們競賽 Ai+mj = i+1; Aij = i+m+1; /支配兩組選手之間的競賽(后m-1天

20、)/ for(i=0,j=m+1;j<2*m;j+) Aij = j+1; /2. 1號(hào)選手的后m-1天競賽 A (Aij -1) j = i+1; /3. 他的對(duì)手后m-1天的支配 /以下的取值要依靠于1號(hào)選手的支配，所以之前先支配1號(hào)的賽程 for (i=1;i<m;i+) /第1組的其他選手的后m-1天的支配 for (j=m+1;j<2*m;j+) /2. 觀看得到的規(guī)章一：向下m+12*m循環(huán)遞增 Aij = (Ai-1j+1)%m=0)?Ai-1j+1 :m + (Ai-1j+1)%m; /3. 對(duì)應(yīng)第2組的對(duì)手也要做相應(yīng)的支配 A (Aij-1) j = i+1

21、; return;/*makecopy:當(dāng)前有m位（偶數(shù)）選手，分成兩組，每組由m/2位選手構(gòu)成 由第一組的m/2位選手的支配來構(gòu)成其次組的競賽支配，第一 組與其次組的競賽支配。要區(qū)分m/2為奇數(shù)和偶數(shù)兩種狀況*/void makecopy(int m) if (isodd(m/2) /m/2為奇數(shù) copyodd(m/2); else /m/2為偶數(shù) copyeven(m/2);void tournament(int m) if(m=1) A00=1; return ; else if(isodd(m) /假如m為奇數(shù)，則m+1是偶數(shù) tournament(m+1); /依據(jù)偶數(shù)個(gè)選手來求解

22、 replaceVirtual(m+1); /然后把第m+1號(hào)虛選手置成0 return ; else /m是偶數(shù)， tournament(m/2); /則先支配第1組的m/2人競賽 makecopy(m); /然后依據(jù)算法，構(gòu)造左下、右下、右上、右下的矩陣 return ;/*endprogram:回收安排的內(nèi)存*/void endprogram() free(schedule); free(A); int main() init(); /初始化 tournament(N);/求解 print(); /打印結(jié)果 endprogram(); /回收內(nèi)存 return 0;第2章 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)

23、劃算法與分治法類似，其基本思想是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃法求解的問題，經(jīng)分解得到的子問題往往不是相互獨(dú)立的，若用分治法解這類問題，則分解得到的子問題數(shù)目太多，以至于最終解決原問題需要耗費(fèi)過多的時(shí)間。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了很多次。假如我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避開大量的重復(fù)計(jì)算。為了達(dá)到此目的，可以用一個(gè)表來記錄全部已解決的子問題的答案。這就是動(dòng)態(tài)規(guī)劃法的基本思想。2.1動(dòng)態(tài)規(guī)劃算法的基本要素2.1.1最優(yōu)子結(jié)構(gòu)矩陣連乘計(jì)算次序問題的最優(yōu)解

24、包含著其子問題的最優(yōu)解。這種性質(zhì)稱為最優(yōu)子結(jié)構(gòu)性質(zhì)。在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個(gè)假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致沖突。 利用問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，以自底向上的方式遞歸地從子問題的最優(yōu)解逐步構(gòu)造出整個(gè)問題的最優(yōu)解。最優(yōu)子結(jié)構(gòu)是問題能用動(dòng)態(tài)規(guī)劃算法求解的前提。2.1.2 重疊子問題遞歸算法求解問題時(shí)，每次產(chǎn)生的子問題并不總是新問題，有些子問題被反復(fù)計(jì)算多次。這種性質(zhì)稱為子問題的重疊性質(zhì)。動(dòng)態(tài)規(guī)劃算法，對(duì)每一個(gè)子問題只解一次，而后將其解保存在一個(gè)表格中，當(dāng)再次需要解此子問題時(shí)，只是簡潔地用常數(shù)

25、時(shí)間查看一下結(jié)果。 通常不同的子問題個(gè)數(shù)隨問題的大小呈多項(xiàng)式增長。因此用動(dòng)態(tài)規(guī)劃算法只需要多項(xiàng)式時(shí)間，從而獲得較高的解題效率。2.2實(shí)例分析 2.2.1 計(jì)算最優(yōu)值對(duì)于1ijn不同的有序?qū)?i,j)對(duì)應(yīng)于不同的子問題。因此，不同子問題的個(gè)數(shù)最多只有 由此可見，在遞歸計(jì)算時(shí)，很多子問題被重復(fù)計(jì)算多次。這也是該問題可用動(dòng)態(tài)規(guī)劃算法求解的又一顯著特征。用動(dòng)態(tài)規(guī)劃算法解此問題，可依據(jù)其遞歸式以自底向上的方式進(jìn)行計(jì)算。在計(jì)算過程中，保存已解決的子問題答案。每個(gè)子問題只計(jì)算一次，而在后面需要時(shí)只要簡潔查一下，從而避開大量的重復(fù)計(jì)算，最終得到多項(xiàng)式時(shí)間的算法。用動(dòng)態(tài)規(guī)劃法求最優(yōu)解public static

26、void matrixChain(int p, int m, int s) int n=p.length-1; for (int i = 1; i <= n; i+) mii = 0; for (int r = 2; r <= n; r+) for (int i = 1; i <= n - r+1; i+) int j=i+r-1; mij = mi+1j+ pi-1*pi*pj; sij = i; for (int k = i+1; k < j; k+) int t = mik + mk+1j + pi-1*pk*pj; if (t < mij) mij = t

27、; sij = k; 2.2.2 0-1 背包問題 給定 n 種物品和一背包。 物品i的重量是wi，其價(jià)值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包中物品，使得裝入背包中物品的總價(jià)值最大？設(shè)(y1,y2,.,yn)是所給0-1背包問題的一個(gè)最優(yōu)解，則(y2,y3,.,yn)是經(jīng)過一次選擇后的0-1背包問題的最優(yōu)解。0-1背包問題的遞歸關(guān)系，設(shè)當(dāng)前子問題的最優(yōu)值為m(i,j)，即m(i,j)是背包涵量為j，可選擇物品為i,i+1,.,n時(shí)0-1背包問題的最優(yōu)值。由0-1背包問題的最優(yōu)子結(jié)構(gòu)性質(zhì)，可以建立計(jì)算m(i,j)的遞歸式：當(dāng)i= n時(shí)，若j>=wn，則m(i,j)=vn；若0<

28、;=j<wn，則m(i,j)=0。當(dāng)i<n時(shí)，若j>=wi，則m(i,j)=maxm(i+1,j),m(i+1,j-wi)+vi；若0<=j<wi，則m(i ,j)=m(i+1,j)。 程序代碼如下:import javax.swing.*;public class Knapsack extends JFrame final JScrollPane scrollPane = new JScrollPane();public static JTextArea resulttextArea;public JLabel l1 = new JLabel("最優(yōu)解

29、");public JLabel l3 = new JLabel("所用時(shí)間");public static JTextField t1 = new JTextField();public static JTextField t2 = new JTextField();final JLabel label = new JLabel();final JLabel label_1 = new JLabel();public Knapsack()this.setResizable(false);this.setTitle("動(dòng)態(tài)規(guī)劃計(jì)算0-1背包")

30、; this.getContentPane().setLayout(null); this.setBounds(100, 100, 670, 400); this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); scrollPane.setBounds(190, 25, 454, 293); getContentPane().add(scrollPane); resulttextArea = new JTextArea(); resulttextArea.setEditable(false); scrollPane.setViewportView

31、(resulttextArea); label.setHorizontalTextPosition(SwingConstants.RIGHT); label.setHorizontalAlignment(SwingConstants.RIGHT); label.setText("最優(yōu)解："); label.setBounds(10, 42, 66, 18); getContentPane().add(label); t1.setHorizontalAlignment(SwingConstants.RIGHT); t1.setHorizontalAlignment(Swing

32、Constants.RIGHT); t1.setBounds(80, 42, 66, 18); getContentPane().add(t1); label_1.setHorizontalTextPosition(SwingConstants.RIGHT); label_1.setHorizontalAlignment(SwingConstants.RIGHT); label_1.setText("所用時(shí)間："); label_1.setBounds(10, 75, 66, 18); getContentPane().add(label_1); t2.setHorizon

33、talAlignment(SwingConstants.RIGHT); t2.setHorizontalAlignment(SwingConstants.RIGHT); t2.setBounds(80, 75, 66, 18); getContentPane().add(t2);void display(int v,int w,int c,int n,int m)int jMax = Math.min(wn-1-1,c);for(int j=0;j<=jMax;j+)mnj = 0;/初始化for(int j=wn-1;j<c;j+)mnj=vn;for(int i=n-1;i&g

34、t;0;i-)jMax=Math.min(wi-1,c);for(int j=0;j<=jMax;j+)mij=mi+1j;for(int j=wi;j<c;j+)mij=Math.max(mi+1j,mi+1j-wi+vi);System.out.println("出來的循環(huán)m0c-1:"+m0c-1);System.out.println("出來的循環(huán)m1c-1:"+m0c-1);m0c-1=m1c-1;if(c>=w0)m0c-1=Math.max(m0c-1,m1c-w0+v0);System.out.println("

35、;-"); System.out.println("此0-1背包問題的最優(yōu)解為："+m0c-1);System.out.println("物品的選擇（0代表沒有選擇，1代表選擇）如下：");System.out.println("-"); t1.setText(""+m0c-1);void taceback(int w,int c,int n,int m,int x)resulttextArea.append("物品的選擇（0代表沒有選擇，1代表選擇）如下：/n");for(int i

36、=0;i<n;i+)if(mic-1=mi+1c-1) xi=0;else xi=1;c-=wi; System.out.println("x"+i+"="+xi);resulttextArea.append("x"+i+"="+xi+"/n");if(mn-1c-1=1) xn-1=1;else xn-1=0;System.out.println("x"+n+"="+xn-1);resulttextArea.append("x"

37、+n+"="+xn-1+"/n");System.out.println("-"); public static void main(String args)final int c=1000;final int n=50;int v=220,208,198,192,180,180,165,162,160,158,155,130,125,122, 120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,70,69,66,65,63,60,58,56,50,30,20,1

38、5,10,8,5,3,1,1;int w=80,82,85,70,72,70,66,50,55,25,50,55,40,48,50,32,22,60,30, 32,40,38,35,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,1,1;int m=new intnc;int x=new intn;long start = System.currentTimeMillis();Knapsack k=new Knapsack();k.setVisible(true);k.display(v,w,c,

39、n-1,m);k.taceback(w,c,n-1,m,x);long end = System.currentTimeMillis();t2.setText(end - start)+"ms");System.out.println("/n Time consuming: " + (end - start);2.2.3 石子合并 在一個(gè)圓形操場(chǎng)的四周擺放著n 堆石子。現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的2 堆石子合并成新的一堆，并將新的一堆石子數(shù)記為該次合并的得分。 試設(shè)計(jì)一個(gè)算法，計(jì)算出將n堆石子合并成一堆的最小得分和最大得分。輸入文件

40、: 包含兩行，第1 行是正整數(shù)n（1<=n<=100），表示有n堆石子。 第2行有n個(gè)數(shù)，分別表示每堆石子的個(gè)數(shù)。 輸出兩行。 第1 行中的數(shù)是最小得分；第2 行中的數(shù)是最大得分。動(dòng)態(tài)規(guī)劃思路： 階段i：石子的每一次合并過程，先兩兩合并，一一再合并，.最終N堆合并 狀態(tài)s：每一階段中各個(gè)不同合并方法的石子合并總得分。 決策：把當(dāng)前階段的合并方法細(xì)分成前一階段已計(jì)算出的方法，選擇其中的最優(yōu)方案 具體來說我們應(yīng)當(dāng)定義一個(gè)數(shù)組si,j用來表示合并方法，i表示從編號(hào)為i的石頭開頭合并，j表示從i開頭數(shù)j堆進(jìn)行合并，si,j為合并的最優(yōu)得分。 對(duì)于上面的例子來說，初始階段就是s1,1,s2,

41、1,s3,1,s4,1,s5,1,s6,1，由于一開頭還沒有合并，所以這些值應(yīng)當(dāng)全部為0。 其次階段：兩兩合并過程如下，其中sum(i,j)表示從i開頭數(shù)j個(gè)數(shù)的和 s1,2=s1,1+s2,1+sum(1,2) s2,2=s2,1+s3,1+sum(2,2) s3,2=s3,1+s4,1+sum(3,2) s4,2=s4,1+s5,1+sum(4,2) s5,2=s5,1+s6,1+sum(5,2) s6,2=s6,1+s1,1+sum(6,2) 第三階段：三三合并可以拆成兩兩合并，拆分方法有兩種，前兩個(gè)為一組或后兩個(gè)為一組. s1,3=s1,2+s3,1+sum(1,3)或s1,3=s1,

42、1+s2,2+sum(1,3)，取其最優(yōu) s2,3=s2,2+s4,1+sum(2,3)或s1,3=s2,1+s3,2+sum(2,3)，取其最優(yōu) 第四階段：四四合并的拆分方法用三種，同理求出三種分法的得分，取其最優(yōu)即可。以后第五階段、第六階段依次類推，最終在第六階段中找出最優(yōu)答案即可源程序#include "stdio.h"#include "stdlib.h"int num101;int s99100;int sum(int i,int j,int n)/求和 int result,final; result=numi;for(int p=1;p&l

43、t;=j-1;p+) if(i+p>n) final=(i+p)%n; else final=i+p; result=result+numfinal; return result; int max(int n) int k,t,w,result; for(int i=1;i<=n;i+)/初始階段就是s1,1,s2,1,s3,1,s4,1,s5,1,s6,1，由于一開頭還沒有合并，所以這些值應(yīng)當(dāng)全部為0 si1=0; for(int r=2;r<=n;r+)/枚舉階段，從兩兩合并開頭計(jì)算 for( i=1;i<=n;i+)/計(jì)算當(dāng)前階段的n種不同狀態(tài)的值,從一開頭的1到

44、n種不同狀態(tài)，例如s1n和s2n if(i+1>n) w=(i+1)%n; else w=i+1; sir=si1+swr-1+sum(i,r,n);/s(i,r,n)表示從i開頭數(shù)r個(gè)數(shù)的和 /mir=w; for( k=1;k<=r-1;k+)/枚舉不同的分段方法 if(i+k>n) w=(i+k)%n; else w=i+k; t=sik+swr-k+sum(i,r,n); if(t>sir)/比較取s1.nr中的最值 sir=t; /mir=k; result=s1n; for(int u=1;u<=n;u+)/從s1n到snn中取最大值 / printf

45、("%d ",sun); if(sun>result) result=sun; return result;int min(int n)/同max()差不多 int k,t,w,result; for(int i=1;i<=n;i+) si1=0; for(int r=2;r<=n;r+) for( i=1;i<=n;i+) if(i+1>n) w=(i+1)%n; else w=i+1; sir=si1+swr-1+sum(i,r,n); mir=w; for( k=1;k<=r-1;k+) if(i+k>n) w=(i+k)%n

46、; else w=i+k; t=sik+swr-k+sum(i,r,n); if(t<sir)/比較 sir=t; mir=k; result=s1n; for(int u=1;u<=n;u+)/還是比較，與max比較不同 / printf("%d ",sun); if(sun<result) result=sun; return result;int main() int n; scanf("%d",&n); for(int i=1;i<=n;i+) scanf("%d",&numi); pr

47、intf("%dn",min(n); printf("%dn",max(n); return 1; 第三章 貪心算法貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，期望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)全部問題都得到整體最優(yōu)解，但對(duì)很多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些狀況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。3.1 貪心算法的特性貪欲算法可解決的問題通常大部分都有如下的特性： 有一個(gè)以最優(yōu)方式來解決的問題。為了構(gòu)造問題的解決方案，有一個(gè)候選的對(duì)象的集合：比如不同面值的硬幣。 隨著算法的進(jìn)行，將積累起其它兩個(gè)集合：一個(gè)包含已經(jīng)被考慮過并被選出的候選對(duì)象，另一個(gè)包含已經(jīng)被考慮過但被丟棄的候選對(duì)象。 有一個(gè)函數(shù)來檢查一個(gè)候選對(duì)象的集合是否供應(yīng)了問題的解答。該函數(shù)不考慮此時(shí)的解決方法是否最優(yōu)。 還有一個(gè)函數(shù)檢查是否一個(gè)候選對(duì)象的集合是可行的，也即是否可能往該集合上添加更多的候選對(duì)象以獲得一個(gè)解。和上一個(gè)函數(shù)一樣，此時(shí)不考慮解決方法的最優(yōu)性