第5講 動(dòng)態(tài)規(guī)劃的題型

1、動(dòng)態(tài)規(guī)劃的題型動(dòng)態(tài)規(guī)劃的題型計(jì)算所有方案計(jì)算所有方案計(jì)算一些階段性明顯、但不具備最優(yōu)子結(jié)計(jì)算一些階段性明顯、但不具備最優(yōu)子結(jié)構(gòu)特征的問(wèn)題構(gòu)特征的問(wèn)題多進(jìn)程的最優(yōu)化決策問(wèn)題多進(jìn)程的最優(yōu)化決策問(wèn)題雙重動(dòng)態(tài)規(guī)劃雙重動(dòng)態(tài)規(guī)劃自上而下的動(dòng)態(tài)規(guī)劃自上而下的動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃前進(jìn)行預(yù)處理動(dòng)態(tài)規(guī)劃前進(jìn)行預(yù)處理狀態(tài)的定義是提高效率的關(guān)鍵狀態(tài)的定義是提高效率的關(guān)鍵一、計(jì)算所有方案 對(duì)于一些階段性強(qiáng)、但不屬于最優(yōu)化的問(wèn)題，是對(duì)于一些階段性強(qiáng)、但不屬于最優(yōu)化的問(wèn)題，是否也可以借助動(dòng)態(tài)規(guī)劃方法呢？如果我們可以找否也可以借助動(dòng)態(tài)規(guī)劃方法呢？如果我們可以找出狀態(tài)轉(zhuǎn)移的關(guān)系，并在狀態(tài)轉(zhuǎn)移方程出狀態(tài)轉(zhuǎn)移的關(guān)系，并在狀態(tài)轉(zhuǎn)移方程中

2、去掉中去掉最佳性要求最佳性要求（minmin或或maxmax），將），將擴(kuò)展子狀態(tài)擴(kuò)展子狀態(tài)的所有行動(dòng)作為決策，則可以例舉出由初始狀態(tài)的所有行動(dòng)作為決策，則可以例舉出由初始狀態(tài)至目標(biāo)狀態(tài)的所有方案。至目標(biāo)狀態(tài)的所有方案。例題2 過(guò)河卒 如圖，如圖，A A點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)點(diǎn)有一個(gè)過(guò)河卒，需要走到目標(biāo)B B點(diǎn)。點(diǎn)。卒行走的規(guī)則：可以向下、或者向右。卒行走的規(guī)則：可以向下、或者向右。 同時(shí)在棋盤(pán)上的任一點(diǎn)有一個(gè)對(duì)方的馬（如上圖的同時(shí)在棋盤(pán)上的任一點(diǎn)有一個(gè)對(duì)方的馬（如上圖的C C點(diǎn)）點(diǎn)）, ,該馬該馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)。例如所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)

3、方馬的控制點(diǎn)。例如上圖上圖C C點(diǎn)上的馬可以控制點(diǎn)上的馬可以控制8 8個(gè)點(diǎn)（圖中的個(gè)點(diǎn)（圖中的P1P1，P2.P8P2.P8）。卒不能）。卒不能通過(guò)對(duì)方馬的控制點(diǎn)。通過(guò)對(duì)方馬的控制點(diǎn)。 棋盤(pán)用坐標(biāo)表示，棋盤(pán)用坐標(biāo)表示，A A點(diǎn)（點(diǎn)（0 0，0 0）、）、B B點(diǎn)（點(diǎn)（n n，m m）(n,m(n,m為不超過(guò)為不超過(guò)2020的整數(shù)的整數(shù), ,并由鍵盤(pán)輸入并由鍵盤(pán)輸入) )，同樣馬的位置坐標(biāo)是需要給出的（約定：，同樣馬的位置坐標(biāo)是需要給出的（約定：CACA，同時(shí)，同時(shí)CBCB）。現(xiàn)在要求你計(jì)算出卒從）?，F(xiàn)在要求你計(jì)算出卒從A A 點(diǎn)能夠到達(dá)點(diǎn)能夠到達(dá)B B點(diǎn)點(diǎn)的路徑的條數(shù)。的路徑的條數(shù)。輸輸 入：

4、入：鍵盤(pán)輸入鍵盤(pán)輸入B B點(diǎn)的坐標(biāo)點(diǎn)的坐標(biāo)(n,m)(n,m)以及對(duì)方馬的坐標(biāo)（以及對(duì)方馬的坐標(biāo)（X X，Y Y）輸輸 出：出：屏幕輸出一個(gè)整數(shù)（路徑的條數(shù)）。屏幕輸出一個(gè)整數(shù)（路徑的條數(shù)）。輸入輸出樣例：輸入輸出樣例：輸入：輸入：3 3 2 23 3 2 2輸出：輸出：0 0按照題意，對(duì)方的馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)，卒按照題意，對(duì)方的馬所在的點(diǎn)和所有跳躍一步可達(dá)的點(diǎn)稱為對(duì)方馬的控制點(diǎn)，卒不能通過(guò)對(duì)方馬的控制點(diǎn)。在卒出發(fā)之前，必須計(jì)算對(duì)方馬的所有控制點(diǎn)。不能通過(guò)對(duì)方馬的控制點(diǎn)。在卒出發(fā)之前，必須計(jì)算對(duì)方馬的所有控制點(diǎn)。顯然，若（顯然，若（0，0）或（）或（n,m）為控

5、制點(diǎn)，則輸出路徑數(shù)為）為控制點(diǎn)，則輸出路徑數(shù)為0。設(shè)。設(shè)constmove:array1.8,1.2ofinteger=(1,-2),(1,2),(2,1),(2,-1),(-1,2),(-1,-2),(-2,1),(-2,-1)； movek，1.2為馬為馬沿沿k方向跳躍一步的水平增量和垂直增量方向跳躍一步的水平增量和垂直增量varlist:array-1.20,-1.20 of comp；路徑數(shù)序列，其中路徑數(shù)序列，其中l(wèi)isti,j為卒從為卒從(0,0)到到(i,j)的路徑數(shù)的路徑數(shù)can:array0.20,0.20 of boolean； 點(diǎn)點(diǎn)(i,j)允許卒通行的標(biāo)志允許卒通行的標(biāo)

6、志馬的初始位置為（馬的初始位置為（x,y）。我們按照下述方式計(jì)算）。我們按照下述方式計(jì)算can序列：序列：canx,y false； 對(duì)方馬所在的點(diǎn)為控制點(diǎn)對(duì)方馬所在的點(diǎn)為控制點(diǎn)for i1 to 8 do begin從（從（x，y）出發(fā)，沿）出發(fā)，沿8個(gè)跳馬方向計(jì)算控制點(diǎn)個(gè)跳馬方向計(jì)算控制點(diǎn)jx+movei,1； 計(jì)算計(jì)算i方向的跳馬位置方向的跳馬位置(j，k)ky+movei,2；if (j=0) and (k=0) and (j=n) and (k=m) 若（若（j,k）在界內(nèi)，則為控制點(diǎn)）在界內(nèi)，則為控制點(diǎn)then canj,k false；end；forif (not can0,0)

7、or(not cann,m) 若卒的起點(diǎn)和終點(diǎn)為控制點(diǎn)，則輸出路徑數(shù)若卒的起點(diǎn)和終點(diǎn)為控制點(diǎn)，則輸出路徑數(shù)0 then writeln(0)else begin 計(jì)算和輸出卒從（計(jì)算和輸出卒從（0，0）走到（）走到（n,m）點(diǎn)的路徑數(shù)）點(diǎn)的路徑數(shù)listn,m； end；else1 1、計(jì)算對(duì)方馬的控制點(diǎn)、計(jì)算對(duì)方馬的控制點(diǎn) 我們按照由上而下、由左而右的順序，將卒可能到達(dá)的每一我們按照由上而下、由左而右的順序，將卒可能到達(dá)的每一個(gè)位置（個(gè)位置（i,ji,j）(0in(0in，0jm)0jm)設(shè)為階段設(shè)為階段, ,顯然這樣做，可以顯然這樣做，可以取消對(duì)狀態(tài)的枚舉。取消對(duì)狀態(tài)的枚舉。 首 先 ，

8、將 卒 的 出 發(fā) 點(diǎn) （首 先 ， 將 卒 的 出 發(fā) 點(diǎn) （ 0 0 ， 0 0 ） 的 路 徑 數(shù) 設(shè) 為） 的 路 徑 數(shù) 設(shè) 為 1 1（list0,01list0,01），并將該位置設(shè)為控制點(diǎn)（），并將該位置設(shè)為控制點(diǎn)（can0,0 can0,0 falsfals）。然后從（）。然后從（0 0，0 0）出發(fā)，按照由上而下、由左而右的順）出發(fā)，按照由上而下、由左而右的順序計(jì)算卒經(jīng)過(guò)每一個(gè)可行點(diǎn)的路徑數(shù)。若（序計(jì)算卒經(jīng)過(guò)每一個(gè)可行點(diǎn)的路徑數(shù)。若（i i，j j）為可行點(diǎn)，則）為可行點(diǎn)，則卒可由上側(cè)的（卒可由上側(cè)的（i-1,ji-1,j）和左側(cè)的（）和左側(cè)的（i,j-1i,j-1）進(jìn)入該

9、點(diǎn)。將這兩點(diǎn)）進(jìn)入該點(diǎn)。將這兩點(diǎn)的路徑數(shù)加起來(lái)，即為從（的路徑數(shù)加起來(lái)，即為從（0 0，0 0）走到（）走到（i i，j j ）的路徑數(shù)，即）的路徑數(shù)，即listi,j=listi-1,j+listi,j-1listi,j=listi-1,j+listi,j-1（i i，j j）非控制點(diǎn)）非控制點(diǎn)依次類推，最后得出的依次類推，最后得出的listn,mlistn,m即為問(wèn)題的解。即為問(wèn)題的解。2 2、計(jì)算和輸出卒從（、計(jì)算和輸出卒從（0 0，0 0）走到（）走到（n,mn,m）點(diǎn)的路徑條數(shù)）點(diǎn)的路徑條數(shù)由此得出算法：由此得出算法：fillchar(list,sizeof(list),0)fill

10、char(list,sizeof(list),0)； 路徑數(shù)序列初始化路徑數(shù)序列初始化 list0,01list0,01； 卒從（卒從（0 0，0 0）出發(fā)的路徑數(shù)為）出發(fā)的路徑數(shù)為1 1，該位置不，該位置不再允許卒通行再允許卒通行 can0,0 falsecan0,0 false； for i0 to n dofor i0 to n do對(duì)于每個(gè)可行點(diǎn)對(duì)于每個(gè)可行點(diǎn), ,小兵要么從左側(cè)、要么小兵要么從左側(cè)、要么從上方走到從上方走到, ,由此計(jì)算從由此計(jì)算從(0,0)(0,0)到到(i,j)(i,j)的路徑數(shù)的路徑數(shù) for j0 to m do if cani,jthen listi,jli

11、sti- for j0 to m do if cani,jthen listi,jlisti-1,j+listi,j-11,j+listi,j-1；輸出卒從（輸出卒從（0 0，0 0）走到（）走到（n,mn,m）點(diǎn)的路徑條數(shù)）點(diǎn)的路徑條數(shù)listn,mlistn,m；2 2、計(jì)算和輸出卒從（、計(jì)算和輸出卒從（0 0，0 0）走到（）走到（n,mn,m）點(diǎn)的路徑條數(shù)）點(diǎn)的路徑條數(shù)例題3 n重冪 設(shè)給定設(shè)給定n n個(gè)變量個(gè)變量x1,x2,xn,x1,x2,xn,將這些變量依序作底和各層冪，可將這些變量依序作底和各層冪，可得出左圖的得出左圖的n n重冪。這里將重冪。這里將n n重冪看作是不確定的，當(dāng)

12、在其中加入重冪看作是不確定的，當(dāng)在其中加入適當(dāng)?shù)睦ㄌ?hào)后，才能成為一個(gè)確定的適當(dāng)?shù)睦ㄌ?hào)后，才能成為一個(gè)確定的n n重冪。通常將重冪。通常將n n重冪的理解重冪的理解為右圖所示的形狀：為右圖所示的形狀：123xxxxn不同的加括號(hào)方式導(dǎo)致不同的不同的加括號(hào)方式導(dǎo)致不同的n n重冪。例如，當(dāng)重冪。例如，當(dāng)n=4n=4時(shí)，時(shí)，x1,x2,x3,x4x1,x2,x3,x4的全部的全部4 4重冪有重冪有5 5個(gè)。試設(shè)計(jì)一個(gè)算法，對(duì)個(gè)。試設(shè)計(jì)一個(gè)算法，對(duì)n n個(gè)變量個(gè)變量計(jì)算出有多少個(gè)不同的計(jì)算出有多少個(gè)不同的n n重冪重冪。狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程 設(shè)設(shè)cici為為i i個(gè)變量計(jì)算出的不同的個(gè)變量計(jì)算出的

13、不同的i i重冪的重冪的個(gè)數(shù)。個(gè)數(shù)。 C1=1C1=1； ci= ci= ； 目標(biāo)是計(jì)算目標(biāo)是計(jì)算cncn。注意高精度運(yùn)算。注意高精度運(yùn)算11*ijjicjcreadln(n)readln(n)； 讀變量數(shù)讀變量數(shù) fillchar(c,sizeof(c),0);fillchar(c,sizeof(c),0);creat(c1,1);creat(c1,1);建立值為建立值為1 1的的c c數(shù)組數(shù)組for i:=2 to n dofor i:=2 to n do for j:=1 to i-1 do for j:=1 to i-1 do begin begin multiply2(cj,ci-j

14、,a); multiply2(cj,ci-j,a);acjacjci-jci-j plus(ci,a,b);plus(ci,a,b);bci+abci+a ci:=bci:=b end; end; 輸出輸出cncn三、雙重動(dòng)態(tài)規(guī)劃三、雙重動(dòng)態(tài)規(guī)劃 當(dāng)問(wèn)題的決策為復(fù)合決策（也就是一些子決當(dāng)問(wèn)題的決策為復(fù)合決策（也就是一些子決策的排列）時(shí)，將每個(gè)復(fù)合決策細(xì)化成若干個(gè)策的排列）時(shí)，將每個(gè)復(fù)合決策細(xì)化成若干個(gè)子決策，并在每個(gè)子決策后面增設(shè)一個(gè)狀態(tài)。子決策，并在每個(gè)子決策后面增設(shè)一個(gè)狀態(tài)。這樣，后面的子決策只在前面的子決策達(dá)到最這樣，后面的子決策只在前面的子決策達(dá)到最優(yōu)解時(shí)才進(jìn)行轉(zhuǎn)移優(yōu)解時(shí)才進(jìn)行轉(zhuǎn)移 。

15、 使用使用“雙重動(dòng)態(tài)規(guī)劃的條件：即原來(lái)每個(gè)復(fù)雙重動(dòng)態(tài)規(guī)劃的條件：即原來(lái)每個(gè)復(fù)合決策的各個(gè)子決策之間也滿足最優(yōu)化原理和合決策的各個(gè)子決策之間也滿足最優(yōu)化原理和無(wú)后效性。即符合最優(yōu)決策的子決策也是最優(yōu)無(wú)后效性。即符合最優(yōu)決策的子決策也是最優(yōu)決策，前面的子決策不影響后面的子決策。決策，前面的子決策不影響后面的子決策。例題5 金明的預(yù)算方案 金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一金明今天很開(kāi)心，家里購(gòu)置的新房就要領(lǐng)鑰匙了，新房里有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說(shuō)：對(duì)他說(shuō)：“你的房間需要購(gòu)買哪些物品，怎么

16、布置，你說(shuō)了算，你的房間需要購(gòu)買哪些物品，怎么布置，你說(shuō)了算，只要不超過(guò)只要不超過(guò)N N元錢就行元錢就行”。今天一早，金明就開(kāi)始做預(yù)算了，。今天一早，金明就開(kāi)始做預(yù)算了，他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的，下表就是一些主件與附件的例子：件的，下表就是一些主件與附件的例子：主件附件電腦打印機(jī)，掃描儀書(shū)柜圖書(shū) 如果要買歸類為附件的物品，必須先買該附件所屬如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個(gè)主件可以有的主件。每個(gè)主件可以有0 0個(gè)、個(gè)、1 1個(gè)或個(gè)或2 2個(gè)附件。附件不個(gè)附件。附件不再有從屬于自己的附件

17、。金明想買的東西很多，肯定會(huì)再有從屬于自己的附件。金明想買的東西很多，肯定會(huì)超過(guò)媽媽限定的超過(guò)媽媽限定的N N元。于是，他把每件物品規(guī)定了一個(gè)元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為重要度，分為5 5等：用整數(shù)等：用整數(shù)1515表示，第表示，第5 5等最重要。他等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是還從因特網(wǎng)上查到了每件物品的價(jià)格（都是1010元的整數(shù)元的整數(shù)倍）。他希望在不超過(guò)倍）。他希望在不超過(guò)N N元（可以等于元（可以等于N N元）的前提下，元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。使每件物品的價(jià)格與重要度的乘積的總和最大。 設(shè)第設(shè)第j j件物品的價(jià)格為件物

18、品的價(jià)格為vjvj，重要度為，重要度為wjwj，共選中，共選中了了k k件物品，編號(hào)依次為件物品，編號(hào)依次為j1j1，j2j2，jkjk，則所求的，則所求的總和為：總和為：vj1vj1* *wj1+vj2wj1+vj2* *wj2+ +vjkwj2+ +vjk* *wjkwjk。（其中（其中* *為乘號(hào)）為乘號(hào)）請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單。請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購(gòu)物單?！据斎胛募枯斎胛募据斎胛募枯斎胛募udget.in budget.in 的第的第1 1行，為兩個(gè)正行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開(kāi)：整數(shù)，用一個(gè)空格隔開(kāi)： N mN m（其中（其中N N（3200032

19、000）表示總錢數(shù)，）表示總錢數(shù)，m m（6060）為希望購(gòu)買物品的個(gè)數(shù)）為希望購(gòu)買物品的個(gè)數(shù)） 從第從第2 2行到第行到第m+1m+1行，第行，第j j行給出了編號(hào)為行給出了編號(hào)為j-1j-1的物的物品的基本數(shù)據(jù)，每行有品的基本數(shù)據(jù)，每行有3 3個(gè)非負(fù)整數(shù)個(gè)非負(fù)整數(shù) v p qv p q（其中（其中v v表示該物品的價(jià)格（表示該物品的價(jià)格（v10000v0q0，表示該物品為附件，表示該物品為附件，q q是所屬主件的編號(hào)）是所屬主件的編號(hào)）【輸出文件】輸出文件【輸出文件】輸出文件budget.outbudget.out只有一個(gè)正整數(shù)，只有一個(gè)正整數(shù)，為不超過(guò)總錢數(shù)的物品的價(jià)格與重要度乘積的總和

20、的為不超過(guò)總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（最大值（200000200000）。）。題目大意 給出購(gòu)買總費(fèi)用M和N件物品，每件物品的特性有：價(jià)格、重要度、以及是主件還是附件。對(duì)于每個(gè)附件，必須購(gòu)買主件，才能購(gòu)買該附件。求在購(gòu)買總費(fèi)用內(nèi)，能購(gòu)買多少物品，使得所有物品的價(jià)格*重要度的總和最大。數(shù)據(jù)結(jié)構(gòu) 本題與經(jīng)典動(dòng)態(tài)規(guī)劃本題與經(jīng)典動(dòng)態(tài)規(guī)劃0101背包問(wèn)題十分類似。但不同點(diǎn)是，對(duì)于每個(gè)背包問(wèn)題十分類似。但不同點(diǎn)是，對(duì)于每個(gè)附件，必須先購(gòu)買主件。所以，考慮把附件和主件捆綁在一起考慮。設(shè)附件，必須先購(gòu)買主件。所以，考慮把附件和主件捆綁在一起考慮。設(shè) 物品物品i i的價(jià)格為的價(jià)格為titi、重

21、要度為、重要度為pipi；FiFi表示使用表示使用i i元可以購(gòu)買的價(jià)格元可以購(gòu)買的價(jià)格* *重要度的最大值。主附件組合的方式有四種，其中第重要度的最大值。主附件組合的方式有四種，其中第i i種組合的單價(jià)為種組合的單價(jià)為ttitticonst maxt=32000; maxn=60;const maxt=32000; maxn=60;type ftype=array0.maxtof longint;type ftype=array0.maxtof longint;var var f:ftype; fi f:ftype; fi表示使用表示使用i i元可以購(gòu)買的價(jià)格元可以購(gòu)買的價(jià)格* *重要度的最

22、大值重要度的最大值 ff:array1.4of ftype;ffk,j ff:array1.4of ftype;ffk,j為使用為使用j j元且物品元且物品i i采用第采用第k k種組合方式種組合方式可以購(gòu)買的價(jià)格可以購(gòu)買的價(jià)格* *重要度的最大值重要度的最大值 t,p,prt,pp:array1.maxnof longint; t,p,prt,pp:array1.maxnof longint; 物品物品i i的價(jià)格為的價(jià)格為titi、重要度、重要度為為pipi； prtiprti是附件是附件i i所屬的主件序號(hào)，所屬的主件序號(hào)，ppippi為主件為主件i i的附件個(gè)數(shù)的附件個(gè)數(shù) g:arra

23、y1.maxn,1.2of longint;gI,j g:array1.maxn,1.2of longint;gI,j為主件為主件i i的第的第j j個(gè)附件的序號(hào)個(gè)附件的序號(hào) pt,tt:array1.4of longint; pt,tt:array1.4of longint;第第i i種組合的價(jià)格為種組合的價(jià)格為ttitti；重要度；重要度* *價(jià)格價(jià)格為為ptipti tott,n, :longint; tott,n, :longint; 總錢數(shù)為總錢數(shù)為totttott、希望購(gòu)買的物品數(shù)為、希望購(gòu)買的物品數(shù)為n n 分析主附件組合的四種方式主件主件i i沒(méi)有附件的：沒(méi)有附件的：pipi*

24、 *titi；tt1=tt1=titi主件主件i i只有一個(gè)附件只有一個(gè)附件j j：pipi* *ti+pjti+pj* *tjtj，tt2= tt2= ti+tjti+tj主件主件i i有兩個(gè)附件有兩個(gè)附件j1j1和和j2j2。有四種組合方式。有四種組合方式僅購(gòu)買主件僅購(gòu)買主件i i：pipi* *titi，tt1=tt1=titi購(gòu)買主件購(gòu)買主件i i和附件和附件j1j1：pipi* *ti+pj1ti+pj1* *tj1tj1，tt2= ti+tj1tt2= ti+tj1購(gòu)買主件購(gòu)買主件i i和附件和附件j2j2：pipi* *ti+pj2ti+pj2* *tj2tj2，tt3= ti+

25、tj2tt3= ti+tj2購(gòu)買主件購(gòu)買主件i i、附件、附件j1j1和和j2j2：pipi* *ti+pj1ti+pj1* *tj1+ pj2tj1+ pj2* *tj2tj2，tt4= tt4= ti+tj1+tj2ti+tj1+tj2每一種組合方式為每一種組合方式為1 1個(gè)背包，分別使用動(dòng)態(tài)規(guī)劃解背包問(wèn)個(gè)背包，分別使用動(dòng)態(tài)規(guī)劃解背包問(wèn)題。題。動(dòng)態(tài)規(guī)劃階段階段i i：依次按照物品數(shù)遞增的順序考慮前：依次按照物品數(shù)遞增的順序考慮前i i個(gè)物品的最優(yōu)個(gè)物品的最優(yōu)方案。每個(gè)階段需要進(jìn)行雙重動(dòng)態(tài)規(guī)劃方案。每個(gè)階段需要進(jìn)行雙重動(dòng)態(tài)規(guī)劃1 1、計(jì)算前、計(jì)算前i i個(gè)物品的所有可能的組合方案?jìng)€(gè)物品的所有

26、可能的組合方案計(jì)算物品計(jì)算物品i i的組合方案數(shù)的組合方案數(shù)kkkk；狀態(tài)狀態(tài)k k ：枚舉每一個(gè)組合方案：枚舉每一個(gè)組合方案k k（1kkk1kkk）決策決策j j ：按照：按照遞減順序遞減順序( (如果是遞增順序呢如果是遞增順序呢?)?)枚舉花費(fèi)枚舉花費(fèi)j j（j=mttkj=mttk）設(shè)設(shè)ffk,jffk,j為使用為使用j j元且物品元且物品i i采用第采用第k k種組合方式可以購(gòu)種組合方式可以購(gòu)買的價(jià)格買的價(jià)格* *重要度的最大值重要度的最大值 ffk,j= max(ffk,j= max(考慮前考慮前i-1i-1個(gè)物件花費(fèi)個(gè)物件花費(fèi)j-ttkj-ttk的最優(yōu)的最優(yōu)值值+ +主件主件i

27、i的第的第k k種組合中價(jià)格與重要度乘積的和種組合中價(jià)格與重要度乘積的和) )2 2、計(jì)算四個(gè)背包中的最大值、計(jì)算四個(gè)背包中的最大值Fj Fj 狀態(tài)j：按照遞減方向枚舉所有可能的錢數(shù)(j= m0)決策k：枚舉組合方案（1kkk） fj= 。在遞推了n個(gè)物品后的fm即為問(wèn)題的解。算法復(fù)雜度O(MN)。（M表示總費(fèi)用，N表示物品數(shù)）,max41jkffkreadln(tott,n);readln(tott,n);輸入總錢數(shù)和希望購(gòu)買的物品數(shù)輸入總錢數(shù)和希望購(gòu)買的物品數(shù) for i:=1 to n dofor i:=1 to n do begin begin readln(ti,pi,prti);

28、readln(ti,pi,prti);輸入物品輸入物品i i的價(jià)格、重要的價(jià)格、重要度和主附件標(biāo)志度和主附件標(biāo)志 if prti0 if prti0若物品若物品i i是附件，則所屬主件的附件個(gè)數(shù)是附件，則所屬主件的附件個(gè)數(shù)加加1 1，物品，物品i i進(jìn)入該主件的附件表進(jìn)入該主件的附件表 then begin then begin inc(ppprti);gprti,ppprti:=i inc(ppprti);gprti,ppprti:=i； endend； end;forend;for fillchar(f,sizeof(f),0); fillchar(f,sizeof(f),0);狀態(tài)轉(zhuǎn)移方

29、程初始化狀態(tài)轉(zhuǎn)移方程初始化 for i:=1 to n dofor i:=1 to n do枚舉每一個(gè)物品枚舉每一個(gè)物品 if prti=0if prti=0若物品若物品i i是主件是主件 then begin then begin case ppi of case ppi of 0:begin 0:begin若物品若物品i i沒(méi)有附件，則設(shè)組合標(biāo)志沒(méi)有附件，則設(shè)組合標(biāo)志1 1；計(jì)算；計(jì)算物品物品i i的價(jià)格與重要度的乘積，記下物品的價(jià)格與重要度的乘積，記下物品i i的重要度的重要度 kk:=1;pt1:=pikk:=1;pt1:=pi* *ti;tt1:=titi;tt1:=ti end;

30、end; 1:begin 1:begin若物品若物品i i有一個(gè)附件，則設(shè)組合標(biāo)志有一個(gè)附件，則設(shè)組合標(biāo)志2 2 kk:=2; pt1:=pi kk:=2; pt1:=pi* *ti;tt1:=ti;ti;tt1:=ti;計(jì)算計(jì)算物品物品i i的價(jià)格與重要度的乘積，記下物品的價(jià)格與重要度的乘積，記下物品i i的重要度的重要度 pt2:=pi pt2:=pi* *ti+pgi,1ti+pgi,1* *tgi,1;tgi,1; tt2:=ti+tgi,1 tt2:=ti+tgi,1計(jì)算物品計(jì)算物品i i的價(jià)格與重的價(jià)格與重要度的乘積要度的乘積+ +其附件價(jià)格與重要度的乘積，記下物品其附件價(jià)格與重要

31、度的乘積，記下物品i i與附與附件的重要度的和件的重要度的和 end; end; 2:begin2:begin若物品若物品i i有兩個(gè)附件，則設(shè)組合標(biāo)志有兩個(gè)附件，則設(shè)組合標(biāo)志4 4 kk:=4; kk:=4; pt1:=pi pt1:=pi* *ti;tt1:=ti;ti;tt1:=ti;計(jì)算物品計(jì)算物品i i的價(jià)格與重要度的的價(jià)格與重要度的乘積，記下物品乘積，記下物品i i的重要度的重要度 pt2:=pi pt2:=pi* *ti+pgi,1ti+pgi,1* *tgi,1;tgi,1; tt2:=ti+tgi,1; tt2:=ti+tgi,1;計(jì)算物品計(jì)算物品i i的價(jià)格與重要度的乘積的

32、價(jià)格與重要度的乘積+ +第第1 1個(gè)附件價(jià)格與重要度的乘積，記下物品個(gè)附件價(jià)格與重要度的乘積，記下物品i i與第與第1 1個(gè)附件的重要度的個(gè)附件的重要度的和和 pt3:=pi pt3:=pi* *ti+pgi,2ti+pgi,2* *tgi,2;tgi,2; tt3:=ti+tgi,2; tt3:=ti+tgi,2; 計(jì)算物品計(jì)算物品i i的價(jià)格與重要度的乘積的價(jià)格與重要度的乘積+ +第第2 2個(gè)附件價(jià)格與重要度的乘積，記下物品個(gè)附件價(jià)格與重要度的乘積，記下物品i i與第與第2 2個(gè)附件的重要度個(gè)附件的重要度的和的和 pt4:=pi pt4:=pi* *ti+pgi,1ti+pgi,1* *t

33、gi,1+pgi,2tgi,1+pgi,2* *tgi,2;tgi,2; t4:=ti+tgi,1+tgi,2 t4:=ti+tgi,1+tgi,2 計(jì)算物品計(jì)算物品i i的價(jià)格與重要度的價(jià)格與重要度的乘積的乘積+ +第第1 1個(gè)附件價(jià)格與重要度的乘積個(gè)附件價(jià)格與重要度的乘積+ +第第2 2個(gè)附件價(jià)格與重要度個(gè)附件價(jià)格與重要度的乘積，記下物品的乘積，記下物品i i與兩個(gè)附件的重要度的和與兩個(gè)附件的重要度的和 end endend;caseend;casefor k:=1 to kk dofor k:=1 to kk do枚舉枚舉4 4種組合方案種組合方案 beginbegin ffk:=f;

34、ffk:=f;記下前記下前i-1i-1種物品的狀態(tài)轉(zhuǎn)移方程種物品的狀態(tài)轉(zhuǎn)移方程 for j:=tott downto ttk do for j:=tott downto ttk do ffkj:=max(ffkj,ffkj- ffkj:=max(ffkj,ffkj-ttk+ptk)ttk+ptk)按照遞減方向枚舉第按照遞減方向枚舉第k k種組合方案下所有種組合方案下所有可能的錢數(shù)，計(jì)算該條件下物品價(jià)格與重要度乘積的最大可能的錢數(shù)，計(jì)算該條件下物品價(jià)格與重要度乘積的最大總和總和 end;forend;forfor j:=tott downto 0 dofor j:=tott downto 0 d

35、o按照遞減方向枚舉所有可能的按照遞減方向枚舉所有可能的錢數(shù)，在所有的組合方案中尋找物品價(jià)格與重要度乘積的錢數(shù)，在所有的組合方案中尋找物品價(jià)格與重要度乘積的最大總和最大總和 for k:=1 to kk do fj:=max(fj,ffkj) for k:=1 to kk do fj:=max(fj,ffkj)end;thenend;thenwriteln(ftott);writeln(ftott);不超過(guò)總錢數(shù)不超過(guò)總錢數(shù)totttott的物品價(jià)格與重要的物品價(jià)格與重要度乘積的最大總和為問(wèn)題解度乘積的最大總和為問(wèn)題解 怎樣對(duì)多個(gè)并行的、可劃分階段的進(jìn)程怎樣對(duì)多個(gè)并行的、可劃分階段的進(jìn)程進(jìn)行最優(yōu)

36、化決策，關(guān)鍵是如何存儲(chǔ)狀態(tài)。進(jìn)行最優(yōu)化決策，關(guān)鍵是如何存儲(chǔ)狀態(tài)。多進(jìn)程問(wèn)題的狀態(tài)數(shù)目十分龐大，每一個(gè)多進(jìn)程問(wèn)題的狀態(tài)數(shù)目十分龐大，每一個(gè)狀態(tài)的存儲(chǔ)量大，且又是求多條最佳路徑，狀態(tài)的存儲(chǔ)量大，且又是求多條最佳路徑，這就要求在存儲(chǔ)上必須做一定的優(yōu)化后才這就要求在存儲(chǔ)上必須做一定的優(yōu)化后才有可能實(shí)現(xiàn)算法的程序化。主要的優(yōu)化就有可能實(shí)現(xiàn)算法的程序化。主要的優(yōu)化就是：舍棄一切不必要的存儲(chǔ)量。是：舍棄一切不必要的存儲(chǔ)量。四、多進(jìn)程的最優(yōu)化決策問(wèn)題例題6 方格取數(shù) 設(shè)有設(shè)有n n* *n n的方格圖（的方格圖（），我們將其中的某些方格中填入正整數(shù)，而其他的方），我們將其中的某些方格中填入正整數(shù)，而其他的方格

37、中則放入數(shù)字。如下圖所示（見(jiàn)樣例）：格中則放入數(shù)字。如下圖所示（見(jiàn)樣例）： 某人從圖的左上角的點(diǎn)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角某人從圖的左上角的點(diǎn)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的點(diǎn)。在走過(guò)的路上，它可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字的點(diǎn)。在走過(guò)的路上，它可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字）。此人從點(diǎn)到點(diǎn)共走兩次，試找出條這樣的路徑，使得取得的數(shù)之和）。此人從點(diǎn)到點(diǎn)共走兩次，試找出條這樣的路徑，使得取得的數(shù)之和最大。最大。輸入：輸入的第一行為一個(gè)整數(shù)（表示的方格圖），接下來(lái)的每行右三個(gè)整輸入：輸入的第一行為一個(gè)整數(shù)（表示的方格圖），接下來(lái)的

38、每行右三個(gè)整數(shù)，前兩個(gè)表示位置，第三個(gè)數(shù)為該位置上所放的數(shù)。一行單獨(dú)的表示輸入結(jié)數(shù)，前兩個(gè)表示位置，第三個(gè)數(shù)為該位置上所放的數(shù)。一行單獨(dú)的表示輸入結(jié)束。束。輸出：只需輸出一個(gè)整數(shù)，表示條路徑上取得的最大的和輸出：只需輸出一個(gè)整數(shù)，表示條路徑上取得的最大的和1 1、狀態(tài)的設(shè)計(jì)、狀態(tài)的設(shè)計(jì) 對(duì)于本題來(lái)說(shuō)，狀態(tài)的選定和存儲(chǔ)對(duì)整個(gè)問(wèn)題的處理起了決定性對(duì)于本題來(lái)說(shuō)，狀態(tài)的選定和存儲(chǔ)對(duì)整個(gè)問(wèn)題的處理起了決定性的作用。的作用。我們從（我們從（1 1，1 1）出發(fā)，每走一步作為一個(gè)階段，則可以分成）出發(fā)，每走一步作為一個(gè)階段，則可以分成2 2* *n-1n-1個(gè)個(gè)階段：階段： 第一個(gè)階段，兩條路徑從（第一個(gè)階

39、段，兩條路徑從（1 1，1 1）出發(fā)；）出發(fā)； 第二個(gè)階段，兩條路徑可達(dá)（第二個(gè)階段，兩條路徑可達(dá)（2 2，1 1）和（）和（1 1，2 2）；）； 第三個(gè)階段，兩條路徑可達(dá)的位置集合為（第三個(gè)階段，兩條路徑可達(dá)的位置集合為（3 3，1 1）、（）、（2 2，2 2）和）和（1 1，3 3）；）； 第第2 2* *n-1n-1個(gè)階段，兩條路徑匯聚（個(gè)階段，兩條路徑匯聚（n n，n n）；）；在第在第k(1k2k(1k2* *n-1)n-1)個(gè)階段，兩條路徑的終端坐標(biāo)（個(gè)階段，兩條路徑的終端坐標(biāo)（x x1 1，y y1 1）（）（x x2 2，y y2 2）位于對(duì)應(yīng)的右下對(duì)角線上。如下圖所示：位

40、于對(duì)應(yīng)的右下對(duì)角線上。如下圖所示： 1 1、狀態(tài)的設(shè)計(jì)、狀態(tài)的設(shè)計(jì) 如果我們將兩條路徑走第如果我們將兩條路徑走第i i步的所有可能位置定義為當(dāng)前階段的步的所有可能位置定義為當(dāng)前階段的狀態(tài)的話，面對(duì)的問(wèn)題就是如何存儲(chǔ)狀態(tài)了。方格取數(shù)問(wèn)題的狀狀態(tài)的話，面對(duì)的問(wèn)題就是如何存儲(chǔ)狀態(tài)了。方格取數(shù)問(wèn)題的狀態(tài)數(shù)目十分龐大，每一個(gè)位置是兩維的，且又是求兩條最佳路徑，態(tài)數(shù)目十分龐大，每一個(gè)位置是兩維的，且又是求兩條最佳路徑，這就要求在存儲(chǔ)上必須做一定的優(yōu)化后才有可能實(shí)現(xiàn)算法的程序這就要求在存儲(chǔ)上必須做一定的優(yōu)化后才有可能實(shí)現(xiàn)算法的程序化。主要的優(yōu)化就是：舍棄一切不必要的存儲(chǔ)量。為此，我們?nèi)』?。主要的?yōu)化就是：舍

41、棄一切不必要的存儲(chǔ)量。為此，我們?nèi)∥恢弥械奈恢弥械膞 x坐標(biāo)（坐標(biāo)（x x1 1，x x2 2）作狀態(tài)，其中）作狀態(tài)，其中（1x1x1 1kk）andand（x x1 11n1n）andand（1x1x2 2kk）andand（x x2 21n1n）直接由直接由x x坐標(biāo)計(jì)算對(duì)應(yīng)的坐標(biāo)計(jì)算對(duì)應(yīng)的y y坐標(biāo)：坐標(biāo)：（y y1 1=k+1-x=k+1-x1 1）andand（y y1 11n1n）andand（y y2 2=k+1-x=k+1-x2 2）andand（y y2 21n 1n 2 2、狀態(tài)轉(zhuǎn)移方程、狀態(tài)轉(zhuǎn)移方程 設(shè)兩條路徑在設(shè)兩條路徑在k k階段的狀態(tài)為（階段的狀態(tài)為（x x1 1，

42、x x2 2）。由（）。由（y y1 1=k+1-x=k+1-x1 1）（y y1 11.n1.n）得出第一條路徑的坐標(biāo)為（）得出第一條路徑的坐標(biāo)為（x x1 1，y y1 1）；由（）；由（y y2 2=k+1-x=k+1-x2 2）（y y2 21.n1.n）得出第二條路徑的坐標(biāo)為（）得出第二條路徑的坐標(biāo)為（x x2 2，y y2 2）。）。 假設(shè)在假設(shè)在k-1k-1階段，兩條路徑的狀態(tài)為（階段，兩條路徑的狀態(tài)為（x x1 1，x x2 2）且（）且（x x1 1，x x2 2）位于（位于（x x1 1，x x2 2）狀態(tài)的左鄰或下鄰位置。因此我們?cè)O(shè)兩條路徑的延）狀態(tài)的左鄰或下鄰位置。因此

43、我們?cè)O(shè)兩條路徑的延伸方向?yàn)樯旆较驗(yàn)閐 d1 1和和d d2 2：d di i=0=0，表明第，表明第i i條路徑由（條路徑由（x xi i，y yi i）向右延伸至）向右延伸至（x xi i，y yi i）；）；d di i=1=1，表明第，表明第i i條路徑由（條路徑由（x xi i，y yi i）向下延伸至（）向下延伸至（x xi i，y yi i）（）（1i21i2）。）。 顯然（顯然（x x1 1= x= x2 2）（d d1 1= d= d2 2），表明兩條路徑重合，同時(shí)取走），表明兩條路徑重合，同時(shí)取走了（了（x x1 1，y y1 1）和（）和（x x1 1，y y1 1）中的數(shù)

44、，這種取法當(dāng)然不可能得到最）中的數(shù)，這種取法當(dāng)然不可能得到最大數(shù)和的。大數(shù)和的。2 2、狀態(tài)轉(zhuǎn)移方程、狀態(tài)轉(zhuǎn)移方程分析兩種可能：分析兩種可能：若若x x1 1=x=x2 2，則兩條路徑會(huì)合于，則兩條路徑會(huì)合于x x1 1狀態(tài)，可取走（狀態(tài)，可取走（x x1 1，y y1 1）中的數(shù)）中的數(shù)( (如如下圖下圖) )； x x1 1(x(x2 2)x)x1 1=x=x2 2 x x2 2(x(x1 1)若若x x1 1xx2 2，則在，則在k k階段，第一條路徑由階段，第一條路徑由x x1 1狀態(tài)延伸至狀態(tài)延伸至x x1 1狀態(tài)，第狀態(tài)，第二條路徑由二條路徑由x x2 2狀態(tài)延伸至狀態(tài)延伸至x x

45、2 2狀態(tài)，兩條路徑可分別取走（狀態(tài)，兩條路徑可分別取走（x x1 1，y y1 1）和（和（x x2 2，y y2 2）中的數(shù)）中的數(shù)( (如下圖如下圖) )；設(shè)設(shè) fkfk，x x1 1，x x2 2在第在第k k階段，兩條路徑分別行至階段，兩條路徑分別行至x x1 1狀態(tài)和狀態(tài)和x x2 2狀態(tài)的狀態(tài)的最大數(shù)和。顯然最大數(shù)和。顯然k=1k=1時(shí)，時(shí)，f1f1，1 1，1=01=0；k2k2時(shí)，時(shí)，fkfk，x x1 1，x x2 2=maxfk-1=maxfk-1， x x1 1，x x2 2+(x+(x1 1，y y1 1) )的數(shù)字的數(shù)字xx1 1=x=x2 2，fk-1fk-1，

46、x x1 1，x x2 2+(x+(x1 1，y y1 1) )的數(shù)字的數(shù)字+(x+(x2 2，y y2 2) )的數(shù)字的數(shù)字xx1 1xx2 2 1k2 1k2* *n-1n-1，x x1 1可達(dá)可達(dá)x x1 1的狀態(tài)集合，的狀態(tài)集合，x x2 2可達(dá)可達(dá)x x2 2的狀態(tài)集合，的狀態(tài)集合，（x x1 1xx2 2）(d d1 1dd2 2) )； 由于第由于第k k個(gè)階段的狀態(tài)轉(zhuǎn)移方程僅與第個(gè)階段的狀態(tài)轉(zhuǎn)移方程僅與第k-1k-1個(gè)階段的狀態(tài)發(fā)生個(gè)階段的狀態(tài)發(fā)生聯(lián)系，因此不妨設(shè)聯(lián)系，因此不妨設(shè) f f0 0第第k-1k-1個(gè)階段的狀態(tài)轉(zhuǎn)移方程；個(gè)階段的狀態(tài)轉(zhuǎn)移方程； f f1 1第第k k個(gè)

47、階段的狀態(tài)轉(zhuǎn)移方程；個(gè)階段的狀態(tài)轉(zhuǎn)移方程；初始時(shí)，初始時(shí)，f f0 011，1=01=0。經(jīng)過(guò)。經(jīng)過(guò)2 2* *n-1n-1個(gè)階段后得出的個(gè)階段后得出的f f0 0nn，nn即為問(wèn)題即為問(wèn)題的解。的解。3 3、多進(jìn)程決策的動(dòng)態(tài)規(guī)劃、多進(jìn)程決策的動(dòng)態(tài)規(guī)劃 由于方格取數(shù)問(wèn)題是對(duì)兩條路徑進(jìn)行最優(yōu)化決策的，因此稱這類由于方格取數(shù)問(wèn)題是對(duì)兩條路徑進(jìn)行最優(yōu)化決策的，因此稱這類動(dòng)態(tài)規(guī)劃為動(dòng)態(tài)規(guī)劃為分階段、多進(jìn)程分階段、多進(jìn)程的最優(yōu)化決策過(guò)程。設(shè)的最優(yōu)化決策過(guò)程。設(shè)階段階段i i：準(zhǔn)備走第：準(zhǔn)備走第i i步（步（1i21i2* *n-1n-1）；）；狀態(tài)（狀態(tài)（x x1 1，x x2 2）：）： 第第i-1i

48、-1步的狀態(tài)號(hào)（步的狀態(tài)號(hào)（1x1x1 1，x x2 2i-1i-1。x x1 1，x x2 21.n1.n）決策（決策（d d1 1，d d2 2）：第一條路徑由）：第一條路徑由x x1 1狀態(tài)出發(fā)沿狀態(tài)出發(fā)沿d d1 1方向延伸、第二方向延伸、第二條路徑由條路徑由x x2 2狀態(tài)狀態(tài) 出發(fā)沿出發(fā)沿d d2 2方向延伸，可使得兩條路徑的數(shù)和方向延伸，可使得兩條路徑的數(shù)和最大（最大（0d0d1 1，d d2 211。方向。方向0 0表示右移，方向表示右移，方向1 1表示下移）；表示下移）；fillchar(f0fillchar(f0，sizeof(f0)sizeof(f0)，0) 0)； 行走

49、前的狀態(tài)轉(zhuǎn)行走前的狀態(tài)轉(zhuǎn)移方程初始化移方程初始化 f01f01，1010；for i2 to n+n-1 dofor i2 to n+n-1 do階段：準(zhǔn)備走第階段：準(zhǔn)備走第i i步步 begin begin fillchar(f1 fillchar(f1，sizeof(f1)sizeof(f1)，0) 0)； 走第走第i i步的狀態(tài)步的狀態(tài)轉(zhuǎn)移方程初始化轉(zhuǎn)移方程初始化 for x for x1 11 to i-1 do1 to i-1 do枚舉兩條路徑在第枚舉兩條路徑在第i-1i-1步時(shí)的狀態(tài)步時(shí)的狀態(tài)x x1 1和和x x2 2 for x for x2 21 to i-1 do1 to

50、i-1 do begin begin 計(jì)算計(jì)算y y1 1和和y y2 2； if (xif (x1 1，y y1 1)和和(x (x2 2，y y2 2)在界內(nèi)在界內(nèi) thenthen for d for d1 10 to 1 do 0 to 1 do 決策：計(jì)算兩條路徑的最決策：計(jì)算兩條路徑的最佳延伸方向佳延伸方向 for d for d2 20 to 1 do 0 to 1 do beginbegin 第第1 1條路徑沿條路徑沿d d1 1方向延伸至方向延伸至(x (x1 1，y y1 1）；）； 第第2 2條路徑沿條路徑沿d d2 2方向延伸至方向延伸至(x (x2 2，y y2 2)

51、 )； i f ( ( xi f ( ( x1 1， y y1 1) ) 和和 ( x( x2 2， y y2 2) ) 在 界在 界內(nèi)內(nèi))(d)(d1 1dd2 2)(x)(x1 1xx2 2) ) 計(jì)算第計(jì)算第i i步的狀態(tài)步的狀態(tài)轉(zhuǎn)移方程轉(zhuǎn)移方程 then f1x then f1x1 1，x x2 2maxf0 xmaxf0 x1 1，x x2 2+mapx+mapx1 1，y y1 1xx1 1=x=x2 2，f0 xf0 x1 1，x x2 2+mapx+mapx1 1，y y1 1+mapx+mapx2 2，y y2 2xx1 1xx2 2 end end；forfor end e

52、nd；for for f0f1 f0f1； 記下第記下第i i步的狀態(tài)轉(zhuǎn)移方程步的狀態(tài)轉(zhuǎn)移方程 endend；forfor輸出兩條路徑取得的最大數(shù)和輸出兩條路徑取得的最大數(shù)和f0nf0n，n n例題13 過(guò)河【輸入文件】輸入文件【輸入文件】輸入文件river.inriver.in的第一行有一個(gè)正整數(shù)的第一行有一個(gè)正整數(shù)L L（1 L 1 L 10109 9），表示獨(dú)木橋的長(zhǎng)度。第二行有三個(gè)正整數(shù)），表示獨(dú)木橋的長(zhǎng)度。第二行有三個(gè)正整數(shù)S S，T T，MM，分別表，分別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中1ST10

53、1ST10，1M 1001M 100。第三行有。第三行有MM個(gè)不同的正整數(shù)分別表示這個(gè)不同的正整數(shù)分別表示這MM個(gè)石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒(méi)有石子）。個(gè)石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒(méi)有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開(kāi)。所有相鄰的整數(shù)之間用一個(gè)空格隔開(kāi)?！据敵鑫募枯敵鑫募据敵鑫募枯敵鑫募iver.outriver.out只包括一個(gè)整數(shù)，表示青蛙過(guò)河最少需只包括一個(gè)整數(shù)，表示青蛙過(guò)河最少需要踩到的石子數(shù)。要踩到的石子數(shù)。方法2、動(dòng)態(tài)規(guī)劃 1、以橋?yàn)橐?guī)劃對(duì)象、以橋?yàn)橐?guī)劃對(duì)象 設(shè)optn為青蛙到達(dá)n位置最少需要踩到的石子數(shù)。 rockn= 位置無(wú)石子

54、位置有石子nn01minnrockinoptnoptTiS這個(gè)方程的時(shí)間復(fù)雜度是O（n）級(jí)的 ，顯然在競(jìng)賽時(shí)限內(nèi)， n109的極限數(shù)據(jù)是無(wú)法出解的 2、以石子為規(guī)劃對(duì)象、以石子為規(guī)劃對(duì)象 相比上限為109的橋長(zhǎng)L而言，石子數(shù)M要小得多，因?yàn)槠渖舷蕹淦淞繛?00。我們以石子為對(duì)象，由左而右地進(jìn)行規(guī)劃。設(shè) xi為橋上由左而右順序的第i個(gè)石子位置；ai,j為青蛙跳至xi左方相對(duì)距離為j的位置時(shí)所經(jīng)過(guò)的最少石子總數(shù)（0in，0jt-1）。若j=0，說(shuō)明青蛙踩到了橋上的第i個(gè)石子。初始時(shí)，ai,j=n+1。顯然，青蛙在跳躍過(guò)程中有兩種可能：第1種情況：xi-j位置位于xi-1的左方，即xi-jxi-1

55、顯然，跳至xi-j位置經(jīng)過(guò)的最少石子總數(shù)為ai-1,j-xi+xi-1第2種情況：xi-j位置位于xi-1的右方，即xi-jxi-1 顯然，如果青蛙能夠由xi-1-v位置跳至xi-j位置，則跳至xi-j位置經(jīng)過(guò)的石子總數(shù)為ai-1,v或者為ai-1,v+1（j=0時(shí)，即踩到了橋上的第i個(gè)石子）。但究竟v多大時(shí)，才能使得最少石子數(shù)最少呢，我們無(wú)法預(yù)知，只能在0t-1的范圍內(nèi)一一枚舉v，從中找出經(jīng)過(guò)的最少石子數(shù)。 ai,j=最后，我們枚舉青蛙跳出獨(dú)木橋前的最后一個(gè)起跳位置最后，我們枚舉青蛙跳出獨(dú)木橋前的最后一個(gè)起跳位置xn-xn-i(0it-1i(0it-1），從中計(jì)算出青蛙過(guò)河最少需要踩到的石子

56、數(shù)），從中計(jì)算出青蛙過(guò)河最少需要踩到的石子數(shù)現(xiàn)在動(dòng)態(tài)規(guī)劃的關(guān)鍵變成了如何判斷青蛙能否從現(xiàn)在動(dòng)態(tài)規(guī)劃的關(guān)鍵變成了如何判斷青蛙能否從xi-1-vxi-1-v位置跳至位置跳至xi-jxi-j位置，即青蛙能否跳到相對(duì)距離為位置，即青蛙能否跳到相對(duì)距離為v v遠(yuǎn)的位置。遠(yuǎn)的位置。 ,min10inati狀態(tài)轉(zhuǎn)移方程狀態(tài)轉(zhuǎn)移方程0,11 1, 1min0,1 1, 1min 11, 11010jixjixjixvixviajixjixjixvixviaixjixixixjiatvtv位置位置跳至青蛙能夠從位置位置跳至青蛙能夠從如果相對(duì)距離vs(s-1)的話，青蛙是一定能夠跳到的如果相對(duì)距離vs(s-1)，

57、則用一次跳躍的距離范圍遞推設(shè)n為橋上的石子數(shù)（1nm）；bi為能否用s到t的一次跳躍距離跳至i遠(yuǎn)的標(biāo)志bi=true i=0bi= 1i90cv為青蛙能否跳到相對(duì)距離為v遠(yuǎn)的標(biāo)志（v90） cv= jibortjs) 1(0) 1(0ssvvbssvtruevfalse解決一個(gè)特例 當(dāng)S=T時(shí)上述等式是無(wú)法使用的，因?yàn)樵谶@種情況下，青蛙不可避免地跳到其位置為S倍數(shù)的石子上，因此只需要在所有石子中，統(tǒng)計(jì)出坐標(biāo)是S倍數(shù)的石子個(gè)數(shù)就可以了。 var L,s,t,m,n,i,j,v,best:longint; x:array 0.100 of longint;由左而右記錄每個(gè)石子的位置由左而右記錄每個(gè)石子的位置 a:array 0.100,0.9 of longint;ai,j為青蛙跳到為青蛙跳到xi-j位置經(jīng)過(guò)的位置經(jīng)過(guò)的最少石子數(shù)最少石子數(shù) b:array -10.90 of boolean;bi記錄能否用記錄能否用s到到t這