第節(jié)動態(tài)規(guī)劃基礎(chǔ)(C版)

第九章動態(tài)規(guī)劃第一節(jié)動態(tài)規(guī)劃的基本模型第二節(jié)動態(tài)規(guī)劃與遞推第三節(jié)背包問題第四節(jié)動態(tài)題動態(tài)規(guī)劃程序設(shè)計是對解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不像前面所述的那些搜索或數(shù)值計算那樣，具有一個標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動態(tài)規(guī)劃程序設(shè)計往往是針對一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動態(tài)規(guī)劃的設(shè)計方法對不同的問題，有各具特色的解題方法，而不存在一種萬能的動態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時，除了要對基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對若干有代表性的問題的動態(tài)規(guī)劃算法進行分析、討論，逐漸學(xué)會并掌握這一設(shè)計方法。第一節(jié)動態(tài)規(guī)劃的基本模型多階段決策過程的最優(yōu)化問題

在現(xiàn)實生活中，有一類活動的過程，由于它的特殊性，可將過程分成若干個互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個過程達(dá)到最好的活動效果。當(dāng)然，各個階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，又影響以后的發(fā)展，當(dāng)各個階段決策確定后，就組成一個決策序列，因而也就確定了整個過程的一條活動路線，這種把一個問題看作是一個前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。如下圖所示：多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯(lián)系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列?！纠?】最短路徑問題。下圖給出了一個地圖，地圖中的每個頂點代表一個城市，兩個城市間的一條連線代表道路，連線上的數(shù)值代表道路的長度?，F(xiàn)在想從城市A到達(dá)城市E，怎樣走路程最短？最短路程的長度是多少？【算法分析】把A到E的全過程分成四個階段，用K表示階段變量，第1階段有一個初始狀態(tài)A，有兩條可供選擇的支路A-B1、A-B2；第2階段有兩個初始狀態(tài)B1、B2，B1有三條可供選擇的支路，B2有兩條可供選擇的支路……。用DK（XI，X+1J）表示在第K階段由初始狀態(tài)XI到下階段的初始狀態(tài)X+1J的路徑距離，F(xiàn)K（XI）表示從第K階段的XI到終點E的最短距離，利用倒推的方法，求解A到E的最短距離。具體計算過程如下：S1：K=4有F4（D1）=3，F(xiàn)4（D2）=4，F(xiàn)4（D3）=3；S2：K=3有F3（C1）=MIN{D3（C1，D1）+F4（D1），D3（C1，D2）+F4（D2）}=MIN{5+3，6+4}=8F3（C2）=D3（C2，D1）+F4（D1）=5+3=8F3（C3）=D3（C3，D3）+F4（D3）=8+3=11F3（C4）=D3（C4，D3）+F4（D3）=3+3=6S3：K=2有F2（B1）=MIN{D2（B1，C1）+F3（C1），D2（B1，C2）+F3（C2），D2（B1，C3）+F3(C3)}=MIN{1+8,6+8,3+11}=9F2（B2）=MIN{D2（B2，C2）+F3（C2），D2（B2，C4）+F3（C4）}=MIN{8+8，4+6}=10S4：K=1有F1（A）=MIN{D1（A，B1）+F2（B1），D1（A，B2）+F2（B2）}=MIN{5+9，3+10}=13因此由A點到E點的全過程最短路徑為A→B2→C4→D3→E；最短路程長度為13。從以上過程可以看出，每個階段中，都求出本階段的各個初始狀態(tài)到終點E的最短距離，當(dāng)逆序倒推到過程起點A時，便得到了全過程的最短路徑和最短距離。在上例的多階段決策問題中，各個階段采取的決策，一般來說是與階段有關(guān)的，決策依賴于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移，一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義，我們稱這種解決多階段決策最優(yōu)化的過程為動態(tài)規(guī)劃程序設(shè)計方法。動態(tài)規(guī)劃的基本概念和基本模型構(gòu)成現(xiàn)在我們來介紹動態(tài)規(guī)劃的基本概念。1.階段和階段變量：用動態(tài)規(guī)劃求解一個問題時，需要將問題的全過程恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段，以便按一定的次序去求解。描述階段的變量稱為階段變量，通常用K表示，階段的劃分一般是根據(jù)時間和空間的自然特征來劃分，同時階段的劃分要便于把問題轉(zhuǎn)化成多階段決策過程，如例題1中，可將其劃分成4個階段，即K=1，2，3，4。2.狀態(tài)和狀態(tài)變量：某一階段的出發(fā)位置稱為狀態(tài)，通常一個階段包含若干狀態(tài)。一般地，狀態(tài)可由變量來描述，用來描述狀態(tài)的變量稱為狀態(tài)變量。如例題1中，C3是一個狀態(tài)變量。3.決策、決策變量和決策允許集合：在對問題的處理中作出的每種選擇性的行動就是決策。即從該階段的每一個狀態(tài)出發(fā)，通過一次選擇性的行動轉(zhuǎn)移至下一階段的相應(yīng)狀態(tài)。一個實際問題可能要有多次決策和多個決策點，在每一個階段的每一個狀態(tài)中都需要有一次決策，決策也可以用變量來描述，稱這種變量為決策變量。在實際問題中，決策變量的取值往往限制在某一個范圍之內(nèi)，此范圍稱為允許決策集合。如例題1中，F(xiàn)3（C3）就是一個決策變量。4．策略和最優(yōu)策略：所有階段依次排列構(gòu)成問題的全過程。全過程中各階段決策變量所組成的有序總體稱為策略。在實際問題中，從決策允許集合中找出最優(yōu)效果的策略成為最優(yōu)策略。5.狀態(tài)轉(zhuǎn)移方程前一階段的終點就是后一階段的起點，對前一階段的狀態(tài)作出某種決策，產(chǎn)生后一階段的狀態(tài)，這種關(guān)系描述了由k階段到k+1階段狀態(tài)的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程。最優(yōu)化原理與無后效性上面已經(jīng)介紹了動態(tài)規(guī)劃模型的基本組成，現(xiàn)在需要解決的問題是：什么樣的“多階段決策問題”才可以采用動態(tài)規(guī)劃的方法求解。一般來說，能夠采用動態(tài)規(guī)劃方法求解的問題，必須滿足最優(yōu)化原理和無后效性原則：1、動態(tài)規(guī)劃的最優(yōu)化原理。作為整個過程的最優(yōu)策略具有：無論過去的狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略的性質(zhì)。也可以通俗地理解為子問題的局部最優(yōu)將導(dǎo)致整個問題的全局最優(yōu)，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，也就是說一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解，而非最優(yōu)解對問題的求解沒有影響。在例題1最短路徑問題中，A到E的最優(yōu)路徑上的任一點到終點E的路徑，也必然是該點到終點E的一條最優(yōu)路徑，即整體優(yōu)化可以分解為若干個局部優(yōu)化。2、動態(tài)規(guī)劃的無后效性原則。所謂無后效性原則，指的是這樣一種性質(zhì)：某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響。也就是說，“未來與過去無關(guān)”，當(dāng)前的狀態(tài)是此前歷史的一個完整的總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程未來的演變。在例題1最短路徑問題中，問題被劃分成各個階段之后，階段K中的狀態(tài)只能由階段K+1中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與其它狀態(tài)沒有關(guān)系，特別與未發(fā)生的狀態(tài)沒有關(guān)系，例如從Ci到E的最短路徑，只與Ci的位置有關(guān)，它是由Di中的狀態(tài)通過狀態(tài)轉(zhuǎn)移方程得來，與E狀態(tài)，特別是A到Ci的路徑選擇無關(guān)，這就是無后效性。由此可見，對于不能劃分階段的問題，不能運用動態(tài)規(guī)劃來解；對于能劃分階段，但不符合最優(yōu)化原理的，也不能用動態(tài)規(guī)劃來解；既能劃分階段，又符合最優(yōu)化原理的，但不具備無后效性原則，還是不能用動態(tài)規(guī)劃來解；誤用動態(tài)規(guī)劃程序設(shè)計方法求解會導(dǎo)致錯誤的結(jié)果。動態(tài)規(guī)劃設(shè)計方法的一般模式動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)；或倒過來，從結(jié)束狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到初始狀態(tài)。這些決策形成一個決策序列，同時確定了完成整個過程的一條活動路線，通常是求最優(yōu)活動路線。動態(tài)規(guī)劃的設(shè)計都有著一定的模式，一般要經(jīng)歷以下幾個步驟：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)移方程是一個遞推式，需要一個遞推的終止條件或邊界條件?！纠?】對應(yīng)的C++程序如下：#include<iostream>#include<cstring>usingnamespacestd;intmain(){longd[5][5][5],f[10][10];memset(d,42,sizeof(d));//有些路徑是不通的,賦值為較大值，用于判斷d[1][1][1]=5;d[1][1][2]=3;d[2][1][1]=1;//以下給可通路徑賦正常值d[2][1][2]=6;d[2][1][3]=3;d[2][2][2]=8d[2][2][4]=4;d[3][1][1]=5;d[3][1][2]=6;d[3][2][1]=5;d[3][3][3]=8;d[3][4][3]=3;d[4][1][1]=3;d[4][2][1]=4;d[4][3][1]=3;for(inti=0;i<=9;++i)for(intj=0;j<=9;++j)f[i][j]=10000000;f[5][1]=0;for(inti=4;i>=1;--i)for(intj=1;j<=4;++j)for(intk=1;k<=4;++k)if(f[i][j]>d[i][j][k]+f[i+1][k])//即使走非法路徑，也不影響答案f[i][j]=d[i][j][k]+f[i+1][k];cout<<f[1][1]<<endl;}第二節(jié)動態(tài)規(guī)劃與遞推

——動態(tài)規(guī)劃是最優(yōu)化算法

由于動態(tài)規(guī)劃的“名氣”如此之大，以至于很多人甚至一些資料書上都往往把一種與動態(tài)規(guī)劃十分相似的算法，當(dāng)作是動態(tài)規(guī)劃。這種算法就是遞推。實際上，這兩種算法還是很容易區(qū)分的。按解題的目標(biāo)來分，信息學(xué)試題主要分四類：判定性問題、構(gòu)造性問題、計數(shù)問題和最優(yōu)化問題。我們在競賽中碰到的大多是最優(yōu)化問題，而動態(tài)規(guī)劃正是解決最優(yōu)化問題的有力武器，因此動態(tài)規(guī)劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數(shù)問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態(tài)規(guī)劃在這兩個方面的聯(lián)系?！纠?】數(shù)塔問題（IOI1994）有形如圖所示的數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一起走到底層，要求找出一條路徑，使路徑上的值最大。這道題如果用枚舉法，在數(shù)塔層數(shù)稍大的情況下（如40），則需要列舉出的路徑條數(shù)將是一個非常龐大的數(shù)目。如果用貪心法又往往得不到最優(yōu)解。在用動態(tài)規(guī)劃考慮數(shù)塔問題時可以自頂向下的分析，自底向上的計算。從頂點出發(fā)時到底向左走還是向右走應(yīng)取決于是從左走能取到最大值還是從右走能取到最大值，只要左右兩道路徑上的最大值求出來了才能作出決策。同樣的道理下一層的走向又要取決于再下一層上的最大值是否已經(jīng)求出才能決策。這樣一層一層推下去，直到倒數(shù)第二層時就非常明了。所以實際求解時，可從底層開始，層層遞進，最后得到最大值。一般說來，很多最優(yōu)化問題都有著對應(yīng)的計數(shù)問題；反過來，很多計數(shù)問題也有著對應(yīng)的最優(yōu)化問題。因此，我們在遇到這兩類問題時，不妨多聯(lián)系、多發(fā)展，舉一反三，從比較中更深入地理解動態(tài)規(guī)劃的思想。其實遞推和動態(tài)規(guī)劃這兩種方法的思想本來就很相似，也不必說是誰借用了誰的思想。關(guān)鍵在于我們要掌握這種思想，這樣我們無論在用動態(tài)規(guī)劃法解最優(yōu)化問題，或是在用遞推法解判定型、計數(shù)問題時，都能得心應(yīng)手、游刃有余了?！窘夥ㄒ弧浚嫱品ǎ舅惴ǚ治觥竣儇澬姆ㄍ貌坏阶顑?yōu)解：本題若采用貪心法則：13-11-12-14-13，其和為63,但存在另一條路：13-8-26-15-24，其和為86。貪心法問題所在：眼光短淺。②動態(tài)規(guī)劃求解：動態(tài)規(guī)劃求解問題的過程歸納為：自頂向下的分析，自底向上計算。其基本方法是：劃分階段：按三角形的行，劃分階段，若有n行，則有n-1個階段。A．從根結(jié)點13出發(fā)，選取它的兩個方向中的一條支路，當(dāng)?shù)降箶?shù)第二層時，每個結(jié)點其后繼僅有兩個結(jié)點，可以直接比較，選擇最大值為前進方向，從而求得從根結(jié)點開始到底端的最大路徑。B．自底向上計算：（給出遞推式和終止條件）①從底層開始，本身數(shù)即為最大數(shù)；②倒數(shù)第二層的計算，取決于底層的數(shù)據(jù)：12+6=18，13+14=27，24+15=39，24+8=32；③倒數(shù)第三層的計算，取決于底二層計算的數(shù)據(jù)：27+12=39，39+7=46，39+26=65④倒數(shù)第四層的計算，取決于底三層計算的數(shù)據(jù)：46+11=57，65+8=73⑤最后的路徑：13——8——26——15——24C．?dāng)?shù)據(jù)結(jié)構(gòu)及算法設(shè)計①圖形轉(zhuǎn)化：直角三角形，便于搜索：向下、向右②用三維數(shù)組表示數(shù)塔：a[x][y][1]表示行、列及結(jié)點本身數(shù)據(jù),a[x][y][2]能夠取得最大值,a[x][y][3]表示前進的方向——0向下，1向右；③算法：數(shù)組初始化，輸入每個結(jié)點值及初始的最大路徑、前進方向為0；從倒數(shù)第二層開始向上一層求最大路徑，共循環(huán)N-1次；從頂向下，輸出路徑：究竟向下還是向右取決于列的值，若列的值比原先多1則向右，否則向下。

參考程序#include<iostream>#include<cstring>usingnamespacestd;intmain(){ intn,x,y; inta[51][51][3]; cout<<"pleaseinputthenumberofrows:"; cin>>n; memset(a,0,sizeof(0)); for(x=1;x<=n;x++)//輸入數(shù)塔的初始值 for(y=1;y<=x;y++) { cin>>a[x][y][1]; a[x][y][2]=a[x][y][1]; a[x][y][3]=0;//路徑走向，默認(rèn)向下 }for(x=n-1;x>=1;x--)for(y=1;y<=x;y++)if(a[x+1][y][2]>a[x+1][y+1][2])//選擇路徑，保留最大路徑值{a[x][y][2]=a[x][y][2]+a[x+1][y][2];a[x][y][3]=0;}else{a[x][y][2]=a[x][y][2]+a[x+1][y+1][2];a[x][y][3]=1;}cout<<"max="<<a[1][1][2]<<endl;//輸出數(shù)塔最大值y=1;for(x=1;x<=n-1;x++)//輸出數(shù)塔最大值的路徑{cout<<a[x][y][1]<<"->";y=y+a[x][y][3];//下一行的列數(shù)}cout<<a[n][y][1]<<endl;}輸入：5//數(shù)塔層數(shù)1311812726614158127132411輸出結(jié)果：max=8613->8->26->15->24【解法二】（順推法）【算法分析】此題貪心法往往得不到最優(yōu)解，例如13-11-12-14-13其路徑的值為63，但這不是最優(yōu)解。窮舉搜索往往是不可能的，當(dāng)層數(shù)N=100時，路徑條數(shù)P=299這是一個非常大的數(shù)，即使用世界上最快的電子計算機，也不能在規(guī)定時間內(nèi)計算出來。對這道題唯一正確的方法是動態(tài)規(guī)劃。如果得到一條由頂?shù)降椎哪程幍囊粭l最佳路徑，那么對于該路徑上的每一個中間點來說，由頂點至該中間點的路徑所經(jīng)過的數(shù)字和也為最大。因此本題是一個典型的多階段決策最優(yōu)化問題。在本題中僅要求輸出最優(yōu)解，為此我們設(shè)置了數(shù)組A[i,j]保存三角形數(shù)塔，B[i,j]保存狀態(tài)值，按從上往下方式進行求解。階段i：以層數(shù)來劃分階段，由從上往下方式計算；因此可通過第一重循環(huán): for(inti=1;i<=n;i++)枚舉每一階段；狀態(tài)B[i][j]：由于每個階段中有多個狀態(tài)，因此可通過第二重循環(huán): for(intj=1;j<=i;j++)求出每個階段的每個狀態(tài)的最優(yōu)解B[i][j]；決策：每個狀態(tài)最多由上一層的兩個結(jié)點連接過來，因此不需要做循環(huán)。

【參考程序】#include<iostream>#include<cstring>usingnamespacestd;intmain(){ intn,i,j,a[200][200],b[200][200],maxx;

cin>>n;memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i=1;i<=n;++i) for(j=1;j<=i;++jj) { cin>>a[i][j]; b[i][j]=a[i][j]; }

for(i=2;i<=n;++i)//選擇路徑，保留最大路徑值for(j=1;j<=i;++j)if(b[i-1][j-1]>b[i-1][j])b[i][j]=b[i][j]+b[i-1][j-1];elseb[i][j]=b[i][j]+b[i-1][j];maxx=0;for(j=1;j<=n;++j)if(b[n][j]>maxx)//在第n行中找出數(shù)塔最大值maxx=b[n][j];cout<<"Max="<<maxx<<endl;//輸出數(shù)塔最大值}【例3】求最長不下降序列㈠問題描述：設(shè)有由n個不相同的整數(shù)組成的數(shù)列，記為:b(1)、b(2)、……、b(n)且b(i)<>b(j)

(i<>j)，若存在i1<i2<i3<…<ie且有b(i1)<b(i2)<…<b(ie)則稱為長度為e的不下降序列。程序要求，當(dāng)原數(shù)列出之后，求出最長的不下降序列。例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一個長度為7的不下降序列，同時也有7，9，16，18，19，21，22，63長度為8的不下降序列。㈡算法分析：根據(jù)動態(tài)規(guī)劃的原理，由后往前進行搜索(當(dāng)然從前往后也一樣)。1·對b(n)來說，由于它是最后一個數(shù)，所以當(dāng)從b(n)開始查找時，只存在長度為1的不下降序列；2·若從b(n-1)開始查找，則存在下面的兩種可能性：①若b(n-1)<b(n)則存在長度為2的不下降序列b(n-1)，b(n)。②若b(n-1)>b(n)則存在長度為1的不下降序列b(n-1)或b(n)。3·一般若從b(i)開始，此時最長不下降序列應(yīng)該按下列方法求出:在b(i+1),b(i+2),…,b(n)中，找出一個比b(i)大的且最長的不下降序列，作為它的后繼。㈢數(shù)據(jù)結(jié)構(gòu)：為算法上的需要，定義一個整數(shù)類型二維數(shù)組b(N,3)1·b(I,1)表示第I個數(shù)的數(shù)值本身；2·b(I,2)表示從I位置到達(dá)N的最長不下降序列長度

3·b(I,3)表示從I位置開始最長不下降序列的下一個位置，若b[I,3]=0則表示后面沒有連接項。㈣求解過程：①從倒數(shù)第二項開始計算，后面僅有1項，比較一次，因63>15，不符合要求，長度仍為1。②從倒數(shù)第三項開始其后有2項，需做兩次比較，得到目前最長的不下降序列為2，如下表：11121314……11121314226315……21226315211……32111300……121300㈤一般處理過程是：①在i+1,i+2,…,n項中，找出比b[I,1]大的最長長度L以及位置K;②若L>0，則b[I,2]:=L+1;b[I,3]:=k;最后本題經(jīng)過計算，其數(shù)據(jù)存儲表如下：123456789101112131413791638243718441921226315787634352432114348979101311121300初始化:for(i=1;i<=n;i++){cin>>b[i][1];b[i][2]=1;b[i][3]=0;}下面給出求最長不下降序列的算法:for(i=n-1;i>=1;i--){l=0;k=0;for(j=i+1;j<=n;j++)if((b[j][1]>b[i][1])&&(b[j][2]>l)){l=b[j][2];k=j;}if(l>0){b[i][2]=l+1;b[i][3]=k;}}下面找出最長不下降序列：k=1;for(j=1;j<=n;j++)if(b[j][2]>b[k][2])k=j;最長不下降序列長度為b[k][2]序列while(k!=0){cout<<’’<<b[k][1];k=b[k][3];}#include<iostream>usingnamespacestd;intmain(){intn,i,j,l,k,b[200][10];cout<<"inputn:"<<endl;cin>>n;for(i=1;i<=n;i++)//輸入序列的初始值{cin>>b[i][1];b[i][2]=1;b[i][3]=0;}

程序運行結(jié)果：輸入：1413791638243718441921226315輸出：max=879161819212263

for(i=n-1;i>=1;i--)//求最長不下降序列{l=0;k=0;for(j=i+1;j<=n;j++)if((b[j][1]>b[i][1])&&(b[j][2]>l)){l=b[j][2];k=j;}if(l>0){b[i][2]=l+1;b[i][3]=k;}}k=1;for(j=1;j<=n;j++)//求最長不下降序列的起始位置if(b[j][2]>b[k][2])k=j;cout<<"max="<<b[k][2]<<endl;//輸出結(jié)果while(k!=0)//輸出最長不下降序列{cout<<''<<b[k][1];k=b[k][3];}}【例4】攔截導(dǎo)彈(Noip1999)某國為了防御敵國的導(dǎo)彈襲擊，發(fā)展出一種導(dǎo)彈攔截系統(tǒng)。但是這種導(dǎo)彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達(dá)任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達(dá)捕捉到敵國的導(dǎo)彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導(dǎo)彈。輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000的正整數(shù)，導(dǎo)彈數(shù)不超過1000），計算這套系統(tǒng)最多能攔截多少導(dǎo)彈，如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。樣例：INPUT OUTPUT389207155300299170158656（最多能攔截的導(dǎo)彈數(shù)）

2（要攔截所有導(dǎo)彈最少要配備的系統(tǒng)數(shù)）【算法分析】

第一問即經(jīng)典的最長不下降子序列問題，可以用一般的DP算法，也可以用高效算法，但這個題的數(shù)據(jù)規(guī)模不需要。用a[x]表示原序列中第x個元素，b[x]表示長度為x的不下降子序列的長度，。當(dāng)處理第a[x]時，可查找它可以連接到長度最大為多少的不下降子序列后（即與部分b[x]比較）。假設(shè)可以連到長度最大為maxx的不下降子序列后，則b[x]:=maxx+1。b數(shù)組被賦值的最大值就是第一問的答案。第二問用貪心法即可。每顆導(dǎo)彈來襲時，使用能攔截這顆導(dǎo)彈的防御系統(tǒng)中上一次攔截導(dǎo)彈高度最低的那一套來攔截。若不存在符合這一條件的系統(tǒng)，則使用一套新系統(tǒng)?！緟⒖汲绦颉浚樛品ǎ?include<iostream>#include<cstdio>#include<cstring>usingnamespacestd;intmain(){freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);inti,j,k,x,n,maxx,m,a[10000],b[10000],h[10000];i=1;n=0;m=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(h,0,sizeof(h));while(cin>>a[i]){maxx=0;for(j=1;j<=i-1;j++)//計算前i-1個導(dǎo)彈最佳攔截的方案

if(a[j]>=a[i])if(b[j]>maxx)maxx=b[j];b[i]=maxx+1;if(b[i]>m)m=b[i];x=0;for(k=1;k<=n;k++)//計算由哪一套系統(tǒng)攔截導(dǎo)彈if(h[k]>=a[i])if(x==0)x=k;elseif(h[k]<h[x])x=k;//如果有多套系統(tǒng)可攔截，則選擇上一次攔截高度最低的if(x==0){n++;x=n;}//新增一套導(dǎo)彈攔截系統(tǒng)h[x]=a[i];i++;}cout<<m<<endl<<n<<endl;}經(jīng)過計算，其數(shù)據(jù)存儲表如下

II=1I=2I=3I=4I=5I=6I=7I=8A[I]38920715530029917015865B[I]12323456N值12H[1]38920715565H[2]300299170158【例5】下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費用，單向通行由A->E。試用動態(tài)規(guī)劃的最優(yōu)化原理求出A->E的最省費用。交通圖1

交通圖2

如圖：求v1到v10的最短路徑長度及最短路徑?！緲永斎搿縮hort.in100251000000

000012140000

00006104000

0000131211000

0000000390

0000000650

00000000100

0000000005

0000000002

0000000000【樣例輸出】short.outminlong=19135810【算法分析】逆推法設(shè)f[i]表示點i到v10的最短路徑長度，則f[10]=0

f[i]=min{a[i][x]+f[x]當(dāng)a[i][x]>0,i<x<=n時}#include<iostream>usingnamespacestd;#include<cstring>#include<cstdio>intmain(){longn,i,j,x,f[100],c[100],a[100][100];memset(a,0,sizeof(a));memset(c,0,sizeof(c));cin>>n;for(i=1;i<=n;i++)//輸入各個城市之間距離for(j=1;j<=n;j++)cin>>a[i][j];for(i=1;i<=n;i++)f[i]=1000000;//初始化，默認(rèn)每一個城市到達(dá)終點都是1000000f[n]=0;for(i=n-1;i>=1;i--)//從終點往前逆推，計算最短路徑for(x=i+1;x<=n;x++)//若f[x]=1000000表示城市x到終點城市不通if((a[i][x]>0)&&(f[x]!=1000000)&&(f[i]>a[i][x]+f[x])){//a[i][x]>0表示城市i和城市x通路f[i]=a[i][x]+f[x];//城市i到終點最短路徑的值c[i]=x;}cout<<"minlong="<<f[1]<<endl;//輸出最短路徑的值x=1;

while(x!=0)//輸出路過的各個城市

{

cout<<x<<'';

x=c[x];

}

cout<<endl;

}【例6】挖地雷【問題描述】在一個地圖上有N個地窖（N<=200）,每個地窖中埋有一定數(shù)量的地雷。同時，給出地窖之間的連接路徑，并規(guī)定路徑都是單向的,也不存在可以從一個地窖出發(fā)經(jīng)過若干地窖后又回到原來地窖的路徑。某人可以從任一處開始挖地雷，然后沿著指出的連接往下挖（僅能選擇一條路徑），當(dāng)無連接時挖地雷工作結(jié)束。設(shè)計一個挖地雷的方案，使他能挖到最多的地雷?！据斎敫袷健縉//地窖的個數(shù)

W1，W2，……WN//每個地窖中的地雷數(shù)

X1，Y1//表示從X1可到Y(jié)1X2，Y2……0，0//表示輸入結(jié)束【輸出格式】K1-K2-…-Kv//挖地雷的順序

MAX//最多挖出的地雷數(shù)【輸入樣例】Mine.in6510205451214243445

465600【輸出樣例】Mine.out3-4-5-634【算法分析】本題是一個經(jīng)典的動態(tài)規(guī)劃問題。很明顯，題目規(guī)定所有路徑都是單向的，所以滿足無后效性原則和最優(yōu)化原理。設(shè)W[i]為第i個地窖所藏有的地雷數(shù)，A[i][j]表示第i個地窖與第j個地窖之間是否有通路，F(xiàn)[i]為從第i個地窖開始最多可以挖出的地雷數(shù)，則有如下遞歸式：F[i]=max{W[i]+F[j]}(i<j<=n,A[i][j]=true)邊界：F[n]=W[n]于是就可以通過遞推的方法，從后F(n)往前逐個找出所有的F[i]，再從中找一個最大的即為問題2的解。對于具體所走的路徑（問題1），可以通過一個向后的鏈接來實現(xiàn)?！緟⒖汲绦颉?include<iostream>#include<cstring>usingnamespacestd;intmain(){longf[201]={0},w[201],c[201]={0};boola[201][201]={0};longi,j,n,x,y,l,k,maxx;memset(f,0,sizeof(f));

memset(c,0,sizeof(c));memset(a,false,sizeof(a));cin>>n;for(i=1;i<=n;i++)cin>>w[i];//輸入每個地窖中的地雷數(shù)

do{cin>>x>>y;//表示從X可到Y(jié)if((x!=0)&&(y!=0))a[x][y]=true;}while((x!=0)||(y!=0));f[n]=w[n];//從后F[n]往前逐個找出所有的F[i]for(i=n-1;i>=1;i--){l=0;k=0;for(j=i+1;j<=n;j++)if((a[i][j])&&(f[j]>l)){l=f[j];k=j;}f[i]=l+w[i];//保存從第i個地窖起能挖到最大地雷數(shù)

c[i]=k;//k地窖是i地窖最優(yōu)路徑

}k=1;for(j=2;j<=n;j++)//計算最多挖出的地雷數(shù)

if(f[j]>f[k])k=j;maxx=f[k];cout<<k;

k=c[k];while(k!=0)//輸出挖地雷的順序

{cout<<"-"<<k;k=c[k];}cout<<endl;cout<<maxx<<endl;//輸出最多挖出的地雷數(shù)}【例7】友好城市

【問題描述】Palmia國有一條橫貫東西的大河，河有筆直的南北兩岸，岸上各有位置各不相同的N個城市。北岸的每個城市有且僅有一個友好城市在南岸，而且不同城市的友好城市不相同。每對友好城市都向政府申請在河上開辟一條直線航道連接兩個城市，但是由于河上霧太大，政府決定避免任意兩條航道交叉，以避免事故。編程幫助政府做出一些批準(zhǔn)和拒絕申請的決定，使得在保證任意兩條航線不相交的情況下，被批準(zhǔn)的申請盡量多?！据斎敫袷健康?行，一個整數(shù)N(1<=N<=5000)，表示城市數(shù)。第2行到第n+1行，每行兩個整數(shù)，中間用1個空格隔開，分別表示南岸和北岸的一對友好城市的坐標(biāo)。(0<=xi<=10000)【輸出格式】僅一行，輸出一個整數(shù)，表示政府所能批準(zhǔn)的最多申請數(shù)?！据斎霕永?22426103151298171742【輸出樣例】【算法分析】

我們將每對友好城市看成一條線段，則這道題的描述化為：有N條線段，問最少去掉多少條線，可以使剩下的線段互不交叉？第一，以北岸為線的起點而南岸為線的終點；先將所有的線按照起點坐標(biāo)值從小到大排序，按照每條線的終點坐標(biāo)計算交叉數(shù)：求線I的交叉數(shù)A[I]，則檢查所有1..I-1條線，若線J(1<=J<I)的終點值大于線I的終點值，則線I與線J相交。A[I]與A[J]同時加1。整個搜索量最大為5000*5000。第二，將A數(shù)組從大到小排序，每刪除一條線，則將與之相交的線的A值減1，重復(fù)這個過程，直到所有A值都為0。此時剩下的線則全不交叉。4如上數(shù)據(jù)，則可得下面結(jié)果：編號南岸北岸交叉數(shù)11322242331244515523此時，1、2、3航線的交叉數(shù)都一樣，如果刪去的是3、5線，則剩下的1、2、4線互不相交，最多航線數(shù)為3；但如果刪去的是2、3，則還要刪去第5線才符合要求，此時的最多航線數(shù)為2，不是最優(yōu)解。于是，我們從上面的分析中再深入，將航線按起點坐標(biāo)排好序后，如上所述，在本題中，只要線J的起點小于線I的起點，同時它的終點也小于線I的終點，則線J和線I不相交。因此，求所有線中最多能有多少條線不相交，實際上是從終點坐標(biāo)值數(shù)列中求一個最長不下降序列。這就把題目轉(zhuǎn)化為一個非常典型的動態(tài)規(guī)劃題目了。求最長不下降序列的規(guī)劃方程如下：L(Si)=max{L(Sj)}+1；1<=j<i且Sj<Si。Si為航線的終點坐標(biāo)值。從以上分析過程可以得出：當(dāng)我們拿到一道題時，不要急于求解，而應(yīng)先將題目的表面現(xiàn)象一層層象剝竹筍一樣去掉，只留下最實質(zhì)的內(nèi)容。這時再來設(shè)計算法，往往能事半功倍?！纠?】合唱隊形【問題描述】

N位同學(xué)站成一排，音樂老師要請其中的(N-K)位同學(xué)出列，使得剩下的K位同學(xué)排成合唱隊形。合唱隊形是指這樣的一種隊形：設(shè)K位同學(xué)從左到右依次編號為1,2,…,K，他們的身高分別為T1,T2,…,TK，則他們的身高滿足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。你的任務(wù)是，已知所有N位同學(xué)的身高，計算最少需要幾位同學(xué)出列，可以使得剩下的同學(xué)排成合唱隊形?！据斎胛募枯斎胛募horus.in的第一行是一個整數(shù)N（2≤N≤100），表示同學(xué)的總數(shù)。第二行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti（130≤Ti≤230）是第i位同學(xué)的身高（厘米）?！据敵鑫募枯敵鑫募horus.out包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學(xué)出列?！緲永斎搿?186186150200160130197220【樣例輸出】4【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)，保證有n≤20；對于全部的數(shù)據(jù)，保證有n≤100?！舅惴ǚ治觥课覀儼凑沼勺蠖液陀捎叶蟮捻樞?，將n個同學(xué)的身高排成數(shù)列。如何分別在這兩個數(shù)列中尋求遞增的、未必連續(xù)的最長子序列，就成為問題的關(guān)鍵。設(shè)a為身高序列，其中a[i]為同學(xué)i的身高；b為由左而右身高遞增的人數(shù)序列，其中b[i]為同學(xué)1‥同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然b[i]=max{b[j]|同學(xué)j的身高<同學(xué)i的身高}+1；c為由右而左身高遞增的人數(shù)序列，其中c[i]為同學(xué)n‥同學(xué)i間（包括同學(xué)i）身高滿足遞增順序的最多人數(shù)。顯然c[i]=max{c[j]|同學(xué)j的身高<同學(xué)i的身高}+1；由上述狀態(tài)轉(zhuǎn)移方程可知，計算合唱隊形的問題具備了最優(yōu)子結(jié)構(gòu)性質(zhì)(要使b[i]和c[i]最大，子問題的解b[j]和c[k]必須最大(1≤j≤i-1，i+1≤k≤n))和重迭子問題的性質(zhì)(為求得b[i]和c[i]，必須一一查閱子問題的解b[1]‥b[i-1]和c[i+1]‥c[n])，因此可采用動態(tài)程序設(shè)計的方法求解。顯然，合唱隊的人數(shù)為max{b[i]+c[i]}-1(公式中同學(xué)i被重復(fù)計算，因此減1)，n減去合唱隊人數(shù)即為解。具體算法如下：#include<cstring>#include<iostream>usingnamespacestd;inta[200],b[200],c[200];main(){intn,i,j,maxx;cin>>n;//讀學(xué)生數(shù)

memset(b,0,sizeof(b));//身高滿足遞增順序的兩個隊列初始化

memset(c,0,sizeof(c));for(i=1;i<=n;i++)//讀每個學(xué)生的身高

cin>>a[i];for(i=1;i<=n;i++)//按照由左而右的順序計算b序列

{b[i]=1;for(j=1;j<=i-1;j++)if((a[i]>a[j])&&(b[j]+1>b[i]))b[i]=b[j]+1;}

for(i=n;i>=1;i--)//按照由右而左的順序計算c序列

{c[i]=1;for(j=i+1;j<=n;j++)if((a[j]<a[i])&&(c[j]+1>c[i]))c[i]=c[j]+1;}maxx=0;//計算合唱隊的人數(shù)max（其中1人被重復(fù)計算

for(i=1;i<=n;i++)if(b[i]+c[i]>maxx)maxx=b[i]+c[i];cout<<n-maxx+1<<endl;//輸出出列人數(shù)}這個算法的時間復(fù)雜度為O(n2)，在1秒時限內(nèi)可解決n≤100范圍內(nèi)的問題。【例9】機器分配【問題描述】總公司擁有高效設(shè)備M臺，準(zhǔn)備分給下屬的N個分公司。各分公司若獲得這些設(shè)備，可以為國家提供一定的盈利。問：如何分配這M臺設(shè)備才能使國家得到