動(dòng)態(tài)規(guī)劃方法例題

動(dòng)態(tài)規(guī)劃方法例題最長上升子序列問題一個(gè)序列有N個(gè)數(shù)：A[1],A[2],…,A[N]，求出最長上升子序列的長度（LIS：longestincreasingsubsequence)。例如，對(duì)于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,5,9),(3,4,8)等等。這些子序列中最長的長度是4，比如子序列(1,3,5,9)，(1,3,5,8)和(1,3,4,8).分析假如我們考慮求A[1],A[2],…,A[i]的最長上升子序列的長度，其中i<N，那么上面的問題變成了原問題的一個(gè)子問題(問題規(guī)模變小了，可讓i=1,2,3等來分析)然后我們定義d(i)，表示前i個(gè)數(shù)中以A[i]結(jié)尾的最長上升子序列的長度。這個(gè)d(i)就是我們要找的狀態(tài)。如果我們把d(1)到d(N)都計(jì)算出來，那么最終我們要找的答案就是這里面最大的那個(gè)。狀態(tài)找到了，下一步來找狀態(tài)轉(zhuǎn)移方程。找出狀態(tài)轉(zhuǎn)移方程我們來看下面這6個(gè)數(shù)的序列：5，3，4，8，6，7我們可以得到：（下文的最長上升子序列都用LIS表示）前1個(gè)數(shù)的LIS長度d(1)=1(序列：5)前2個(gè)數(shù)的LIS長度d(2)=1(序列：3；3前面沒有比3小的)前3個(gè)數(shù)的LIS長度d(3)=2(序列：3，4；4前面有個(gè)比它小的3)第1階段決策選優(yōu)：求最長上升子序列的長度需要判斷當(dāng)前的數(shù)是否與其左邊最長上升子序列構(gòu)成一個(gè)上升序列，如果是，則：d(3)=max{d(1),d(2)}+1；即第3個(gè)數(shù)左邊最長上升子序列最大長度+1前4個(gè)數(shù)的LIS長度d(4)=3(序列：3，4，8；8前面比它小的有3個(gè)數(shù)，所以d(4)=max{d(1),d(2),d(3)}+1=3狀態(tài)轉(zhuǎn)移方程如果我們已經(jīng)求出了d(1)到d(i-1)，那么d(i)可以用下面的狀態(tài)轉(zhuǎn)移方程得到：d(i)=max{d(j)}+1（1）其中j=1,2,...,i-1,A[j]<A[i]有可能i前面的各個(gè)子序列中最后一個(gè)數(shù)都大于A[i]，那么d(i)=1（2）即它自身成為一個(gè)長度為1的子序列。求解LIS的C++代碼段intlen=1;for(inti=0;i<n;++i){d[i]=1;//數(shù)組d用來保存子序列的長度

for(intj=0;j<i;++j)if(A[j]<=A[i]&&d[j]+1>d[i])d[i]=d[j]+1;if(d[i]>len)len=d[i];}序列變化求最長非降子序列(longestnon-decreasingsubsequence)，與此問題近似。只需要將上述條件A[j]<A[i]改為：A[j]≤A[i]。求最長下降子序列(longestdecreasingsubsequence)，將上述條件A[j]<A[i]改為：A[j]>A[i]。如果要求最長非遞增子序列（longestnon-increasingsubsequence），將上述條件A[j]<A[i]改為：A[j]≥A[i]。藍(lán)橋杯網(wǎng)站練習(xí)系統(tǒng)算法訓(xùn)練中的“攔截導(dǎo)彈”問題，本質(zhì)上就是一個(gè)求最長非遞增子序列長度的題。例1攔截導(dǎo)彈某國為了防御敵國的導(dǎo)彈襲擊，開發(fā)出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個(gè)缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。（藍(lán)橋網(wǎng)編號(hào)：ALGO-13 VIP試題 ）攔截導(dǎo)彈輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，并依次輸出被攔截的導(dǎo)彈飛來時(shí)候的高度。輸入第一行輸入測試數(shù)據(jù)組數(shù)N（1<=N<=10）接下來一行輸入這組測試數(shù)據(jù)共有多少個(gè)導(dǎo)彈m（1<=m<=20）接下來行輸入導(dǎo)彈依次飛來的高度，所有高度值均是大于10的正整數(shù)。輸出輸出最多能攔截的導(dǎo)彈數(shù)目攔截導(dǎo)彈樣例輸入輸出樣例輸入SAMPLEINPUT:28389207155300299170158653883465SAMPLEOUTPUT:638930029917015865分析因?yàn)橹挥幸惶讓?dǎo)彈攔截系統(tǒng)，并且這套系統(tǒng)除了第一發(fā)炮彈能到達(dá)任意高度外，以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度；所以，被攔截的導(dǎo)彈應(yīng)該按飛來的導(dǎo)彈高度組成一個(gè)非遞增序列。題目要求我們計(jì)算這套系統(tǒng)最多能攔截的導(dǎo)彈數(shù)，并依次輸出被攔截導(dǎo)彈的高度，實(shí)際上就是要在導(dǎo)彈依次飛來的高度序列中尋找一個(gè)最長非遞增子序列的長度。狀態(tài)轉(zhuǎn)移方程如果我們已經(jīng)求出了d(1)到d(i-1)，那么d(i)可以用下面的狀態(tài)轉(zhuǎn)移方程得到：d(i)=max{d(j)}+1（1）其中j=1,2,...,i-1,A[j]≥A[i]有可能i前面的各個(gè)子序列中最后一個(gè)數(shù)都小于A[i]，那么d(i)=1（2）即它自身成為一個(gè)長度為1的子序列。只需修改這個(gè)符號(hào)，就可以求最長非遞增子序列求解攔截導(dǎo)彈問題的C++代碼段intlen=1;for(inti=0;i<n;++i){d[i]=1;//數(shù)組d用來保存子序列的長度

for(intj=0;j<i;++j)if(A[j]>=A[i]&&d[j]+1>d[i])d[i]=d[j]+1;if(d[i]>len)len=d[i];}例2乘積最大問題描述設(shè)有一個(gè)長度N的數(shù)字串，要求選手使用K個(gè)乘號(hào)將它分成K+1個(gè)部分，找出一種分法，使得這K+1個(gè)部分的乘積能夠?yàn)樽畲?。例子：有一個(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)你設(shè)計(jì)一個(gè)程序，求得正確的答案。（藍(lán)橋網(wǎng)站題目編號(hào)：ALGO-17VIP試題2013-11-07

）輸入輸出樣例輸入：輸入中有若干組測試數(shù)據(jù)，每組測試數(shù)據(jù)有兩行：第一行共有2個(gè)自然數(shù)T，K（6<=T<=40，1<=K<=6），第二行是一個(gè)長度為T的數(shù)字串。輸出:

結(jié)果顯示在屏幕上，相對(duì)于輸入，應(yīng)輸出所求得的最大乘積（一個(gè)自然數(shù)）。輸入樣例:421231輸出樣例：62分析：劃分階段假設(shè)在n0n1…ni(2≤i≤n)中插入k個(gè)’*’。其中n0n1…nt中插入了k-1個(gè)’*’，即乘式中的第k+1項(xiàng)為nt+1…ni(k≤t≤i-1)，即有形式：

狀態(tài)轉(zhuǎn)移方程設(shè)F[i][k]是長度為i+1的數(shù)串中插入k個(gè)“*”的最大乘積（整型數(shù)組），0≤k≤i。顯然F[i][0]=，i=0，1，2，…，N-1；狀態(tài)轉(zhuǎn)移方程為高精度運(yùn)算由于自然數(shù)位數(shù)的上限為40，乘號(hào)數(shù)的上限為6，因此最大乘積位數(shù)的上限接近42位。顯然，運(yùn)算任何整數(shù)類型都無法容納如此之大的數(shù)據(jù)，需要采用高精度運(yùn)算，這里僅介紹解題思路。為了便于大家理解算法思想，程序中只是用了在長整型范圍內(nèi)的數(shù)據(jù)處理，如整數(shù)的分劃、合成和乘法運(yùn)算等。

01背包問題一個(gè)旅行者有一個(gè)最多能用M公斤的背包，現(xiàn)在有N件物品，

它們的重量分別是W1，W2，...,Wn,

它們的價(jià)值分別為P1,P2,...,Pn.

若每種物品只有一件，求旅行者能獲得最大總價(jià)值。輸入輸出輸入格式：

M,N

W1,P1

W2,P2

......

輸出格式：

X分析階段：在前i件物品中，選取若干件物品放入背包中；狀態(tài)：在前i件物品中，選取若干件物品放入所?？臻g為c的背包中的所能獲得的最大價(jià)值；決策：第i件物品放或者不放；狀態(tài)轉(zhuǎn)移方程可以按每個(gè)物品劃分階段；每種物品有選和不選兩種選擇（決策）設(shè)F(i,j)表示前i件物品載重為j的最大效益，則有1<=i<=N,0<=j<=M初值：F(0,j)=0F(N,M)即答案顯然時(shí)間復(fù)雜度為O(NM)f(i,j)=max{f(i-1,j),f(i-1,j-w[i])+P(i)}c[i][j]數(shù)組保存了1,2,3號(hào)物品依次選擇后的最大價(jià)值f(i,j)測試數(shù)據(jù)：

10,3（容量為10，3個(gè)物品）3,4

4,5

5,6f(2,7)=max{f(1,7),f(1,7-4)+5)}=max{5,4+5}=9裝入2號(hào)物品f(3,7)=max{f(2,7),f(2,7-5)+6)}=max{9,0+6}=9不裝入3號(hào)物品主程序fori:=1tomdof[0,i]:=0;//初始化fori:=1tondof[i,0]:=0;fori:=1tondo//動(dòng)態(tài)規(guī)劃，遞推求f forj:=1tomdo begin ifj>=w[i]then//背包容量夠大

f[i,j]:=max(f[i-1,j-w[i]]+p[i],f[i-1,j]) else//背包容量不足

f[i,j]:=f[i-1,j]; end;例3入學(xué)考試辰辰是個(gè)天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大?！?/p>

如果你是辰辰，你能完成這個(gè)任務(wù)嗎？

藍(lán)橋網(wǎng)編號(hào)：ALGO-30VIP試題2013-11-08輸入輸出格式輸入格式第一行有兩個(gè)整數(shù)T（1<=T<=1000）和M（1<=M<=100），用一個(gè)空格隔開，T代表總共能夠用來采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。輸出格式包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。輸入輸出樣例樣例輸入703

71100

691

12樣例輸出3數(shù)據(jù)規(guī)模和約定對(duì)于30%的數(shù)據(jù)，M<=10；

對(duì)于全部的數(shù)據(jù)，M<=100。分析這是一個(gè)典型的01背包問題可以將T（總共能夠用來采藥的時(shí)間）看作背包容量將采每一株草藥需要時(shí)間的時(shí)間看作物品重量將每株草藥的價(jià)值看作物品的價(jià)值例4開心的金明金明今天很開心，家里購置的新房就要領(lǐng)鑰匙了，新房里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對(duì)他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預(yù)算，但是他想買的東西太多了，肯定會(huì)超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個(gè)重要度，分為5等：用整數(shù)1~5表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價(jià)格（都是整數(shù)元）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。設(shè)第j件物品的價(jià)格為v[j]，重要度為w[j]，共選中了k件物品，編號(hào)依次為j1...jk，則所求的總和為：v[j1]*w[j1]+..+v[jk]*w[jk]請(qǐng)你幫助金明設(shè)計(jì)一個(gè)滿足要求的購物單。藍(lán)橋網(wǎng)題目編號(hào)：ALGO-31VIP試題2013-11-08輸入輸出【輸入文件】輸入的第1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開：Nm（其中N（<30000）表示總錢數(shù)，m(<25)為希望購買物品的個(gè)數(shù)。）從第2行到第m+1行，第j行給出了編號(hào)為j-1的物品的基本數(shù)據(jù)，每行有2個(gè)非負(fù)整數(shù)vp（其中v表示該物品的價(jià)格（v≤10000），p表示該物品的重要度（1~5））【輸出文件】輸出只有一個(gè)正整數(shù)，為不超過總錢數(shù)的物品的價(jià)格與重要度乘積的總和的最大值（<100000000）。輸入輸出樣例【輸入樣例】1000580024005300540032002【輸出樣例】3900分析這是一個(gè)有微小變化的01背包問題總錢數(shù)N可看做背包的容量，物品的價(jià)格可看作物品的重量。優(yōu)化目標(biāo)：在不超過N元（可以等于N元）的前提下，使每件物品的價(jià)格與重要度的乘積的總和最大。狀態(tài)轉(zhuǎn)移方程如下：f[i,j]=max{f[i-1,j-vi]+vi*pi(j>=wi),f[i-1,j]}主要程序段for(i=0;i<n;i++) f[0][i]=0;//初始化最大價(jià)值數(shù)組的第0行；for(i=1;i<m;i++)

for(j=0;j<n;j++) { f[i][j]=f[i-1][j]; if((j>=v[i])&&(f[i-1][j-v[i]]+v[i]*p[i]>f[i][j]))

f[i][j]=f[i-1][j-v[i]]+v[i]*p[i];

}/*如果當(dāng)前物品的價(jià)格小于總價(jià)格(j>=v[i])*/例5裝箱問題有一個(gè)箱子容量為V（正整數(shù)，0＜＝V＜＝20000），同時(shí)有n個(gè)物品（0＜n＜＝30），每個(gè)物品有一個(gè)體積（正整數(shù)）。要求n個(gè)物品中，任取若干個(gè)裝入箱內(nèi)，使箱子的剩余空間為最小。輸入格式第一行為一個(gè)整數(shù)，表示箱子容量；第二行為一個(gè)整數(shù)，表示有n個(gè)物品；接下來n行，每行一個(gè)整數(shù)表示這n個(gè)物品的各自體積。輸出格式一個(gè)整數(shù)，表示箱子剩余空間。藍(lán)橋網(wǎng)編號(hào)：ALGO-21VIP試題 2013-11-07輸入輸出樣例樣例輸入2468312797樣例輸出0分析這是一個(gè)變形的背包問題，最優(yōu)目標(biāo)是：使箱子的剩余空間為最小?？赊D(zhuǎn)換成物品占據(jù)的容量最大。用F[i,j]表示容量為j的箱子裝入前i個(gè)物品后，物品占據(jù)的容量。則狀態(tài)轉(zhuǎn)移方程為：F[i,j]=max{F[i-1,j-a[i]]+a[i]，F(xiàn)[i-1,j]}其中a[i]表示第i個(gè)物品的體積。主要代碼段dp[0]=0;//注意這是關(guān)鍵

for(i=0;i<n;i++) {inta;scanf("%d",&a); for(j=v;j>=a;j--)

dp[j]=max(dp[j],dp[j-a]+a);}收集蘋果：二維的DP問題平面上有N＊M個(gè)格子，每個(gè)格子中放著一定數(shù)量的蘋果。你從左上角的格子開始，每一步只能向下走或是向右走，每次走到一個(gè)格子上就把格子里的蘋果收集起來，這樣下去，你最多能收集到多少個(gè)蘋果。我們必須注意到的一點(diǎn)是，到達(dá)一個(gè)格子的方式最多只有兩種：從左邊來的(除了第一列)和從上邊來的(除了第一行)。分析因此為了求出到達(dá)當(dāng)前格子后最多能收集到多少個(gè)蘋果，我們就要先去考察那些能到達(dá)當(dāng)前這個(gè)格子(i,j)之前的格子，到達(dá)它們最多能收集到多少個(gè)蘋果。(i-1,j)(i,j-1)(i,j)A[i,j]狀態(tài)和狀態(tài)轉(zhuǎn)移方程狀態(tài)S[i][j]表示我們走到(i,j)這個(gè)格子時(shí)，最多能收集到多少個(gè)蘋果。那么，狀態(tài)轉(zhuǎn)移方程如下：S[i][j]=A[i][j]+max(S[i-1][j],ifi>0;S[i][j-1],ifj>0)其中i代表行，j代表列，下標(biāo)均從0開始；A[i][j]代表格子(i,j)處的蘋果數(shù)量。例6傳紙條

小淵和小軒是好朋友也是同班同學(xué)，他們?cè)谝黄鹂傆姓劜煌甑脑掝}。一次素質(zhì)拓展活動(dòng)中，班上同學(xué)安排做成一個(gè)m行n列的矩陣，而小淵和小軒被安排在矩陣對(duì)角線的兩端，因此，他們就無法直接交談了。幸運(yùn)的是，他們可以通過傳紙條來進(jìn)行交流。紙條要經(jīng)由許多同學(xué)傳到對(duì)方手里，小淵坐在矩陣的左上角，坐標(biāo)(1,1)，小軒坐在矩陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。在活動(dòng)進(jìn)行中，小淵希望給小軒傳遞一張紙條，同時(shí)希望小軒給他回復(fù)。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時(shí)候幫忙，那么在小軒遞給小淵的時(shí)候就不會(huì)再幫忙。反之亦然。還有一件事情需要注意，全班每個(gè)同學(xué)愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時(shí)用0表示），可以用一個(gè)0-100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學(xué)來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度之和最大。現(xiàn)在，請(qǐng)你幫助小淵和小軒找到這樣的兩條路徑。藍(lán)橋網(wǎng)題目編號(hào)：ALGO-36 VIP試題 2013-11-08輸入輸出格式輸入格式輸入第一行有2個(gè)用空格隔開的整數(shù)m和n，表示班里有m行n列（1<=m,n<=50）。

接下來的m行是一個(gè)m*n的矩陣，矩陣中第i行j列的整數(shù)表示坐在第i行j列的學(xué)生的好心程度。每行的n個(gè)整數(shù)之間用空格隔開。輸出格式輸出一行，包含一個(gè)整數(shù)，表示來回兩條路上參與傳遞紙條的學(xué)生的好心程度之和的最大值。樣例輸入輸出樣例輸入33039285570樣例輸出34數(shù)據(jù)規(guī)模和約定

30%的數(shù)據(jù)滿足：1<=m,n<=10

100%的數(shù)據(jù)滿足：1<=m,n<=50傳紙條(甩干后)小淵坐在矩陣的左上角，坐標(biāo)(1,1)，小軒坐在矩陣的右下角，坐標(biāo)(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。班里每個(gè)同學(xué)都可以幫他們傳遞，但只會(huì)幫他們一次。每個(gè)同學(xué)愿意幫忙的好感度有高有低，可以用一個(gè)0-100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學(xué)來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學(xué)的好心程度