




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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)??梢越(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ī)??s小到肯定的程度就可以簡潔地解決;該問題可以分解為若干個(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è)圓形操場的四周擺放著n 堆石子?,F(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)性
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 韓國租房合同續(xù)租協(xié)議書
- 商業(yè)決策中的教育技術(shù)力量
- 小學(xué)2025年國防教育實(shí)地考察計(jì)劃
- 旅游行業(yè)衛(wèi)生與感染防控職責(zé)
- 中小學(xué)師德師風(fēng)評(píng)估機(jī)制與職責(zé)
- 人教版七年級(jí)英語下冊(cè)各單元聽力訓(xùn)練范文
- 退休人員去職限制協(xié)議
- 醫(yī)療機(jī)構(gòu)冠狀病毒患者轉(zhuǎn)診流程
- 高層建筑施工安全生產(chǎn)管理計(jì)劃
- 私立學(xué)校食堂承包協(xié)議
- 公司招采管理制度
- 故障測(cè)距-牽引網(wǎng)故障測(cè)距(鐵路牽引供電系統(tǒng)繼電保護(hù))
- 國家開放大學(xué)期末機(jī)考人文英語1
- 廣州市輕工技師學(xué)院招聘真題
- 邦納T30UX系列超聲波傳感器
- 產(chǎn)業(yè)命題賽道命題解決對(duì)策參考模板
- 重點(diǎn)崗位工崗位應(yīng)知風(fēng)險(xiǎn)和異常情況處置管控措施清單
- 電動(dòng)車分期付款的合同范本
- 《反對(duì)校園欺凌》話劇劇本
- 國家開放大學(xué)電大《課程與教學(xué)論》形考任務(wù)2試題及答案
- 東風(fēng)雪鐵龍世嘉c-quatre說明書(三廂)
評(píng)論
0/150
提交評(píng)論