淺談動(dòng)態(tài)規(guī)劃

淺談動(dòng)態(tài)規(guī)劃安徽師大附中葉國(guó)平動(dòng)態(tài)規(guī)劃的基本模型有一類活動(dòng)的過程，由于它的特殊性，可將分成若干個(gè)互相聯(lián)系的階段，在它的每一個(gè)階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。因此各個(gè)階段決策的選取不能任意確定，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展。當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線。這種把一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策最優(yōu)化問題。動(dòng)態(tài)規(guī)劃的基本模型[多段圖問題]多段圖G=（V，E）是一個(gè)有向圖。它具有如下特性：圖中的結(jié)點(diǎn)被劃分成k≥2個(gè)不相交的集合Vi，1≤i≤k，其中V1和Vk分別只有一個(gè)結(jié)點(diǎn)s（源點(diǎn)）和t（匯點(diǎn)）。圖中所有的邊<u，v>均具有如下性質(zhì)：若u∈Vi，則v∈Vi+1，1≤i＜k-1，且每條邊<u，v>都附有成本c(u,v)。從s到t的一條路徑成本是這條路徑上邊的成本和。多段圖問題是求由s到t的最小成本路徑。

動(dòng)態(tài)規(guī)劃的基本模型V1

V2

V3

V4

V5

動(dòng)態(tài)規(guī)劃的基本模型分析：在k段圖的每一條由源點(diǎn)s到匯點(diǎn)t的路徑可以看成是在k-2個(gè)階段中作出的某個(gè)決策序列的相應(yīng)結(jié)果。第i次決策就是確定Vi+1哪個(gè)結(jié)點(diǎn)在這條路徑上，1≤i≤k-2。分析：設(shè)COST(i,j)是從Vi中的結(jié)點(diǎn)j到匯點(diǎn)t的最小成本路徑的成本。于是向前處理法立即就可得到COST(i,j)=min{c(j,l)+COST(i+1,l)}l∈Vi+1，<j,l>∈E若<j,t>∈E，有COST(k-1,j)=c(j,t);若<j,t>!∈E，有COST(k-1,j)=∞動(dòng)態(tài)規(guī)劃的基本模型COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=min{2+COST(3,6),7+COST(3,7)}=9COST(2,4)=11+COST(3,8)=18COST(2,5)=min{11+COST(3,7),8+COST(3,8)}=15COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16動(dòng)態(tài)規(guī)劃的基本模型在計(jì)算每一個(gè)COST(i,j)的同時(shí)，記下每個(gè)狀態(tài)（結(jié)點(diǎn)j）所作的決策（即，使c(j,l)+COST(i+1,l)取最小值的l值，設(shè)它為D(i,j),則很容易的求出這條最小路徑。對(duì)于上例：可得到D(3,6)=10D(3,7)=10D(3,8)=10D(2,2)=7D(2,3)=6D(2,4)=8D(2,5)=8D(1,1)=2這樣設(shè)最小成本路徑使s=1,v2,v3,……,vk-1,t=12,立即可知，v2=D(1,1)=2,v3=D(2,D(1,1))=7,v4=D(3,D(2,D(1,1))=10.所以最短路徑應(yīng)該是1—>2—>7—>10—>12階段：據(jù)空間順序或時(shí)間順序?qū)栴}的求解劃分階段。狀態(tài)：描述事物的性質(zhì)，不同事物有不同的性質(zhì)，因而用不同的狀態(tài)來刻畫。對(duì)問題的求解狀態(tài)的描述是分階段的。決策：根據(jù)題意要求，對(duì)每個(gè)階段所做出的某種選擇性操作。狀態(tài)轉(zhuǎn)移方程：用數(shù)學(xué)公式描述與階段相關(guān)的狀態(tài)間的演變規(guī)律。動(dòng)態(tài)規(guī)劃的基本概念:動(dòng)態(tài)規(guī)劃的基本概念:動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，是解決多階段決策過程最優(yōu)化的一種方法。所謂多階段決策過程，是將所研究的過程劃分為若干個(gè)相互聯(lián)系的階段，在求解時(shí)，對(duì)每一個(gè)階段都要做出決策，前一個(gè)決策確定以后，常常會(huì)影響下一個(gè)階段的決策。動(dòng)態(tài)規(guī)劃的兩個(gè)必要條件最優(yōu)子結(jié)構(gòu)：對(duì)于多階段決策問題，如果每一個(gè)階段的最優(yōu)決策序列的子序列也是最優(yōu)的，且決策序列具有“無后效性”，就可以將此決策方法理解為最優(yōu)子結(jié)構(gòu)。動(dòng)態(tài)規(guī)劃的兩個(gè)必要條件無后效性：動(dòng)態(tài)規(guī)劃法的最優(yōu)解通常是由一系列最優(yōu)決策組成的決策序列，最優(yōu)子結(jié)構(gòu)就是這些最優(yōu)決策序列中的一個(gè)子序列，對(duì)于每個(gè)子序列再做最優(yōu)決策會(huì)產(chǎn)生新的最優(yōu)決策（子）序列，如果某個(gè)決策只受當(dāng)前最優(yōu)決策子序列的影響，而不受當(dāng)前決策可能產(chǎn)生的新的最優(yōu)決策子序列的影響，則可以理解這個(gè)最優(yōu)決策具有無后效性。動(dòng)態(tài)規(guī)劃的兩個(gè)必要條件具體地說，如果一個(gè)問題被劃分各個(gè)階段之后，階段i中的狀態(tài)只能由階段i-1中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與其它狀態(tài)沒有關(guān)系，特別是與未發(fā)生的狀態(tài)沒有關(guān)系。從圖論的角度去考慮，如果把這個(gè)問題中的狀態(tài)定義成圖中的頂點(diǎn)，兩個(gè)狀態(tài)之間的轉(zhuǎn)移定義為邊，轉(zhuǎn)移過程中的權(quán)值增量定義為邊的權(quán)值，則構(gòu)成一個(gè)有向無環(huán)加權(quán)圖，因此，這個(gè)圖可以進(jìn)行“拓?fù)渑判颉?，至少可以按它們拓?fù)渑判虻捻樞蛉澐蛛A段。動(dòng)態(tài)規(guī)劃的基本概念:動(dòng)態(tài)規(guī)劃所依據(jù)的是“最優(yōu)性原理”?！白顑?yōu)性原理”可陳述為：不論初始狀態(tài)和第一步?jīng)Q策是什么，余下的決策相對(duì)于前一次決策所產(chǎn)生的新狀態(tài)，構(gòu)成一個(gè)最優(yōu)決策序列。最優(yōu)決策序列的子序列，一定是局部最優(yōu)決策子序列。包含有非局部最優(yōu)的決策子序列，一定不是最優(yōu)決策序列。動(dòng)態(tài)規(guī)劃的基本概念:動(dòng)態(tài)規(guī)劃的指導(dǎo)思想是：在做每一步?jīng)Q策時(shí)，列出各種可能的局部解，之后依據(jù)某種判定條件，舍棄那些肯定不能得到最優(yōu)解的局部解。這樣，在每一步都經(jīng)過篩選，以每一步都是最優(yōu)的來保證全局是最優(yōu)的。篩選相當(dāng)于最大限度地有效剪枝（從搜索角度看），效率會(huì)十分高。但它又不同于貪心法。貪心法只能做到局部最優(yōu)，不能保證全局最優(yōu)，因?yàn)橛行﹩栴}不符合最優(yōu)性原理。貪心法產(chǎn)生一個(gè)按貪心策略形成的判定序列，該序列不保證解是全局最優(yōu)的。而動(dòng)態(tài)規(guī)劃會(huì)產(chǎn)生許多判定序列，再按最優(yōu)性原理對(duì)這些序列加以篩選，去除那些非局部最優(yōu)的子序列。兩種算法的差別0/1背包問題

———最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問題[一般描述]一個(gè)旅行者有一個(gè)最多能用m公斤的背包，現(xiàn)在有n件物品，它們的重量分別是W1,W2,……Wn，它們的價(jià)值分別為C1,C2,……Cn。若每種物品只有一件求旅行者能獲得最大總價(jià)值。

0/1背包問題

———最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問題[分析]顯然這個(gè)題可用深度優(yōu)先方法對(duì)每件物品進(jìn)行枚舉(選或不選用0,1控制).程序簡(jiǎn)單,但是當(dāng)n的值很大的時(shí)候不能滿足時(shí)間要求，時(shí)間復(fù)雜度為O()。按遞歸的思想我們可以把問題分解為子問題,使用遞歸函數(shù)。0/1背包問題

———最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問題[分析]設(shè)

F[i][j]表示前i件物品，總重量不超過j的最優(yōu)價(jià)值。則F[i][j]=max(F[i-1][j-W[i]]+C[i],F[i-1][j])[目標(biāo)]F[n][m]即為最優(yōu)解[初始化]F[0][j]=0,

F[i][0]=0;0/1背包問題

———最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問題#include<iostream>#include<cstdio>#definemax(a,b)(a>b)?(a):(b)usingnamespacestd;const

int

MaxM=1001;const

int

MaxN=101;intm,n,i,j;intw[MaxN],c[MaxN],f[MaxN][MaxM];intmain(void){cin>>m>>n;

for(i=1;i<=n;i++)

cin>>w[i]>>c[i];for(i=1;i<=n;i++)

f[i][0]=0;for(i=1;i<=m;i++)

f[0][i]=0;for(i=1;i<=n;i++)for(j=1;j<=m;j++)

{if(j>=w[i])f[i][j]=max(f[i-

1][j],f[i-1][j-w[i]]+c[i]);elsef[i][j]=f[i-1][j];}cout<<"maxp="<<f[n][m];return0;}0/1背包問題

———最簡(jiǎn)單的動(dòng)態(tài)規(guī)劃問題[DP程序](數(shù)組降維之后，只要把循環(huán)順序改變一下）#include<iostream>#include<cstdio>#definemax(a,b)(a>b)?(a):(b)#defineMaxM

30000#defineMaxN101usingnamespacestd;intw[MaxN],c[MaxN],f[MaxM];intmain(void){intm,n,i,j;cin>>m>>n;for(i=1;i<=n;i++)

cin>>w[i]>>c[i];for(j=0;j<=m;j++)f[j]=0;

for(i=1;i<=n;i++)for(j=m;j>=w[i];j--)

f[j]=max(f[j],f[j-w[i]]+c[i]);cout<<"maxp="<<f[m];return0;}多多看DVD多多進(jìn)幼兒園了,她的叔叔決定給他買一些動(dòng)畫片DVD晚上看。可是爺爺規(guī)定他們只能在一定的時(shí)間段L看完。多多列出一張表要叔叔給她買N張DVD碟，多多給每張碟都打了分Mi（Mi>0），打分越高的碟說明多多越愛看。每張碟有播放的時(shí)間Ti?？墒浅霈F(xiàn)了一個(gè)奇怪的問題，買碟的地方只買給顧客M（M＜N）張碟，不會(huì)多也不會(huì)少。這可讓多多叔叔為難了。怎么可以在N張碟中只買M張而且在規(guī)定時(shí)間看完，而且使總價(jià)值最高呢?多多看DVD狀態(tài)F[i][j][k]表示處理到第i張碟片在時(shí)間段長(zhǎng)為j的情況下看了k張碟片得到的最優(yōu)解狀態(tài)轉(zhuǎn)移方程

f[i][j][k]=max{f[i-1][j][k],f[i-1][j-t[i]][k-1]+w[i]}

多多看DVD目標(biāo)狀態(tài)f[n][l][m]初始狀態(tài)F[i][j][0]=0(k=0)F[i][j][k]=-∞(k≠0)變量循環(huán)順序先循環(huán)k，再循環(huán)i，最后循環(huán)j金明的預(yù)算方案金明有N元錢可以購買物品布置房間，他把想買的物品分為兩類：主件與附件，附件是從屬于某個(gè)主件的，如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個(gè)主件可以有0個(gè)、1個(gè)或2個(gè)附件。附件不再有從屬于自己的附件。他把每件物品規(guī)定了一個(gè)重要度w[i]，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格v[i]（都是10元的整數(shù)倍）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。金明的預(yù)算方案本題是有依賴的背包問題，這種背包問題的物品間存在某種“依賴”的關(guān)系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡(jiǎn)化起見，我們先設(shè)沒有某個(gè)物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時(shí)依賴多件物品。將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個(gè)問題的簡(jiǎn)化條件可知所有的物品由若干主件和依賴于每個(gè)主件的一個(gè)附件集合組成。金明的預(yù)算方案設(shè)f[i][j]表示前i個(gè)物品在不超過j元（可以等于j元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。按照背包問題的一般思路，僅考慮一個(gè)主件和它的附件集合。它包括：①一個(gè)也不選；②僅選擇主件，③選擇主件后再選擇一個(gè)附件，④選擇主件后再選擇兩個(gè)附件。在上面四種情況下選取最大值。for(i=1;i<=n;i++)for(j=1;j<=m;j++){f[i][j]=f[i-1][j];//一個(gè)也不選

if(j>=w[i][0])//僅選擇主件

f[i][j]=max(f[i][j],f[i-1][j-w[i][0]]+c[i][0]);if(j>=w[i][0]+w[i][1])//選擇主件后再選第擇一個(gè)附件

f[i][j]=max(f[i][j],f[i-1][j-w[i][0]-w[i][1]]+c[i][0]+c[i][1]);if(j>=w[i][0]+w[i][2])//選擇主件后再選第擇一個(gè)附件

f[i][j]=max(f[i][j],f[i-1][j-w[i][0]-w[i][2]]+c[i][0]+c[i][2]);if(j>=w[i][0]+w[i][1]+w[i][2])//選擇主件后再選擇兩個(gè)附件

f[i][j]=max(f[i][j],f[i-1][j-w[i][0]-w[i][1]-w[i][2]]+c[i][0]+c[i][1]+c[i][2]);}最小重量機(jī)器設(shè)計(jì)問題描述設(shè)某一機(jī)器由n個(gè)部件組成，每一種部件都可以從m個(gè)不同的供應(yīng)商處購得。設(shè)W[i][j]是從供應(yīng)商j處購得的部件i的重量，C[i][j]是相應(yīng)的價(jià)格。試設(shè)計(jì)一個(gè)算法，給出總價(jià)格不超過d的最小重量機(jī)器設(shè)計(jì)。輸入格式第一行有3個(gè)正整數(shù)n，m和d。接下來的2n行，每行n個(gè)數(shù)。前n行是c，后n行是w。輸出格式第一行輸出計(jì)算出的最小重量，第二行輸出每個(gè)部件的供應(yīng)商，如果有多組答案，要求輸出字典序最小的一種。最小重量機(jī)器設(shè)計(jì)狀態(tài)：f[i][j]表示前i個(gè)部件在價(jià)格和不超過j的條件下得到最小重量狀態(tài)轉(zhuǎn)移f[i][j]=min{f[i-1][j-c[i][k]]+w[i][k]}(k=1...m)

目標(biāo)狀態(tài)f[n][d]初始化f[[i][j]=∞最小重量機(jī)器設(shè)計(jì)怎樣保證得到的字典序最小？由于要輸出字典序最小的一種方案,所以逆序輸入怎樣輸出每個(gè)部件從哪個(gè)供應(yīng)商處購得？r[i][j]記下決策，即f[i][j]取最優(yōu)解時(shí)第i個(gè)部件從第r[i][j]個(gè)供應(yīng)商處購得。最小重量機(jī)器設(shè)計(jì)樣例334123321222123321222決策的產(chǎn)生f[3][4]=4 r[3][4]=1 c[3][1]=2F[2][2]=2 r[2][2]=3 c[2][3]=1F[1][1]=1 r[1][1]=1voidout(int

i,intj){if(i==1)

printf("%d\n",r[i][j]);else

printf("%d",r[i][j]);if(i>1)out(i-1,j-c[i][r[i][j]]);}攔截導(dǎo)彈問題

———最長(zhǎng)單調(diào)不上升序列[一般描述]

某國(guó)為了防御敵國(guó)的導(dǎo)彈襲擊，研發(fā)出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國(guó)的導(dǎo)彈來襲。由于該系統(tǒng)還在試驗(yàn)階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。攔截導(dǎo)彈問題

———最長(zhǎng)單調(diào)不上升序列[輸入格式]

輸入數(shù)據(jù)只有一行，該行包含若干個(gè)數(shù)據(jù)，之間用空格隔開，表示導(dǎo)彈依次飛來的高度（導(dǎo)彈最多有20枚，其高度為不大于30000的正整數(shù)）。[輸出格式]

輸出數(shù)據(jù)有兩行，第一行包含兩個(gè)數(shù)據(jù)，之間用半角逗號(hào)隔開。第一個(gè)數(shù)據(jù)表示一套系統(tǒng)最多能攔截的導(dǎo)彈數(shù)；第二個(gè)數(shù)據(jù)表示若要攔截所有導(dǎo)彈至少要多少套這樣的系統(tǒng)。第二行依次輸出攔截導(dǎo)彈數(shù)目最多的一套系統(tǒng)所攔截導(dǎo)彈的序號(hào)。攔截導(dǎo)彈問題

———最長(zhǎng)單調(diào)不上升序列[分析]

一套系統(tǒng)攔截導(dǎo)彈的問題本質(zhì)是在一個(gè)數(shù)列中尋求遞減的、未必連續(xù)的最長(zhǎng)子序列。設(shè)h[i]:導(dǎo)彈i…導(dǎo)彈n中可被攔截的最多導(dǎo)彈數(shù)(包括導(dǎo)彈i,1≤i≤n),顯然:h[i]=max{h[j](導(dǎo)彈i的高度≤導(dǎo)彈j的高度)}+1(i+1≤j≤n)一套系統(tǒng)攔截的最多導(dǎo)彈數(shù)best=max{h[i]}(1≤i≤n)w[i]:記憶表,即最佳方案中導(dǎo)彈i和導(dǎo)彈w[i]相繼被攔截,顯然:h[i]=h[w[i]]+1one:最佳方案中被攔截的第一枚導(dǎo)彈序號(hào),即:best=h[one]攔截導(dǎo)彈問題

———最長(zhǎng)單調(diào)不上升序列[程序](只輸出最多攔截導(dǎo)彈數(shù)best,并依次輸出被攔截導(dǎo)彈的序號(hào))memset(h,0,sizeof(h));memset(w,0,sizeof(w));best=0;for(i=n;i>=1;i--){h[i]=1;

w[i]=i;for(j=i+1;j<=n;j++)if((a[j]<=a[i])&&(h[j]+1)>h[i])

{h[i]=h[j]+1;

w[i]=j;

}if(h[i]>best)

{best=h[i];one=i;

}}while(one!=w[one])

{cout<<one;one=w[one];

}cout<one;攔截導(dǎo)彈問題

———最長(zhǎng)單調(diào)不上升序列[分析]

一套系統(tǒng)攔截的所有導(dǎo)彈中,最后一枚導(dǎo)彈的高度最低.設(shè)k:當(dāng)前配備的系統(tǒng)數(shù);low[k]:被第k套系統(tǒng)攔截的最后一枚導(dǎo)彈的高度,簡(jiǎn)稱系統(tǒng)k的最低高度(1≤k≤n)若導(dǎo)彈i的高度a[i]高于所有系統(tǒng)的最低高度,則需要增設(shè)一套系統(tǒng),即k=k+1,low[k]=a[i](1≤k≤n)若導(dǎo)彈i的高度a[i]低于某些系統(tǒng)的最低高度,則導(dǎo)彈i可被這些系統(tǒng)所攔截,用貪心法選擇最低高度最小的一套系統(tǒng)p,即low[p]=min{low[j](low[j])>a[i])}(1≤j≤k)然后:low[p]=a[i];攔截導(dǎo)彈問題

———最長(zhǎng)單調(diào)不上升序列[程序](計(jì)算配備的最少系統(tǒng)數(shù))k=1;//當(dāng)前配備的系統(tǒng)數(shù)low[1]=a[1];//第1套系統(tǒng)攔截導(dǎo)彈的最低高度for(i=2;i<=n;i++){p=0;//攔截導(dǎo)彈的最低高度最小的一套系統(tǒng)pfor(j=1;j<=k;j++)if((low[j]>=a[i])&&((p==0)||(low[j]<low[p]))p=j;if(p==0)

{k++;

low[k]=a[i];

}elselow[p]=a[i];}cout<<k;尼克的任務(wù)尼克每天上班之前都連接上英特網(wǎng)，接收他的上司發(fā)來的郵件，這些郵件包含了尼克主管的部門當(dāng)天要完成的全部任務(wù)，每一個(gè)任務(wù)都有一個(gè)開始時(shí)刻與一個(gè)持續(xù)時(shí)間構(gòu)成。尼克的一個(gè)工作日為N分鐘，從第一分鐘開始到第N分鐘結(jié)束。當(dāng)尼克到達(dá)單位后他就開始干活。如果在同一時(shí)刻有多個(gè)任務(wù)需要完成，尼克可以任選其中的一個(gè)來做，而其余的則由他的同事完成，反之，如果只有一個(gè)任務(wù)，則該任務(wù)必需由尼克去完成，假如某些任務(wù)開始時(shí)刻尼克正在工作，則這些任務(wù)也由尼克的同事完成。如果某任務(wù)于第P分鐘開始，持續(xù)時(shí)間為T分鐘，則該任務(wù)將在第P+T-1分鐘結(jié)束。尼克的任務(wù)請(qǐng)你寫一個(gè)程序，計(jì)算尼克應(yīng)該如何選取任務(wù)，才能獲得最大的空暇時(shí)間。輸入 輸出156 4 12164118581115

尼克的任務(wù)題目給定的數(shù)據(jù)規(guī)模十分巨大：1≤k≤10000。采用窮舉法顯然是不合適的。根據(jù)求最大空暇時(shí)間這一題解要求，先將k個(gè)任務(wù)放在一邊，以分鐘為階段，設(shè)置minute[i]表示從i分鐘到最后一分鐘所能獲得的最大空暇時(shí)間，決定該值的因素主要是從第i分鐘起到第n分鐘選取哪幾個(gè)任務(wù)，與i分鐘以前開始的任務(wù)無關(guān)，由后向前逐一推求各階段的minute值。

尼克的任務(wù)對(duì)于minute[i]，在任務(wù)表中找不到從第i分鐘開始的任務(wù)，則minute[i]=minute[i+1]+1；若在任務(wù)表中有一個(gè)或多個(gè)從第i分鐘開始的任務(wù)，這時(shí)，如何選定其中的一個(gè)任務(wù)去做，使所獲得的空暇時(shí)間最大，是求解的關(guān)鍵：minute[i]=max{minute[i+t[j]]}(條件是p[j]=i)，其中p[j]是第j個(gè)任務(wù)開始的時(shí)間，t[j]是第j個(gè)任務(wù)持續(xù)的時(shí)間尼克的任務(wù)狀態(tài)minute[i]表示從i分鐘到最后一分鐘所能獲得的最大空暇時(shí)間，狀態(tài)轉(zhuǎn)移方程

目標(biāo)狀態(tài)minute[1]初始化minute[n+1]=0添括號(hào)問題

———資源分配類動(dòng)態(tài)規(guī)劃[一般描述]題目很簡(jiǎn)單，給出N個(gè)數(shù)字，不改變它們的相對(duì)位置，在中間加入M個(gè)乘號(hào)和(N-M-1)個(gè)加號(hào)，還可以隨便加括號(hào)，使最終結(jié)果盡量大。因?yàn)槌颂?hào)和加號(hào)一共就是N-1個(gè)了，所以恰好每?jī)蓚€(gè)相鄰數(shù)字之間都有一個(gè)運(yùn)算符號(hào)。例如：N=5,

M=2，5個(gè)數(shù)字分別為1、2、3、4、5，可以加成：1*2*(3+4+5)=24 1*(2+3)*(4+5)=45(1*2+3)*(4+5)=45 (1+2+3)*4*5=120添括號(hào)問題

———資源分配類動(dòng)態(tài)規(guī)劃狀態(tài)f[i][j]表示前i個(gè)數(shù)字加j個(gè)乘號(hào)后能得到的最大值狀態(tài)轉(zhuǎn)移方程f[i][j]=max(f[i][j],f[k][j-1]*(s[i]-s[k]));初始化f[i][0]=s[i](s[i]表示前i個(gè)數(shù)字的和)f[i][j]=0(其余的i,j)目標(biāo)狀態(tài)f[n][m]機(jī)器分配總公司擁有高效生產(chǎn)設(shè)備M臺(tái)（相同的設(shè)備），準(zhǔn)備分給下屬的N個(gè)公司（公司編號(hào)從1到N）。各分公司若獲得這些設(shè)備，可以為國(guó)家提供一定的盈利。問：如何分配這M臺(tái)設(shè)備才能使國(guó)家得到的盈利最大？求出最大盈利值。分配原則：每個(gè)公司有權(quán)獲得任意數(shù)目的設(shè)備，但總臺(tái)數(shù)不得超過總設(shè)備數(shù)M。機(jī)器分配【輸入格式】第一行兩個(gè)數(shù)，第一個(gè)數(shù)是設(shè)備臺(tái)數(shù)M，第二個(gè)數(shù)是分公司數(shù)N。接下來是一個(gè)M*N的矩陣，第I行第J列的數(shù)表示將I臺(tái)機(jī)器分配給第J個(gè)公司的盈利。(M<=500，N<=100)【輸出格式】只有一個(gè)整數(shù)，即最大的盈利值。機(jī)器分配【輸入樣例】4355478910911121113【輸出格式】19

機(jī)器分配狀態(tài)f[i][j]表示把i臺(tái)機(jī)器分配給前j個(gè)公司的最大盈利狀態(tài)轉(zhuǎn)移方程f[i][j]=max(f[i][j],f[i-k][j-1]+a[k][j]);a[k][j]表示k臺(tái)機(jī)器分配給第j個(gè)公司的盈利初始化f[i][j]=0目標(biāo)狀態(tài)f[m][n]加分二叉樹

———區(qū)間類動(dòng)態(tài)規(guī)劃[一般描述]設(shè)一個(gè)n個(gè)節(jié)點(diǎn)的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點(diǎn)編號(hào)。每個(gè)節(jié)點(diǎn)都有一個(gè)分?jǐn)?shù)（均為正整數(shù)），記第j個(gè)節(jié)點(diǎn)的分?jǐn)?shù)為di，tree及它的每個(gè)子樹都有一個(gè)加分，任一棵子樹subtree（也包含tree本身）的加分計(jì)算方法如下：subtree的左子樹的加分×subtree的右子樹的加分＋subtree的根的分?jǐn)?shù)加分二叉樹

———區(qū)間類動(dòng)態(tài)規(guī)劃[一般描述]若某個(gè)子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；（1）tree的最高加分（2）tree的前序遍歷加分二叉樹

———區(qū)間類動(dòng)態(tài)規(guī)劃[一般描述]若某個(gè)子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；（1）tree的最高加分（2）tree的前序遍歷加分二叉樹

———區(qū)間類動(dòng)態(tài)規(guī)劃【輸入格式】

第1行：一個(gè)整數(shù)n（n＜30），為節(jié)點(diǎn)個(gè)數(shù)。第2行：n個(gè)用空格隔開的整數(shù)，為每個(gè)節(jié)點(diǎn)的分?jǐn)?shù)（分?jǐn)?shù)＜100）?！据敵龈袷健?/p>

第1行：一個(gè)整數(shù)，為最高加分（結(jié)果不會(huì)超過4,000,000,000）。第2行：n個(gè)用空格隔開的整數(shù)，為該樹的前序遍歷?！据斎霕永? 【輸出樣例】5 145571210 31245加分二叉樹如果整棵樹的權(quán)值最大，必然有左子樹的權(quán)值最大，右子樹德權(quán)值也最大，符合最優(yōu)性原理。加分二叉樹我們?cè)囍鴮懗鰻顟B(tài)轉(zhuǎn)移方程：

f[i,j]=max{i<=t<=j|d[t]+f[i,t-1]*f[t+1,j]}初始化：f(i,i)=d[i]目標(biāo)狀態(tài)：f(1,n)這樣，我們可以寫出一個(gè)動(dòng)態(tài)規(guī)劃的算法，可以按照狀態(tài)f[i,j]中i與j的距離來劃分階段(當(dāng)然也有其它的劃分階段的辦法),先處理掉邊界情況(空樹和只含有一個(gè)節(jié)點(diǎn)的樹),然后就可以按照階段自底向上進(jìn)行動(dòng)態(tài)規(guī)劃了，最后再遞歸地輸出，注意要保存每次決策。時(shí)間復(fù)雜度

O(n3)加分二叉樹voiddp(){int

i,j,k,d;for(d=1;d<=n-1;d++)for(i=1;i<=n-d;i++){j=i+d;for(k=i;k<=j;k++)if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k]){f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];

r[i][j]=k;}}}加分二叉樹voidout(int

b,inte)//輸出前序遍歷{intk;if(b<=e){k=r[b][e];if(first) {printf("%d",k);first=0;}else

printf("%d",k);out(b,k-1);out(k+1,e);}}石子歸并問題[問題描述]

在一個(gè)圓形操場(chǎng)的四周擺放著N堆石子(N<=100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選取相鄰的兩堆合并成新的一堆,并將新的一堆的石子數(shù),記為該次合并的得分.編一程序,由文件讀入堆棧數(shù)N及每堆棧的石子數(shù)(<=20).

(1)選擇一種合并石子的方案,使用權(quán)得做N－1次合并,得分的總和最小;

(2)選擇一種合并石子的方案,使用權(quán)得做N－1次合并,得分的總和最大;石子歸并問題【輸入格式】

第一行為石子堆數(shù)N；

第二行為每堆的石子數(shù),每?jī)蓚€(gè)數(shù)之間用一個(gè)空格分隔?！据敵龈袷健?/p>

輸出文件有兩行，各包含一個(gè)非負(fù)整數(shù)。第一行數(shù)是最小得分，第二行數(shù)是最大得分?！据斎霕永?4459【輸出樣例】4354石子歸并問題[分析]很多同學(xué)采用了盡可能逼近目標(biāo)的貪心法來逐次合并：從最上面的一堆開始，沿順時(shí)針方向排成一個(gè)序列。第一次選得分最?。ㄗ畲螅┑南噜弮啥押喜?，形成新的一堆；接下來，在N－1堆中選得分最?。ㄗ畲螅┑南噜弮啥押喜ⅰ?，依次類推，直至所有石子經(jīng)N－1次合并后形成一堆。例如有６堆石子，每堆石子數(shù)（從最上面一堆數(shù)起，順時(shí)針數(shù)）依次為３４６５４２。用貪心法（每次取得分最小的相鄰兩堆）合并，總得分：5＋9＋9＋15＋24＝62；但實(shí)際上還有總得分更低的合并方法：7＋6＋11＋13＋24＝61。方法是第一次合并：76

542；第二次合并