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

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

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

——?jiǎng)討B(tài)規(guī)劃是最優(yōu)化算法

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

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

3·b(I,3)表示從I位置開(kāi)始最長(zhǎng)不下降序列的下一個(gè)位置，若b[I,3]=0則表示后面沒(méi)有連接項(xiàng)。㈣求解過(guò)程：①?gòu)牡箶?shù)第二項(xiàng)開(kāi)始計(jì)算，后面僅有1項(xiàng)，比較一次，因63>15，不符合要求，長(zhǎng)度仍為1。②從倒數(shù)第三項(xiàng)開(kāi)始其后有2項(xiàng)，需做兩次比較，得到目前最長(zhǎng)的不下降序列為2，如下表：11121314……11121314226315……21226315211……32111300……121300㈤一般處理過(guò)程是：①在i+1,i+2,…,n項(xiàng)中，找出比b[I,1]大的最長(zhǎng)長(zhǎng)度L以及位置K;②若L>0，則b[I,2]:=L+1;b[I,3]:=k;最后本題經(jīng)過(guò)計(jì)算，其數(shù)據(jù)存儲(chǔ)表如下：123456789101112131413791638243718441921226315787634352432114348979101311121300初始化:for(i=1;i<=n;i++){cin>>b[i][1];b[i][2]=1;b[i][3]=0;}下面給出求最長(zhǎng)不下降序列的算法: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;}}下面找出最長(zhǎng)不下降序列：k=1;for(j=1;j<=n;j++)if(b[j][2]>b[k][2])k=j;最長(zhǎng)不下降序列長(zhǎng)度為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;}

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

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

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

第一問(wèn)即經(jīng)典的最長(zhǎng)不下降子序列問(wèn)題，可以用一般的DP算法，也可以用高效算法，但這個(gè)題的數(shù)據(jù)規(guī)模不需要。用a[x]表示原序列中第x個(gè)元素，b[x]表示長(zhǎng)度為x的不下降子序列的長(zhǎng)度，。當(dāng)處理第a[x]時(shí)，可查找它可以連接到長(zhǎng)度最大為多少的不下降子序列后（即與部分b[x]比較）。假設(shè)可以連到長(zhǎng)度最大為maxx的不下降子序列后，則b[x]:=maxx+1。b數(shù)組被賦值的最大值就是第一問(wèn)的答案。第二問(wèn)用貪心法即可。每顆導(dǎo)彈來(lái)襲時(shí)，使用能攔截這顆導(dǎo)彈的防御系統(tǒng)中上一次攔截導(dǎo)彈高度最低的那一套來(lái)攔截。若不存在符合這一條件的系統(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++)//計(jì)算前i-1個(gè)導(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++)//計(jì)算由哪一套系統(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)過(guò)計(jì)算，其數(shù)據(jù)存儲(chǔ)表如下

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

交通圖2

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

000012140000

00006104000

0000131211000

0000000390

0000000650

00000000100

0000000005

0000000002

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

f[i]=min{a[i][x]+f[x]當(dāng)a[i][x]>0,i<x<=n時(shí)}#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++)//輸入各個(gè)城市之間距離for(j=1;j<=n;j++)cin>>a[i][j];for(i=1;i<=n;i++)f[i]=1000000;//初始化，默認(rèn)每一個(gè)城市到達(dá)終點(diǎn)都是1000000f[n]=0;for(i=n-1;i>=1;i--)//從終點(diǎn)往前逆推，計(jì)算最短路徑for(x=i+1;x<=n;x++)//若f[x]=1000000表示城市x到終點(diǎn)城市不通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到終點(diǎn)最短路徑的值c[i]=x;}cout<<"minlong="<<f[1]<<endl;//輸出最短路徑的值x=1;

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

{

cout<<x<<'';

x=c[x];

}

cout<<endl;

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

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

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

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

465600【輸出樣例】Mine.out3-4-5-634【算法分析】本題是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃問(wèn)題。很明顯，題目規(guī)定所有路徑都是單向的，所以滿(mǎn)足無(wú)后效性原則和最優(yōu)化原理。設(shè)W[i]為第i個(gè)地窖所藏有的地雷數(shù)，A[i][j]表示第i個(gè)地窖與第j個(gè)地窖之間是否有通路，F(xiàn)[i]為從第i個(gè)地窖開(kāi)始最多可以挖出的地雷數(shù)，則有如下遞歸式：F[i]=max{W[i]+F[j]}(i<j<=n,A[i][j]=true)邊界：F[n]=W[n]于是就可以通過(guò)遞推的方法，從后F(n)往前逐個(gè)找出所有的F[i]，再?gòu)闹姓乙粋€(gè)最大的即為問(wèn)題2的解。對(duì)于具體所走的路徑（問(wèn)題1），可以通過(guò)一個(gè)向后的鏈接來(lái)實(shí)現(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];//輸入每個(gè)地窖中的地雷數(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]往前逐個(gè)找出所有的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個(gè)地窖起能挖到最大地雷數(shù)

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

}k=1;for(j=2;j<=n;j++)//計(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】友好城市

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

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

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

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

cin>>a[i];for(i=1;i<=n;i++)//按照由左而右的順序計(jì)算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--)//按照由右而左的順序計(jì)算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;//計(jì)算合唱隊(duì)的人數(shù)max（其中1人被重復(fù)計(jì)算

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