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

1、動態(tài)規(guī)劃方法例題最長上升子序列問題 一個序列有N個數(shù)：A1,A2,AN，求出最長上升子序列的長度（LIS：longest increasing subsequence)。 例如，對于序列(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). 分析 假如我們考慮求A1,A2,Ai的最長上升子序列的長度，其中iN，那么上面的問題變成了原問題的一個子問題(問題規(guī)模變小了，可讓i=1,2,3等來分析) 然后我

2、們定義d(i)，表示前i個數(shù)中以Ai結(jié)尾的最長上升子序列的長度。這個d(i)就是我們要找的狀態(tài)。 如果我們把d(1)到d(N)都計算出來，那么最終我們要找的答案就是這里面最大的那個。狀態(tài)找到了，下一步來找狀態(tài)轉(zhuǎn)移方程。 找出狀態(tài)轉(zhuǎn)移方程我們來看下面這6個數(shù)的序列：5，3，4，8，6，7我們可以得到：（下文的最長上升子序列都用LIS表示）前1個數(shù)的LIS長度d(1)=1(序列：5) 前2個數(shù)的LIS長度d(2)=1(序列：3；3前面沒有比3小的) 前3個數(shù)的LIS長度d(3)=2(序列：3，4；4前面有個比它小的3) 第1階段決策選優(yōu)：求最長最長上升子序列的長度 需要判斷當前的數(shù)是否與其左邊最長

3、左邊最長上升子序列構(gòu)成一個上升序列，如果是，則： d(3)= maxd(1),d(2)+1； 即第3個數(shù)左邊最長上升子序列最大長度+1 前4個數(shù)的LIS長度d(4)=3 (序列：3，4，8；8前面比它小的有3個數(shù)，所以 d(4)=maxd(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) = maxd(j)+1 （1）其中j=1,2, . ,i-1, AjAi有可能i前面的各個子序列中最后一個數(shù)都大于Ai，那么d(i)=1 （2）即它自身成為一個長度為1的子序列。求解LIS的C+代碼段int len = 1

4、; for(int i=0; in; +i) di = 1;/數(shù)組d用來保存子序列的長度 for(int j=0; ji; +j) if(Ajdi) di = dj + 1; if(dilen) len = di; 序列變化 求最長非降子序列(longest non-decreasing subsequence)，與此問題近似。只需要將上述條件AjAi改為：AjAi。 求最長下降子序列(longest decreasing subsequence)，將上述條件AjAi。 如果要求最長非遞增子序列（longest non-increasing subsequence），將上述條件AjAi改為：A

5、jAi。 藍橋杯網(wǎng)站練習系統(tǒng)算法訓練中的“攔截導彈攔截導彈”問題，本質(zhì)上就是一個求最長非遞增子序列長度的題。 例1 攔截導彈 某國為了防御敵國的導彈襲擊，開發(fā)出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。 （藍橋網(wǎng)編號：ALGO-13 VIP試題 ）攔截導彈輸入導彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導彈，并依次輸出被攔截的導彈飛來時候的高度。輸入第一行

6、輸入測試數(shù)據(jù)組數(shù)N（1=N=10）接下來一行輸入這組測試數(shù)據(jù)共有多少個導彈m（1=m=20）接下來行輸入導彈依次飛來的高度，所有高度值均是大于10的正整數(shù)。輸出輸出最多能攔截的導彈數(shù)目 攔截導彈 樣例輸入輸出 樣例輸入 SAMPLE INPUT:28389 207 155 300 299 170 158 65388 34 65SAMPLE OUTPUT:6389 300 299 170 158 65 分析 因為只有一套導彈攔截系統(tǒng)，并且這套系統(tǒng)除了第一發(fā)炮彈能到達任意高度外，以后的每一發(fā)炮彈都不能高于前一發(fā)炮彈的高度；所以，被攔截的導彈應該按飛來的導彈高度組成一個非遞增序列。 題目要求我們計算

7、這套系統(tǒng)最多能攔截的導彈數(shù)，并依次輸出被攔截導彈的高度，實際上就是要在導彈依次飛來的高度序列中尋找一個最長非遞增子序列的長度一個最長非遞增子序列的長度。狀態(tài)轉(zhuǎn)移方程如果我們已經(jīng)求出了d(1)到d(i-1)，那么d(i)可以用下面的狀態(tài)轉(zhuǎn)移方程得到：d(i) = maxd(j)+1 （1）其中j=1,2, . ,i-1, Aj Ai有可能i前面的各個子序列中最后一個數(shù)都小于Ai，那么d(i)=1 （2）即它自身成為一個長度為1的子序列。只需修改這個符號，就可以求最長非遞增子序列求解攔截導彈問題的C+代碼段int len = 1; for(int i=0; in; +i) di = 1;/數(shù)組d用

8、來保存子序列的長度 for(int j=0; j=Ai & dj+1di) di = dj + 1; if(dilen) len = di; 例例2 乘積最大乘積最大 問題描述 設有一個長度N的數(shù)字串，要求選手使用K個乘號將它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。 例子：有一個數(shù)字串: 312，當N=3，K=1時會有以下兩種分法： 1）3*12=36 2）31*2=62 這時，符合題目要求的結(jié)果是： 31*2=62 現(xiàn)在，請你設計一個程序，求得正確的答案。（藍橋網(wǎng)站題目編號：ALGO-17 VIP試題2013-11-07 ）輸入輸出樣例輸入： 輸入中有若干

9、組測試數(shù)據(jù)，每組測試數(shù)據(jù)有兩行：第一行共有2個自然數(shù)T，K （6=T=40，1=K=6），第二行是一個長度為T的數(shù)字串。輸出: 結(jié)果顯示在屏幕上，相對于輸入，應輸出所求得的最大乘積（一個自然數(shù)）。輸入樣例: 4 21231 輸出樣例：62分析：劃分階段假設在n0n1ni(2in)中插入k個*。其中n0n1nt中插入了k-1個*，即乘式中的第k+1項為nt+1ni(kti-1) ，即有形式： itktnnnn1*10* 個插入狀態(tài)轉(zhuǎn)移方程設Fik是長度為i+1的數(shù)串 中插入k個“*”的最大乘積（整型數(shù)組），0ki。ittnnnn10.1* 1max10itnumktFkiFtkittnnnn10

10、.顯然顯然Fi0= ，i=0，1，2，N-1；狀態(tài)轉(zhuǎn)移方程為狀態(tài)轉(zhuǎn)移方程為 高精度運算由于自然數(shù)位數(shù)的上限為40，乘號數(shù)的上限為6，因此最大乘積位數(shù)的上限接近42位。顯然，運算任何整數(shù)類型都無法容納如此之大的數(shù)據(jù)，需要采用高精度運算，這里僅介紹解題思路。 為了便于大家理解算法思想，程序中只是用了在長整型范圍內(nèi)的數(shù)據(jù)處理，如整數(shù)的分劃、合成和乘法運算等。 01背包問題 一個旅行者有一個最多能用M公斤的背包，現(xiàn)在有N件物品，它們的重量分別是W1，W2，.,Wn,它們的價值分別為P1,P2,.,Pn.若每種物品只有一件只有一件，求旅行者能獲得最大總價值。 輸入輸出 輸入格式：M,NW1,P1W2,P

11、2.輸出格式： X 分析 階段：在前i件物品中，選取若干件物品放入背包中； 狀態(tài)：在前i件物品中，選取若干件物品放入所?？臻g為c的背包中的所能獲得的最大價值； 決策：第i件物品放或者不放； 狀態(tài)轉(zhuǎn)移方程 可以按每個物品劃分階段； 每種物品有選和不選兩種選擇（決策） 設F(i,j)表示前i件物品載重為j的最大效益，則有 1=i=N, 0=j=wi then /背包容量夠大 fi,j:=max(fi-1,j-wi+pi,fi-1,j)else /背包容量不足 fi,j:=fi-1,j;end;例3 入學考試 辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為

12、師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自采每一株都需要一些時間，每一株也有它自身的價值身的價值。我會給你一段時間會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大讓采到的草藥的總價值最大。”如果你是辰辰，你能完成這個任務嗎？ 藍橋網(wǎng)編號：ALGO-30 VIP試題 2013-11-08輸入輸出格式輸入格式第一行有兩個整數(shù)T（1 = T = 1000）和M（1 = M = 100），用一個空格隔開，T代表總共能夠用來采

13、藥的時間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值。輸出格式包括一行，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。 輸入輸出樣例樣例輸入70 371 10069 11 2樣例輸出3數(shù)據(jù)規(guī)模和約定對于30%的數(shù)據(jù)，M = 10；對于全部的數(shù)據(jù)，M = 100。 分析 這是一個典型的01背包問題 可以將T（總共能夠用來采藥的時間）看作背包容量 將采每一株草藥需要時間的時間看作物品重量 將每株草藥的價值看作物品的價值例4 開心的金明 金明今天很開心，家里購置的新房就要領鑰匙了，新房

14、里有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：“你的房間需要購買哪些物品，怎么布置，你說了算，只要不超過N元錢就行”。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的N元。于是，他把每件物品規(guī)定了一個重要度，分為5等：用整數(shù)15表示，第5等最重要。他還從因特網(wǎng)上查到了每件物品的價格（都是整數(shù)元）。他希望在不超過N元（可以等于N元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第j件物品的價格為vj，重要度為wj，共選中了k件物品，編號依次為j1.jk，則所求的總和為：vj1*wj1+.+vjk*wjk請你幫助金明設計一個滿足要求的購物單。 藍橋

15、網(wǎng)題目編號：ALGO-31 VIP試題 2013-11-08 輸入輸出【輸入文件】輸入的第1行，為兩個正整數(shù)，用一個空格隔開：N m（其中N（30000）表示總錢數(shù)，m(25)為希望購買物品的個數(shù)。）從第2行到第m+1行，第j行給出了編號為j-1的物品的基本數(shù)據(jù)，每行有2個非負整數(shù)v p（其中v表示該物品的價格（v10000），p表示該物品的重要度（15）【輸出文件】輸出只有一個正整數(shù)，為不超過總錢數(shù)的物品的價格與重要度乘積的總和的最大值（=wi),fi-1,j 主要程序段for(i=0;in;i+)f0i=0;/初始化最大價值數(shù)組的第0行；for(i=1;im;i+)for(j=0;j=vi

16、)&(fi-1j-vi+vi*pifij) fij=fi-1j-vi+vi*pi;/*如果當前物品的價格小于總價格(j=vi)*/ 例5 裝箱問題有一個箱子容量為V（正整數(shù)，0V20000），同時有n個物品（0n30），每個物品有一個體積（正整數(shù)）。要求n個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小。輸入格式第一行為一個整數(shù)，表示箱子容量；第二行為一個整數(shù)，表示有n個物品；接下來n行，每行一個整數(shù)表示這n個物品的各自體積。輸出格式一個整數(shù)，表示箱子剩余空間。藍橋網(wǎng)編號：ALGO-21 VIP試題 2013-11-07 輸入輸出樣例樣例輸入2468312797樣例輸出0分析這是一

17、個變形的背包問題，最優(yōu)目標是：使箱子的剩余空間為最小?？赊D(zhuǎn)換成物品占據(jù)的容量最大。 用Fi,j表示容量為j的箱子裝入前i個物品后，物品占據(jù)的容量。則狀態(tài)轉(zhuǎn)移方程為：Fi,j= maxFi-1,j-ai+ai，F(xiàn)i-1,j其中ai表示第i個物品的體積。 主要代碼段dp0=0;/注意這是關鍵 for(i=0;i=a;j-) dpj=max(dpj,dpj-a+a); 收集蘋果：二維的DP問題 平面上有NM個格子，每個格子中放著一定數(shù)量的蘋果。你從左上角的格子開始，每一步只能向下走或是向右走，每次走到一個格子上就把格子里的蘋果收集起來，這樣下去，你最多能收集到多少個蘋果。 我們必須注意到的一點是，到

18、達一個格子的方式最多只有兩種：從左邊來的(除了第一列)和從上邊來的(除了第一行)。分析 因此為了求出到達當前格子后最多能收集到多少個蘋果，我們就要先去考察那些能到達當前這個格子(i,j)之前的格子，到達它們最多能收集到多少個蘋果。(i-1,j)(i,j-1)(i,j)Ai,j狀態(tài)和狀態(tài)轉(zhuǎn)移方程狀態(tài)Sij表示我們走到(i, j)這個格子時，最多能收集到多少個蘋果。那么，狀態(tài)轉(zhuǎn)移方程如下：Sij=Aij + max(Si-1j, if i0 ; Sij-1, if j0)其中i代表行，j代表列，下標均從0開始；Aij代表格子(i, j)處的蘋果數(shù)量。例6 傳紙條 小淵和小軒是好朋友也是同班同學，他

19、們在一起總有談不完的話題。一次素質(zhì)拓展活動中，班上同學安排做成一個m行n列的矩陣，而小淵和小軒被安排在矩陣對角線的兩端，因此，他們就無法直接交談了。幸運的是，他們可以通過傳紙條來進行交流。紙條要經(jīng)由許多同學傳到對方手里，小淵坐在矩陣的左上角，坐標(1,1)，小軒坐在矩陣的右下角，坐標(m,n)。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。在活動進行中，小淵希望給小軒傳遞一張紙條，同時希望小軒給他回復。班里每個同學都可以幫他們傳遞，但只會幫他們一次，也就是說如果此人在小淵遞給小軒紙條的時候幫忙，那么在小軒遞給小淵的時候就不會再幫忙。反之亦然。還有一件事

20、情需要注意，全班每個同學愿意幫忙的好感度有高有低（注意：小淵和小軒的好心程度沒有定義，輸入時用0表示），可以用一個0-100的自然數(shù)來表示，數(shù)越大表示越好心。小淵和小軒希望盡可能找好心程度高的同學來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學的好心程度之和最大?，F(xiàn)在，請你幫助小淵和小軒找到這樣的兩條路徑。藍橋網(wǎng)題目編號：ALGO-36VIP試題2013-11-08輸入輸出格式輸入格式輸入第一行有2個用空格隔開的整數(shù)m和n，表示班里有m行n列（1=m,n=50）。接下來的m行是一個m*n的矩陣，矩陣中第i行j列的整數(shù)表示坐在第i行j列的學生的好心程度。每行的n個整數(shù)之間用空格隔開。輸

21、出格式輸出一行，包含一個整數(shù)，表示來回兩條路上參與傳遞紙條的學生的好心程度之和的最大值。樣例輸入輸出樣例輸入3 30 3 92 8 55 7 0樣例輸出34數(shù)據(jù)規(guī)模和約定30%的數(shù)據(jù)滿足：1=m,n=10100%的數(shù)據(jù)滿足：1=m,n=50 傳紙條傳紙條(甩干后甩干后) 小淵坐在矩陣的左上角，坐標小淵坐在矩陣的左上角，坐標(1,1)，小軒坐在矩，小軒坐在矩陣的右下角，坐標陣的右下角，坐標(m,n)。從小淵傳到小軒的紙條。從小淵傳到小軒的紙條只可以向下或者向右傳遞，從小軒傳給小淵的紙只可以向下或者向右傳遞，從小軒傳給小淵的紙條只可以向上或者向左傳遞。條只可以向上或者向左傳遞。 班里每個同學都可以

22、幫他們傳遞，但只會幫他們班里每個同學都可以幫他們傳遞，但只會幫他們一次。一次。 每個同學愿意幫忙的好感度有高有低，可以用一每個同學愿意幫忙的好感度有高有低，可以用一個個0-100的自然數(shù)來表示，數(shù)越大表示越好心。的自然數(shù)來表示，數(shù)越大表示越好心。 小淵和小軒希望盡可能找好心程度高的同學來幫小淵和小軒希望盡可能找好心程度高的同學來幫忙傳紙條，即找到來回兩條傳遞路徑，使得這兩忙傳紙條，即找到來回兩條傳遞路徑，使得這兩條路徑上同學的好心程度條路徑上同學的好心程度之之和最大?，F(xiàn)在，請你和最大?，F(xiàn)在，請你幫助小淵和小軒找到這樣的兩條路徑。幫助小淵和小軒找到這樣的兩條路徑。 1=m,n=50貪心 很容易想到一個算法：很容易想到一個算法： 求出求出1個紙條從（個紙條從（1，1）到（）到（M,N）的路線最大值）的路線最大值. 刪除路徑上的點值刪除路徑上的點值 再求出再求出1個紙條從（個紙條從（M,N） 到（到（1，1）的路線最大值）的路線最大值. 統(tǒng)計兩次和統(tǒng)計兩次和 上述算法很容易找出反例，如下圖。上述算法很容易找出反例，如下圖。 第第1次找最優(yōu)值傳遞后，導致第次找最優(yōu)值傳遞后，導致第2次無法傳遞。次無法傳遞。分析 貪心算法錯誤，因此我們需要同時考慮兩個紙條的傳遞。貪心算法錯誤，因此我們需要同時考慮兩個紙條的傳遞。 由于由于小淵小淵和小軒的路徑可逆，因此，盡管出發(fā)點不同，但和小