動態(tài)規(guī)劃 分類.doc

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