動(dòng)態(tài)規(guī)劃 分類(lèi).doc

動(dòng)態(tài)規(guī)劃分類(lèi)1、背包模型 包括0-1背包、無(wú)限背包、有限背包、有價(jià)值背包、小數(shù)背包（貪心即可)等，是極為經(jīng)典的模型，其轉(zhuǎn)化與優(yōu)化也是很重要的。 H P4 k v3T V A2、最長(zhǎng)非降子序列模型 7i _ F+E N H g O8| | | s 改版：渡河問(wèn)題、合唱隊(duì)型等 3、最大子段和模型 改版：K大子段和、最佳游覽，最大子矩陣和等。 4、LCS模型 ?:p0n E m$v |+r 改版：回文字串、多串的LCS等 5、括號(hào)序列模型 M Y3e V D:D 改版：關(guān)燈問(wèn)題（TSOJ）、charexp（TSOJ）、最大算式等，核心思想在于以串的長(zhǎng)度為階段。 6、遞推模型 p:l s#U i _1J L 這類(lèi)題是屬于徘徊在DP與遞歸之間得一類(lèi)題，本質(zhì)是類(lèi)似于記憶化搜索的一種填表，有很強(qiáng)的數(shù)學(xué)味。 &e n o A:l V7、線段覆蓋問(wèn)題 改版：Tom的煩惱（TOJ）等。經(jīng)常利用到離散化等技巧輔助。 g R V1e+h&F8、單詞劃分模型 和LCS基本上構(gòu)成了字符串DP的主要類(lèi)型。改版：奇怪的門(mén)（TOJ）等。 9、股票模型 8u F. x&m |8g! 這是DP優(yōu)化的經(jīng)典模型。改版有換外匯等。 ,o/z yw ?5/d10、連續(xù)段劃分模型 即要求把數(shù)列劃分成k個(gè)連續(xù)段，使每段和的最大值最小。改版有任務(wù)調(diào)度等。 x0e B6d k X j8tv1| Y11、游戲模型 這類(lèi)題的階段（一般是時(shí)間）和決策（一般就是游戲目標(biāo)）很清楚，因此比較容易想到。改版：免費(fèi)餡餅（NOI98）、Help Jimmy（CEOI2000）、瑰麗華爾茲（NOI2005，優(yōu)化需要多費(fèi)功夫）。dp注意的一些總結(jié)/sgr123/blog 好好看看看完，做完，想完，總結(jié)完后：22/oblog3/user1/40/subject/index.html1.dp一定要邊界條件。關(guān)于初始值的問(wèn)題，這是dp的起點(diǎn)，是dp中除方程外最終要的東西，dp過(guò)程中的每一個(gè)值必須都符合他的狀態(tài)所表示的意義，否則就是錯(cuò)的，以前方程寫(xiě)對(duì)了，但是在這個(gè)問(wèn)題上卻經(jīng)常出錯(cuò)，看了dd_engi大牛的背包問(wèn)題九講中關(guān)于背包恰好放滿(mǎn)，與可不放滿(mǎn)的最大值大求法的比較后才恍然大悟，除非所有的初始邊界在此狀態(tài)定義下他的有意義的值就是0，否則必須初始化。例如背包。（初始化的f數(shù)組事實(shí)上就是在沒(méi)有任何物品可以放入背包時(shí)的合法狀態(tài)。如果要求背包恰好裝滿(mǎn)，那么此時(shí)只有容量為0的背包可能被價(jià)值為0的nothing“恰好裝滿(mǎn)”，其它容量的背包均沒(méi)有合法的解，屬于未定義的狀態(tài)，它們的值就都應(yīng)該是-了。如果背包并非必須被裝滿(mǎn)，那么任何容量的背包都有一個(gè)合法解“什么都不裝”，這個(gè)解的價(jià)值為0，所以初始時(shí)狀態(tài)的值也就全部為0了。背包問(wèn)題九講）2.初始最小值不要想當(dāng)然的賦0，有時(shí)候要求的值可能是負(fù)的，一定要看清題意，注意賦-，但是再用計(jì)算機(jī)表示的時(shí)候不要賦的過(guò)大，或過(guò)小，因?yàn)橹虚g的運(yùn)算過(guò)程中可能會(huì)中間值越界產(chǎn)生215錯(cuò)誤而爆掉3.遞推順序每一步怎樣取最大值，以及每一步的值對(duì)后來(lái)有什么影響都要考慮全再開(kāi)始編，不要一出來(lái)方程就動(dòng)手4.先考慮清楚，必須一次ac！5.始終遵循dp每一步都只用已經(jīng)算出來(lái)的！拿到一個(gè)題一定要 先想好 數(shù)據(jù)結(jié)構(gòu)（在紙上寫(xiě)好），算 法框架（最好也在紙上寫(xiě)好）胸有成竹再下筆！否則則只是浪費(fèi)時(shí)間！6.不要想當(dāng)然的把所有的最優(yōu)化的題目都認(rèn)為是dp，往往貪心和模擬能夠發(fā)揮巨大作用！不是dp的題用dp去做，絕對(duì)是錯(cuò)誤的！7.不是動(dòng)歸方程寫(xiě)出來(lái)就萬(wàn)事大吉了，必須能證明它的無(wú)后效性，必須滿(mǎn)足最有子結(jié)構(gòu)，過(guò)于復(fù)雜的方程往往是錯(cuò)誤的，即使分類(lèi)考慮的情況很多，但是每一類(lèi)也應(yīng)該很簡(jiǎn)潔，必須證明它的正確性再動(dòng)手，否則是在白費(fèi)力氣。8.一定要考慮全面，動(dòng)歸方程一定要包含所有的情況。9.再說(shuō)一遍！實(shí)現(xiàn)的時(shí)候一定要注意遞推邊界和循環(huán)范圍，每一步用到的值都是已經(jīng)求出來(lái)的，初始化！動(dòng)態(tài)規(guī)劃一、多階段決策過(guò)程的最優(yōu)化問(wèn)題問(wèn)題的提出首先，例舉一個(gè)典型的且很直觀的多階段決策問(wèn)題:例 下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費(fèi)用，單向通行由A-E。求A-E的最省費(fèi)用。如圖從A到E共分為4個(gè)階段，即第一階段從A到B，第二階段從B到C，第三階段從C到D，第四階段從D到E。除起點(diǎn)A和終點(diǎn)E外，其它各點(diǎn)既是上一階段的終點(diǎn)又是下一階段的起點(diǎn)。例如從A到B的第一階段中，A為起點(diǎn)，終點(diǎn)有B1，B2，B3三個(gè)，因而這時(shí)走的路線有三個(gè)選擇，一是走到B1，一是走到B2，一是走到B3。若選擇B2的決策，B2就是第一階段在我們決策之下的結(jié)果，它既是第一階段路線的終點(diǎn)，又是第二階段路線的始點(diǎn)。在第二階段，再?gòu)腂2點(diǎn)出發(fā)，對(duì)于B2點(diǎn)就有一個(gè)可供選擇的終點(diǎn)集合(C1，C2，C3)；若選擇由B2走至C2為第二階段的決策，則C2就是第二階段的終點(diǎn)，同時(shí)又是第三階段的始點(diǎn)。同理遞推下去，可看到各個(gè)階段的決策不同，線路就不同。很明顯，當(dāng)某階段的起點(diǎn)給定時(shí)，它直接影響著后面各階段的行進(jìn)路線和整個(gè)路線的長(zhǎng)短，而后面各階段的路線的發(fā)展不受這點(diǎn)以前各階段的影響。故此問(wèn)題的要求是：在各個(gè)階段選取一個(gè)恰當(dāng)?shù)臎Q策，使由這些決策組成的一個(gè)決策序列所決定的一條路線，其總路程最短。具體情況如下：（1）由目標(biāo)狀態(tài)E向前推，可以分成四個(gè)階段，即四個(gè)子問(wèn)題。如上圖所示。（2）策略：每個(gè)階段到E的最省費(fèi)用為本階段的決策路徑。（3）D1，D2是第一次輸入的結(jié)點(diǎn)。他們到E都只有一種費(fèi)用，在D1框上面標(biāo)5，D2框上面標(biāo)2。目前無(wú)法定下，那一個(gè)點(diǎn)將在全程最優(yōu)策略的路徑上。第二階段計(jì)算中，5，2都應(yīng)分別參加計(jì)算。（4）C1，C2，C3是第二次輸入結(jié)點(diǎn)，他們到D1，D2各有兩種費(fèi)用。此時(shí)應(yīng)計(jì)算C1，C2，C3分別到E的最少費(fèi)用。C1的決策路徑是 min（C1D1），（C1D2）。計(jì)算結(jié)果是C1+D1+E，在C1框上面標(biāo)為8。同理C2的決策路徑計(jì)算結(jié)果是C2+D2+E，在C2框上面標(biāo)為7。同理C3的決策路徑計(jì)算結(jié)果是C3+D2+E，在C3框上面標(biāo)為12。此時(shí)也無(wú)法定下第一，二階段的城市那二個(gè)將在整體的最優(yōu)決策路徑上。（5）第三次輸入結(jié)點(diǎn)為B1，B2，B3，而決策輸出結(jié)點(diǎn)可能為C1，C2，C3。仿前計(jì)算可得B1，B2，B3的決策路徑為如下情況。B1:B1C1費(fèi)用 12+8=20， 路徑:B1+C1+D1+EB2:B2C1費(fèi)用 6+8=14， 路徑:B2+C1+D1+EB3:B2C2費(fèi)用 12+7=19， 路徑:B3+C2+D2+E此時(shí)也無(wú)法定下第一，二，三階段的城市那三個(gè)將在整體的最優(yōu)決策路徑上。（6）第四次輸入結(jié)點(diǎn)為A，決策輸出結(jié)點(diǎn)可能為B1，B2，B3。同理可得決策路徑為A：AB2，費(fèi)用5+14=19，路徑 A+B2+C1+D1+E。此時(shí)才正式確定每個(gè)子問(wèn)題的結(jié)點(diǎn)中，那一個(gè)結(jié)點(diǎn)將在最優(yōu)費(fèi)用的路徑上。19是結(jié)果，顯然這種計(jì)算方法，符合最優(yōu)原理。子問(wèn)題的決策中，只對(duì)同一城市（結(jié)點(diǎn)）比較優(yōu)劣。而同一階段的城市（結(jié)點(diǎn)）的優(yōu)劣要由下一個(gè)階段去決定。二、動(dòng)態(tài)規(guī)劃的概念在上例的多階段決策問(wèn)題中，各個(gè)階段采取的決策，一般來(lái)說(shuō)是與時(shí)間有關(guān)的，決策依賴(lài)于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，故有“動(dòng)態(tài)”的含義，稱(chēng)這種解決多階段決策最優(yōu)化問(wèn)題的方法為動(dòng)態(tài)規(guī)劃方法。與窮舉法相比，動(dòng)態(tài)規(guī)劃的方法有兩個(gè)明顯的優(yōu)點(diǎn):(1)大大減少了計(jì)算量(2)豐富了計(jì)算結(jié)果從上例的求解結(jié)果中，我們不僅得到由A點(diǎn)出發(fā)到終點(diǎn)E的最短路線及最短距離，而且還得到了從所有各中間點(diǎn)到終點(diǎn)的最短路線及最短距離，這對(duì)許多實(shí)際問(wèn)題來(lái)講是很有用的。動(dòng)態(tài)規(guī)劃的最優(yōu)化概念：是在一定條件下，得到一種途徑，在對(duì)各階段的效益經(jīng)過(guò)按問(wèn)題具體性質(zhì)所確定的運(yùn)算以后，使得全過(guò)程的總效益達(dá)到最優(yōu)。應(yīng)用動(dòng)態(tài)規(guī)劃要注意階段的劃分是關(guān)鍵，必須依據(jù)題意分析，尋求合理的劃分階段(子問(wèn)題)方法。而每個(gè)子問(wèn)題是一個(gè)比原問(wèn)題簡(jiǎn)單得多的優(yōu)化問(wèn)題。而且每個(gè)子問(wèn)題的求解中，均利用它的一個(gè)后部子問(wèn)題的最優(yōu)化結(jié)果，直到最后一個(gè)子問(wèn)題所得最優(yōu)解，它就是原問(wèn)題的最優(yōu)解。三、動(dòng)態(tài)規(guī)劃適合解決什么樣的問(wèn)題準(zhǔn)確地說(shuō)，動(dòng)態(tài)規(guī)劃不是萬(wàn)能的，它只適于解決一定條件的最優(yōu)策略問(wèn)題?；蛟S，大家聽(tīng)到這個(gè)結(jié)論會(huì)很失望：其實(shí)，這個(gè)結(jié)論并沒(méi)有削減動(dòng)態(tài)規(guī)劃的光輝，因?yàn)閷儆谏厦娣秶鷥?nèi)的問(wèn)題極多，還有許多看似不是這個(gè)范圍中的問(wèn)題都可以轉(zhuǎn)化成這類(lèi)問(wèn)題。上面所說(shuō)的“滿(mǎn)足一定條件”主要指下面兩點(diǎn)：(1)狀態(tài)必須滿(mǎn)足最優(yōu)化原理；(2)狀態(tài)必須滿(mǎn)足無(wú)后效性。動(dòng)態(tài)規(guī)劃的最優(yōu)化原理：是無(wú)論過(guò)去的狀態(tài)和決策如何，對(duì)前面的決策所形成的當(dāng)前狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略?？梢酝ㄋ椎乩斫鉃樽訂?wèn)題的局部最優(yōu)將導(dǎo)致整個(gè)問(wèn)題的全局最優(yōu)。在上例中例題1最短路徑問(wèn)題中，A到E的最優(yōu)路徑上的任一點(diǎn)到終點(diǎn)E的路徑也必然是該點(diǎn)到終點(diǎn)E的一條最優(yōu)路徑，滿(mǎn)足最優(yōu)化原理。動(dòng)態(tài)規(guī)劃的無(wú)后效性原則：某階段的狀態(tài)一旦確定，則此后過(guò)程的演變不再受此前各狀態(tài)及決策的影響。也就是說(shuō)，“未來(lái)與過(guò)去無(wú)關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個(gè)完整總結(jié)，此前的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響過(guò)程未來(lái)的演變。具體地說(shuō)，如果一個(gè)問(wèn)題被劃分各個(gè)階段之后，階段 I 中的狀態(tài)只能由階段 I+1 中的狀態(tài)通過(guò)狀態(tài)轉(zhuǎn)移方程得來(lái)，與其他狀態(tài)沒(méi)有關(guān)系，特別是與未發(fā)生的狀態(tài)沒(méi)有關(guān)系，這就是無(wú)后效性。為什么要用動(dòng)態(tài)規(guī)劃法解題首先，看下面一個(gè)問(wèn)題:【例題1】數(shù)字三角形問(wèn)題。 7 3 8 8 1 0 2 7 7 4 5 5 2 6 5顯示出了一個(gè)數(shù)字三角形寶塔。數(shù)字三角形中的數(shù)字為不超過(guò)100的正整數(shù)?，F(xiàn)規(guī)定從最頂層走到最底層，每一步可沿左斜線向下或右斜線向下走。假設(shè)三角形行數(shù)100，編程求解從最頂層走到最底層的一條路徑，使得沿著該路徑所經(jīng)過(guò)的數(shù)字的總和最大，輸出最大值。輸人數(shù)據(jù)：由文件輸入數(shù)據(jù)，文件第一行是三角形的行數(shù)N。以后的N行分別是從最頂層到最底層的每一層中的數(shù)字。如輸入： 57 3 8 8 1 0 2 7 7 4 4 5 2 6 5 輸出：30【分析】對(duì)于這一問(wèn)題，很容易想到用枚舉的方法（深度搜索法）去解決，即列舉出所有路徑并記錄每一條路徑所經(jīng)過(guò)的數(shù)字總和。然后尋找最大的數(shù)字總和，這一想法很直觀，很容易編程實(shí)現(xiàn)其程序如下：program sjx;const maxn=10;vara:array1.maxn,1.maxn of integer;max:longint;n,i,j:integer;fname:string;inputf:text;procedure try(x,y,dep:integer;sum:longint);begin if (dep=n) then begin if summax then max:=sum; exit end; try(x+1,y,dep+1,sum+ax+1,y); try(x+1,y+1,dep+1,sum+ax+1,y+1);end;beginreadln(fname);assign(inputf,fname);reset(inputf);readln(inputf,n);for i:=1 to n do for j:= 1 to i do read(inputf,ai,j);max:=0;try(1,1,1,a1,1);writeln(max);end.但是當(dāng)行數(shù)很大時(shí)，當(dāng)三角形的行數(shù)等于100時(shí)，其枚舉量之大是可想而知的，用枚舉法肯定超時(shí)，甚至根本不能得到計(jì)算結(jié)果，必須用動(dòng)態(tài)規(guī)劃法來(lái)解。二、怎樣用動(dòng)態(tài)規(guī)劃法解題1.逆推法:按三角形的行劃分階段，若行數(shù)為 n，則可把問(wèn)題看做一個(gè)n-1個(gè)階段的決策問(wèn)題。先求出第n-1階段(第n-1行上各點(diǎn))到第n行的的最大和，再依次求出第n-2階段、第n-3階段第1階段(起始點(diǎn))各決策點(diǎn)至第n行的最佳路徑。設(shè)：fi,j為從第i階段中的點(diǎn)j至第n行的最大的數(shù)字和；則: fn,j=an,j 1=j=n fi,j=maxai,j+fi+1,j,ai,j+fi+1,j+1 1=jfi+1,j+1 then fi,j:=ai,j+fi+1,j else fi,j:=ai,j+fi+1,j+1;writeln(f1,1);end. 2. 順推法按三角形的行劃分階段，若行數(shù)為 n，則可把問(wèn)題看做一個(gè)n-1個(gè)階段的決策問(wèn)題。先求第2行各元素到起點(diǎn)的最大和,再依次求出第3,4，5,.,.n-1,n到起點(diǎn)的最大和,最后找第n行的最大值設(shè)fi,j為 第i行第j列上點(diǎn)到起點(diǎn)的最大和則 f1，1=a1,1; fi，1=ai, 1+fi-1,1; f i，j =max ai,j+fi-1,j-1,ai,j+fi-1,j 2=jfi-1,j then fi,j:=ai,j+fi-1,j-1 else fi,j:=ai,j+fi-1,j; end;maxsum:=0;for i:=1 to n do if fn,imaxsum then maxsum:=fn,i;writeln(maxsum);end.說(shuō)明一下：1.用動(dòng)態(tài)規(guī)劃解題主要思想是用空間換時(shí)間.2.本題如果n較大，用2維數(shù)組空間可能不夠,可以使用1維數(shù)組.程序如下:program datasjx;const maxn=100;varfname:string;inputf:text;n,i,j:integer;a:array1.maxn,1.maxn of integer;f:array1.maxn of integer;maxsum:integer;beginreadln(fname);assign(inputf,fname);reset(inputf);readln(inputf,n);for i:=1 to n do for j:=1 to i do read(inputf,ai,j);fillchar(f,sizeof(f),0);f1:=a1,1;for i:=2 to n do begin for j:=i downto 2 do if fj-1fj then fj:=ai,j+fj-1 else fj:=ai,j+fj; f1:=ai,1+f1; end;maxsum:=0;for i:=1 to n do if fimaxsum then maxsum:=fi;writeln(maxsum);end.練習(xí):用一維數(shù)組和逆推法解本題.三、用動(dòng)態(tài)規(guī)劃法解題的一般模式動(dòng)態(tài)規(guī)劃所處理的問(wèn)題是一個(gè)多階段決策問(wèn)題，一般由初始狀態(tài)開(kāi)始，通過(guò)對(duì)中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過(guò)程的一條活動(dòng)路線(通常是求最優(yōu)的活動(dòng)路線)。如圖所示。動(dòng)態(tài)規(guī)劃的設(shè)計(jì)都有著一定的模式，一般要經(jīng)歷以下幾個(gè)步驟。初始狀態(tài)決策決策決策結(jié)束狀態(tài)(1)劃分階段：按照問(wèn)題的時(shí)間或空間特征，把問(wèn)題分為若干個(gè)階段。在劃分階段時(shí)，注意劃分后的階段一定要是有序的或者是可排序的，否則問(wèn)題就無(wú)法求解。(2)確定狀態(tài)和狀態(tài)變量：將問(wèn)題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出來(lái)。當(dāng)然，狀態(tài)的選擇要滿(mǎn)足無(wú)后效性。(3)確定決策并寫(xiě)出狀態(tài)轉(zhuǎn)移方程：因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來(lái)導(dǎo)出本階段的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫(xiě)出。但事實(shí)上常常是反過(guò)來(lái)做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來(lái)確定決策。(4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個(gè)遞推式，需要一個(gè)遞推的終止條件或邊界條件。(5)程序設(shè)計(jì)實(shí)現(xiàn)：動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡(jiǎn)單。根據(jù)上述動(dòng)態(tài)規(guī)劃設(shè)計(jì)的步驟，可得到大體解題框架如下:1.初始化(邊界條件)2.for i:=2 to n (順推法) 或 for i:=n-1 to 1(逆推法) 對(duì)i階段的每一個(gè)決策點(diǎn)求局部最優(yōu)3.確定和輸出結(jié)束狀態(tài)的值.第三章 典型例題與習(xí)題3.1 最長(zhǎng)不降子序列3.2 背包問(wèn)題3.3 最短路徑3.1 最長(zhǎng)不降子序列（1）問(wèn)題描述設(shè)有由n個(gè)不相同的整數(shù)組成的數(shù)列，記為:a(1)、a(2)、a(n)且a(i)a(j) (ij)例如3，18，7，14，10，12，23，41，16，24。若存在i1i2i3 ie 且有a(i1)a(i2) a(ie)則稱(chēng)為長(zhǎng)度為e的不下降序列。如上例中3，18，23，24就是一個(gè)長(zhǎng)度為4的不下降序列，同時(shí)也有3，7，10，12，16，24長(zhǎng)度為6的不下降序列。程序要求，當(dāng)原數(shù)列給出之后，求出最長(zhǎng)的不下降序列。（2）算法分析根據(jù)動(dòng)態(tài)規(guī)劃的原理，由后往前進(jìn)行搜索。1 對(duì)a(n)來(lái)說(shuō)，由于它是最后一個(gè)數(shù)，所以當(dāng)從a(n)開(kāi)始查找時(shí)，只存在長(zhǎng)度為1的不下降序列；2 若從a(n-1)開(kāi)始查找，則存在下面的兩種可能性：若a(n-1)a(n)則存在長(zhǎng)度為1的不下降序列a(n-1)或a(n)。3 一般若從a(i)開(kāi)始，此時(shí)最長(zhǎng)不下降序列應(yīng)該按下列方法求出:在a(i+1),a(i+2),a(n)中，找出一個(gè)比a(i)大的且最長(zhǎng)的不下降序列，作為它的后繼。4.用數(shù)組b(i),c(i)分別記錄點(diǎn)i到n的最長(zhǎng)的不降子序列的長(zhǎng)度和點(diǎn)i后繼接點(diǎn)的編號(hào)(3) 程序如下:（逆推法）program li1;const maxn=100;var a,b,c:array1.maxn of integer; fname:string; f:text; n,i,j,max,p:integer;beginreadln(fname);assign(f,fname);reset(f);readln(f,n);+for i:=1 to n do begin read(f,ai); bn:=1; cn:=0; end;for i:= n-1 downto 1 do begin max:=0;p:=0; for j:=i+1 to n do if (aimax) then begin max:=bj;p:=j end; if p0 then begin bi:=bp+1;ci:=p end end;max:=0;p:=0;for i:=1 to n do if bimax then begin max:=bi;p:=i end;writeln(maxlong=,max);write(result is:);while p0 do begin write(ap:5);p:=cp end;end.3.2 背包問(wèn)題背包問(wèn)題有三種1.部分背包問(wèn)題 一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n種物品，它們的總重量分別是W1，W2，.,Wn,它們的總價(jià)值分別為C1,C2,.,Cn.求旅行者能獲得最大總價(jià)值。 解決問(wèn)題的方法是貪心算法:將C1/W1,C2/W2,.Cn/Wn,從大到小排序,不停地選擇價(jià)值與重量比最大的放人背包直到放滿(mǎn)為止. 2.0/1背包 一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1，W2，.,Wn,它們的價(jià)值分別為C1,C2,.,Cn.若每種物品只有一件求旅行者能獲得最大總價(jià)值。 分析說(shuō)明: 顯然這個(gè)題可用深度優(yōu)先方法對(duì)每件物品進(jìn)行枚舉(選或不選用0,1控制). 程序簡(jiǎn)單,但是當(dāng)n的值很大的時(shí)候不能滿(mǎn)足時(shí)間要求，時(shí)間復(fù)雜度為O（2n）。按遞歸的思想我們可以把問(wèn)題分解為子問(wèn)題,使用遞歸函數(shù) 設(shè) f(i，x)表示前i件物品，總重量不超過(guò)x的最優(yōu)價(jià)值 則 f（i，x）=max(f(i1，x-Wi)+Ci，f（i1，x） f（n，m）即為最優(yōu)解，邊界條件為f（0，x）0 ，f(i,0)=0; 動(dòng)態(tài)規(guī)劃方法(順推法)程序如下: 程序如下： program knapsack02;const maxm=200;maxn=30;type ar=array1.maxn of integer;var m,n,j,i:integer;c,w:ar;f:array0.maxn,0.maxm of integer;function max(x,y:integer):integer;begin if xy then max:=x else max:=y;end;begin readln(m,n); for i:= 1 to n do readln(wi,ci); for i:=1 to m do f(0,i):=0; for i:=1 to n do f(i,0):=0; for i:=1 to n do for j:=1 to m do begin if j=wi then fi,j:=max(fi-1,j-wi+ci,fi-1,j) else fi,j:=fi-1,j; end; writeln(fn,m); end. 使用二維數(shù)組存儲(chǔ)各子問(wèn)題時(shí)方便，但當(dāng)maxm較大時(shí)如maxn=2000時(shí)不能定義二維數(shù)組f,怎么辦,其實(shí)可以用一維數(shù)組,但是上述中j:=1 to m 要改為j:=m downto 1,為什么?請(qǐng)大家自己解決。 3.完全背包問(wèn)題一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n種物品，每件的重量分別是W1，W2，.,Wn,每件的價(jià)值分別為C1,C2,.,Cn.若的每種物品的件數(shù)足夠多.求旅行者能獲得的最大總價(jià)值。本問(wèn)題的數(shù)學(xué)模型如下： 設(shè) f(x)表示重量不超過(guò)x公斤的最大價(jià)值， 則 f(x）=maxf(x-wi)+ci 當(dāng)x=wi 1=i=wj then t:=fi-wj+cj; if tfi then fi:=t end; writeln(fm); end.3.3 最短路徑問(wèn)題描述：如圖：求v1到v10的最短路徑長(zhǎng)度及最短路徑。圖的鄰接矩陣如下：0 2 5 1 -1 -1 -1 -1 -1 -1-1 0 -1 -1 12 14 -1 -1 -1 -1-1 -1 0 -1 6 10 4 -1 -1 -1-1 -1 -1 0 13 12 11 -1 -1 -1-1 -1 -1 -1 0 -1 -1 3 9 -1-1 -1 -1 -1 -1 0 -1 6 5 -1-1 -1 -1 -1 -1 -1 0 -1 10 -1-1 -1 -1 -1 -1 -1 -1 0 -1 5-1 -1 -1 -1 -1 -1 -1 -1 0 2-1 -1 -1 -1 -1 -1 -1 -1 -1 0采用逆推法設(shè)f（x）表示點(diǎn)x到v10的最短路徑長(zhǎng)度則 f(10)=0 f(x)=min f(i)+ax,i 當(dāng)ax,i0 ,xi0) and (bjmaxint) and (bj+ai,jbi) then begin bi:=bj+ai,j;ci:=j end;writeln(minlong=,b1);x:=1; while x0 do begin write(x:5); x:=cx; end;end.3.4習(xí)題1.若城市路徑示意圖如下圖所示:圖中，每條邊上的數(shù)字是這段道路的長(zhǎng)度。條件：從A地出發(fā)，只允許向右或向上走。試尋找一條從A地到B地的最短路徑和長(zhǎng)度。2.求一個(gè)數(shù)列中的連續(xù)若干個(gè)數(shù)和的最大值.3.資源分配問(wèn)題:n個(gè)資源分配到m個(gè)項(xiàng)目上，i項(xiàng)目分配j個(gè)資源可獲益ai,j,求最大總效益。4. 裝箱問(wèn)題問(wèn)題描述:有一個(gè)箱子容量為V（正整數(shù)，0V20000），同時(shí)有n個(gè)物品（0n30，每個(gè)物品有一個(gè)體積（正整數(shù)）。要求n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。 樣例 輸入： 24 一個(gè)整數(shù)，表示箱子容量 6 一個(gè)整數(shù)，表示有n個(gè)物品 8 接下來(lái)n行，分別表示這n 個(gè)物品的各自體積 3 12 7 9 7輸出：0一個(gè)整數(shù)，表示箱子剩余空間。圖中，每條邊上的數(shù)字是這段道路的長(zhǎng)度。條件：從A地出發(fā)，只允許向右或向上走。試尋找一條從A地到B地的最短路徑和長(zhǎng)度。2.求一個(gè)數(shù)列中的連續(xù)若干個(gè)數(shù)和的最大值.3.資源分配問(wèn)題:n個(gè)資源分配到m個(gè)項(xiàng)目上，i項(xiàng)目分配j個(gè)資源可獲益ai,j,求最大總效益。4. 裝箱問(wèn)題問(wèn)題描述:有一個(gè)箱子容量為V（正整數(shù)，0V20000），同時(shí)有n個(gè)物品（0n30，每個(gè)物品有一個(gè)體積（正整數(shù)）。要求n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。 樣例 輸入： 24 一個(gè)整數(shù)，表示箱子容量 6 一個(gè)整數(shù)，表示有n個(gè)物品 8 接下來(lái)n行，分別表示這n 個(gè)物品的各自體積 3 12 7 9 7輸出：0一個(gè)整數(shù)，表示箱子剩余空間。第四章 動(dòng)態(tài)規(guī)劃的遞歸函數(shù)法（你實(shí)在覺(jué)得你動(dòng)態(tài)規(guī)劃不行，最后1，2個(gè)月專(zhuān)攻的算法，平時(shí)訓(xùn)練不要當(dāng)作動(dòng)態(tài)規(guī)劃的重點(diǎn)，只能是一般算法）4.1 原始遞歸法4.2 改進(jìn)遞歸法4.3 習(xí)題4.1 原始遞歸法先看完全背包問(wèn)題一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n種物品，每件的重量分別是W1，W2，.,Wn,每件的價(jià)值分別為C1,C2,.,Cn.若的每種物品的件數(shù)足夠多.求旅行者能獲得的最大總價(jià)值。本問(wèn)題的數(shù)學(xué)模型如下： 設(shè) f(x)表示重量不超過(guò)x公斤的最大價(jià)值， 則 f(x）=maxf(x-i)+ci 當(dāng)x=wi 1=i=wi then m:=f(x-i)+ci; if mt then t:=m; end; f:=t; end;end;begin readln(m,n); for i:= 1 to n do readln(wi,ci); writeln(f(m); end.說(shuō)明:當(dāng)m不大時(shí),編程很簡(jiǎn)單,但當(dāng)m較大時(shí),容易超時(shí).4.2 改進(jìn)的遞歸法改進(jìn)的的遞歸法的思想還是以空間換時(shí)間,這只要將遞歸函數(shù)計(jì)算過(guò)程中的各個(gè)子函數(shù)的值保存起來(lái),開(kāi)辟一個(gè)一維數(shù)組即可程序如下:program knapsack04;const maxm=2000;maxn=30;type ar=array0.maxn of integer;var m,n,j,i,t:integer;c,w:ar;p:array0.maxm of integer;function f(x:integer):integer;var i,t,m:integer;beginif px-1 then f:=px else begin if x=0 then px:=0 else begin t:=-1; for i:=1 to n do begin if x=wi then m:=f(i-wi)+ci; if mt then t:=m; end; px:=t; end; f:=px;end;end;begin readln(m,n); for i:= 1 to n do readln(wi,ci);fillchar(p,sizeof(p),-1); writeln(f(m); end.4.3習(xí)題 用改進(jìn)的遞歸法解資源分配問(wèn)題:n個(gè)資源分配到m個(gè)項(xiàng)目上，i項(xiàng)目分配j個(gè)資源可獲益ai,j,求最大總效益。5.1 例1乘積最大問(wèn)題問(wèn)題描述：今年是國(guó)際數(shù)學(xué)聯(lián)盟確定的2000-世界數(shù)學(xué)年，又恰逢我國(guó)著名數(shù)學(xué)家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場(chǎng)別開(kāi)生面的數(shù)學(xué)智力競(jìng)賽的活動(dòng)，你的一個(gè)好朋友XZ也有幸得以參加。活動(dòng)中，主持人給所有參加活動(dòng)的選手除了這樣一道題目：設(shè)有一個(gè)長(zhǎng)度為N的數(shù)字串，要求選手使用K個(gè)乘號(hào)將它分成K+1個(gè)部分，找出一種分法，使得這K+1部分的乘積能夠?yàn)樽畲?。同時(shí)，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個(gè)例子：有一個(gè)數(shù)字川：312，當(dāng)N=3,K=1時(shí)會(huì)有一下兩種分法：1） 3*12=362） 31*2=62這時(shí)，符合題目要求的結(jié)果是；31*2=62現(xiàn)在，請(qǐng)你幫助你的好朋友XZ設(shè)計(jì)一個(gè)程序，求得正確的答案。輸入：程序的輸入共有兩行：第一行共有2個(gè)自然數(shù)N，K（6N50，1K20）第二行是一個(gè)長(zhǎng)度為N的數(shù)字串。輸出：結(jié)果顯示在屏幕上，相對(duì)于輸入，應(yīng)輸出所求得的最大乘積（一個(gè)自然數(shù)）。樣例：輸入4 21231輸出62 程序如下：program tg20002;const maxn=50;maxk=20 ;type num=record len:byte; s:array1.maxn of byte; end;type str=stringmaxn;var n,k,i,j,l:integer; st,temps:str; m,tempm:num; f:array1.maxn of num; s1:array1.maxn of str;procedure strtonum(str1:str;var num1:num);var i:integer;beginnum1.len:=length(str1);for i:=1 to num1.len do num1.si:=ord(str1num1.len-i+1)-ord(0);end;procedure mult(x,y:num;var z: num );var i,j,len:integer;beginfillchar(z,sizeof(z),0);for i:= 1 to x.len do for j:=1 to y.len do begin inc(z.si+j-1, x.si*y.sj); inc(z.si+j,z.si+j-1 div 10); z.si+j-1:=z.si+j-1 mod 10; end;len:=x.len+y.len+1;while (len1) and (z.slen=0) do len:=len-1;z.len:=len;end;procedure bigger(x,y:num;var z:num);var i:integer;beginif x.leny.len then begin z.len:=x.len;z.s:=x.s end elseif x.len1) and (x.si=y.si) do i:=i-1; if x.si=y.si then z.s:=x.s else z.s:=y.s;end;end;beginreadln(n,k);readln(st);fillchar(f,sizeof(f),0);for i:=1 to n do begin s1i:=copy(st,1,i); strtonum(s1i,fi); end;for i:=2 to k+1 do for j:=n