線型動(dòng)態(tài)規(guī)劃000

1、線型動(dòng)態(tài)規(guī)劃線型動(dòng)態(tài)規(guī)劃帶權(quán)有向的多段圖問題帶權(quán)有向的多段圖問題 給定一個(gè)帶權(quán)的有向圖，要求從點(diǎn)A到點(diǎn)D的最短路徑。 設(shè)F(i)表示從點(diǎn)A到達(dá)點(diǎn)i的最短距離，則有 F(A)=0 F(B1)=5,F(B2)=2 F(C1)=minF(B1)+3=8 F(C2)=minF(B1)+2,F(B2)+7=7 F(C3)=minF(B2)+4=6 F(D)=minF(C1)+4,F(C2)+3,F(C3)+5=10多階段最優(yōu)化決策問題多階段最優(yōu)化決策問題l 由上例可以看出，整個(gè)問題分成了由上例可以看出，整個(gè)問題分成了A、B、C、D四個(gè)階段來做，每個(gè)階段的數(shù)值的計(jì)算只會跟上四個(gè)階段來做，每個(gè)階段的數(shù)值的計(jì)

2、算只會跟上一個(gè)階段的數(shù)值相關(guān)，這樣一直遞推下去直到目一個(gè)階段的數(shù)值相關(guān)，這樣一直遞推下去直到目標(biāo)。標(biāo)。l 即由初始狀態(tài)開始，通過對中間階段決策的選擇即由初始狀態(tài)開始，通過對中間階段決策的選擇，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列，同時(shí)確定了完成整個(gè)過程的一條最優(yōu)的活動(dòng)路，同時(shí)確定了完成整個(gè)過程的一條最優(yōu)的活動(dòng)路線線。概念 狀態(tài)狀態(tài)（State）：表示事物的性質(zhì)，是描述“動(dòng)態(tài)規(guī)劃”中的“單元”的量。亦是每一階段求解過程的出發(fā)點(diǎn)。 階段階段（Stage）：階段是一些性質(zhì)相近，可以同時(shí)處理同時(shí)處理的狀態(tài)集合，或者說，階段只是標(biāo)識那些處理方法相同、處理順序

3、無關(guān)的狀態(tài)。 決策決策（Decision）：每個(gè)階段做出的某種選擇性的行動(dòng)，是程序所需要完成的選擇。 狀態(tài)轉(zhuǎn)移方程：狀態(tài)轉(zhuǎn)移方程：是前一個(gè)階段的狀態(tài)轉(zhuǎn)移到后一個(gè)的狀態(tài)的演變規(guī)律，是關(guān)于兩個(gè)相鄰階段狀態(tài)變化的方程，是“動(dòng)態(tài)規(guī)劃”的中心。設(shè)設(shè) fk(i)k階段狀態(tài)i的最優(yōu)權(quán)值，即初始狀態(tài)至狀態(tài)i的最優(yōu)代價(jià) fk+1(i)=minfk(j)+u(i,j) 動(dòng)態(tài)規(guī)劃的基本原理動(dòng)態(tài)規(guī)劃的基本原理l最優(yōu)性原理作為整個(gè)過程的最優(yōu)策略，它滿足：相對前面決策所形成的狀態(tài)而言，余下的子策略必然構(gòu)成“最優(yōu)子策略”。l無后效性原則給定某一階段的狀態(tài)，則在這一階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響，所有各階段都

4、確定時(shí)，整個(gè)過程也就確定了。這個(gè)性質(zhì)意味著過程的歷史只能通過當(dāng)前的狀態(tài)去影響它的未來的發(fā)展，這個(gè)性質(zhì)稱為無后效性。 攔截導(dǎo)彈問題（NOIP1999） 題目簡介題目簡介: 某國為了防御敵國的導(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)彈。 輸入導(dǎo)彈依次飛來的高度（雷達(dá)給出的高度數(shù)據(jù)是不大于30000 的正整數(shù)），計(jì)算這套系統(tǒng)最多能攔截多少導(dǎo)彈，和如果要攔截所有導(dǎo)彈最少要配備多少套這種導(dǎo)彈攔截系統(tǒng)。

5、 樣例：樣例： input 389 207 155 300 299 170 158 65 output 6 解題思路：解題思路： 本試題的實(shí)質(zhì)是在一個(gè)數(shù)列中尋找遞減的、未必連續(xù)的最長子序列。對于這個(gè)問題，我們可以從n出發(fā)，依次反向計(jì)算被攔截的導(dǎo)彈數(shù)。我們假設(shè)當(dāng)導(dǎo)彈i作為被攔截導(dǎo)彈之一時(shí)，F(xiàn)i為導(dǎo)彈i到導(dǎo)彈n序列中可以被攔截的最多導(dǎo)彈數(shù)。對于Fi的求解。我們可以這樣考慮，對于所有導(dǎo)彈j(i+1jn)，如果滿足導(dǎo)彈j的高度，則判斷最大的Fj值，F(xiàn)i就是最大的Fj加上1，即： Fi:=max(Fj|導(dǎo)彈j的高度導(dǎo)彈i的高度)1（i+1jn） 而一套系統(tǒng)能夠攔截最多的導(dǎo)彈數(shù)best就是max(Fi)（

6、1in）。對于這個(gè)例子，從動(dòng)態(tài)規(guī)劃算法的角度看，F(xiàn)i是狀態(tài)，公式Fi:=max(Fj|導(dǎo)彈j的高度導(dǎo)彈i的高度)1（i+1jn）就是狀態(tài)轉(zhuǎn)移方程。 部分參考程序段： best:=0; fillchar(f,sizeof(f),0); for i:=n downto 1 do begin fi:=1; for j:=i+1 to n do if (ajfi) then fi:=fj+1; ai為第i枚導(dǎo)彈的高度 if fibest then best:=fi; end;最長上升序列 設(shè)有整數(shù)序列b1,b2,b3,bm，若存在下標(biāo)i1i2i3 in，且bi1bi2bi3 bin，則稱 b1,b2,

7、b3,bm中有長度為n的上升序列bi1 , bi2 ,bi3 ,bin 。 求序列b1,b2,b3,bm中所有長度(n)最大上升子序列 輸入：整數(shù)序列。 輸出：最大長度n和所有長度為n的序列個(gè)數(shù)。分析 設(shè)設(shè)f f(i)為前為前i個(gè)數(shù)中的最長上升序列長度個(gè)數(shù)中的最長上升序列長度 , 則則 f(i)=maxf(j)+1 (1=jif(i)=maxf(j)+1 (1=ji=m=m, bjbi), bjbi) 邊界為邊界為F(1)=1F(1)=1分析 設(shè)設(shè)t t(i)(i)為前為前i i個(gè)數(shù)中最長序列的個(gè)數(shù)個(gè)數(shù)中最長序列的個(gè)數(shù), ,則則 t(i)=t(j) (t(i)=t(j) (1=ji1=ji=m

8、 , bjbi, f(i)=f(j+1) )=m , bjbi, f(i)=f(j+1) ) 初始為初始為t t(i)=1(i)=1 當(dāng)當(dāng)f(i)=nf(i)=n時(shí)，將時(shí)，將t(i)t(i)累加累加 舉例：舉例： 1 2 3 4 6 5 8 10 9 f: 1 2 3 4 5 5 6 7 7 t: 1 1 1 1 1 1 2 2 2答案：答案：f=7時(shí)，時(shí)，邊界為邊界為t t=4=4進(jìn)一步(3)求本質(zhì)不同的最長序列個(gè)數(shù)有多少個(gè)？ 如：1 2 3 4 6 5 8 10 9 有， 1 2 3 4 6 8 10 , 1 2 3 4 5 8 10, 1 2 3 4 6 8 9 ,1 2 3 4 5 8

9、 9 都是本質(zhì)不同的。 但對于 1 2 2 3 3 5 4 f ： 1 2 2 3 3 4 4 t： 1 1 1 2 2 4 4 答案有8個(gè)，其中4個(gè)1 2 3 5 ，4個(gè)1 2 3 4改進(jìn)算法 上例顯然對于相個(gè)相同的數(shù)，重復(fù)算了多次因此，上例顯然對于相個(gè)相同的數(shù)，重復(fù)算了多次因此，我們對算法進(jìn)行改進(jìn)：我們對算法進(jìn)行改進(jìn)： 對原序列按對原序列按b b從小到大（當(dāng)從小到大（當(dāng)bi=bjbi=bj時(shí)按時(shí)按F F從大到?。拇蟮叫。┡判颍鲈O(shè)排序，增設(shè)Order(i)Order(i)記錄新序列中的記錄新序列中的i i個(gè)數(shù)在原序個(gè)數(shù)在原序列中的位置?？梢姡兄械奈恢?。可見， 求求t(i)t(i)時(shí)，當(dāng)

10、時(shí)，當(dāng)f f(j)=f(j+1),b(j)=b(j+1)(j)=f(j+1),b(j)=b(j+1)且且Order(j+1)Order(i)Order(j+1)Order(i)時(shí)，便不累加時(shí)，便不累加t(j)t(j)。這樣。這樣就避免了重復(fù)。就避免了重復(fù)。 上述算法的時(shí)間復(fù)雜度為上述算法的時(shí)間復(fù)雜度為O(n2) 添括號問題 有一個(gè)由數(shù)字有一個(gè)由數(shù)字1 1，2 2，. . ，9 9組成的數(shù)字串（長組成的數(shù)字串（長度不超過度不超過200200），問如何將），問如何將M(M=20)M(M=20)個(gè)加號個(gè)加號(+)(+)插入到這個(gè)數(shù)字串中，使所形成的算術(shù)表達(dá)式插入到這個(gè)數(shù)字串中，使所形成的算術(shù)表達(dá)式的

11、值最小。請編一個(gè)程序解決這個(gè)問題。的值最小。請編一個(gè)程序解決這個(gè)問題。 注意：注意： 加號不能加在數(shù)字串的最前面或最末尾，也不加號不能加在數(shù)字串的最前面或最末尾，也不應(yīng)有兩個(gè)或兩個(gè)以上的加號相鄰。應(yīng)有兩個(gè)或兩個(gè)以上的加號相鄰。 M M保證小于數(shù)字串的長度。保證小于數(shù)字串的長度。 例如：數(shù)字串例如：數(shù)字串7984679846，若需要加入兩個(gè)加號，則，若需要加入兩個(gè)加號，則最佳方案為最佳方案為79+8+4679+8+46，算術(shù)表達(dá)式的值，算術(shù)表達(dá)式的值133133。分 析 考慮到數(shù)據(jù)的規(guī)模超過了長整型考慮到數(shù)據(jù)的規(guī)模超過了長整型, ,我們注意在解題過程中我們注意在解題過程中采用高精度算法采用高精度

12、算法. . 規(guī)劃方程規(guī)劃方程: : FI,J = MIN FI-1,K + NUMK+1,J (I-FI,J = MIN FI-1,K + NUMK+1,J (I-1=K=J-1)1=K=J-1) 邊界值邊界值:F0,I := NUM1,I:F0,I := NUM1,I; ; FIFI，JJ表示前表示前J J個(gè)數(shù)字中添上個(gè)數(shù)字中添上I I個(gè)加號后得到的最小值。個(gè)加號后得到的最小值。 NUMINUMI，JJ表示數(shù)字串第表示數(shù)字串第I I位到第位到第J J位的數(shù)位的數(shù) 上述問題的每一步，都只與上一步有關(guān)。因此可以采用上述問題的每一步，都只與上一步有關(guān)。因此可以采用滾動(dòng)數(shù)組滾動(dòng)數(shù)組 程序的時(shí)間效率約

13、為程序的時(shí)間效率約為 20 20 * * 200 200 * * 200 200 演唱會 一場演唱會即將舉行?，F(xiàn)有一場演唱會即將舉行?，F(xiàn)有N（ON=200）個(gè)）個(gè)歌迷排隊(duì)買票，一個(gè)人買一張，而售票處規(guī)定，歌迷排隊(duì)買票，一個(gè)人買一張，而售票處規(guī)定，一個(gè)人每次最多只能買兩張票。假設(shè)第一個(gè)人每次最多只能買兩張票。假設(shè)第I位歌迷位歌迷買一張票需要時(shí)間買一張票需要時(shí)間Ti（1=I=n），隊(duì)伍中相），隊(duì)伍中相鄰的兩位歌迷（第鄰的兩位歌迷（第j個(gè)人和第個(gè)人和第j+1個(gè)人）也可以由個(gè)人）也可以由其中一個(gè)人買兩張票，而另一位就可以不用排其中一個(gè)人買兩張票，而另一位就可以不用排隊(duì)了，則這兩位歌迷買兩張票的時(shí)間變?yōu)?/p>

14、隊(duì)了，則這兩位歌迷買兩張票的時(shí)間變?yōu)镽j，(假如假如RjTj+Tj+1，則這樣做就可以縮短后面歌迷，則這樣做就可以縮短后面歌迷等待的時(shí)間，加快整個(gè)售票的進(jìn)程等待的時(shí)間，加快整個(gè)售票的進(jìn)程 )。 現(xiàn)給出現(xiàn)給出N，Ti和和Ri，求使每個(gè)人都買到票的最短，求使每個(gè)人都買到票的最短時(shí)間和方法。時(shí)間和方法。分 析 設(shè)f（i）為前i個(gè)人花費(fèi)最短時(shí)間 于是有f（i）=minf（i-1）+Ti，f（i-2）+Ri-1， 初始f（0）=0，f（1）=T1青蛙過河青蛙過河(NOIP2005) 在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)在河上有一座獨(dú)木橋，一只青蛙想沿著獨(dú)木橋從河的一側(cè)跳到另一側(cè)。在橋上有一

15、些石子，青蛙很討厭踩在這些石跳到另一側(cè)。在橋上有一些石子，青蛙很討厭踩在這些石子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，子上。由于橋的長度和青蛙一次跳過的距離都是正整數(shù)，我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串我們可以把獨(dú)木橋上青蛙可能到達(dá)的點(diǎn)看成數(shù)軸上的一串整點(diǎn)：整點(diǎn)：0，1，L（其中（其中L是橋的長度）。坐標(biāo)為是橋的長度）。坐標(biāo)為0的點(diǎn)的點(diǎn)表示橋的起點(diǎn)，坐標(biāo)為表示橋的起點(diǎn)，坐標(biāo)為L的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的的點(diǎn)表示橋的終點(diǎn)。青蛙從橋的起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。一次跳躍的距離是起點(diǎn)開始，不停的向終點(diǎn)方向跳躍。一次跳躍的距離是S到到T之間的任意正整數(shù)（包括之間的任意正

16、整數(shù)（包括S,T）。當(dāng)青蛙跳到或跳過坐）。當(dāng)青蛙跳到或跳過坐標(biāo)為標(biāo)為L的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。的點(diǎn)時(shí)，就算青蛙已經(jīng)跳出了獨(dú)木橋。 題目給出獨(dú)木橋的長度題目給出獨(dú)木橋的長度L，青蛙跳躍的距離范圍，青蛙跳躍的距離范圍S,T，橋上，橋上石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩石子的位置。你的任務(wù)是確定青蛙要想過河，最少需要踩到的石子數(shù)。到的石子數(shù)?！据斎胛募斎胛募?輸入文件輸入文件river.in的第一行有一個(gè)正整數(shù)的第一行有一個(gè)正整數(shù)L（1 = L = 109），表示獨(dú)木橋的長度。第二行有三個(gè)正整數(shù)，表示獨(dú)木橋的長度。第二行有三個(gè)正整數(shù)S，T，M，分，分別表示青蛙一次跳躍的

17、最小距離，最大距離，及橋上石子別表示青蛙一次跳躍的最小距離，最大距離，及橋上石子的個(gè)數(shù)，其中的個(gè)數(shù)，其中1 = S = T = 10，1 = M = 100。第三行有。第三行有M個(gè)不同的正整數(shù)分別表示這個(gè)不同的正整數(shù)分別表示這M個(gè)石子在數(shù)軸上的位置（個(gè)石子在數(shù)軸上的位置（數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)數(shù)據(jù)保證橋的起點(diǎn)和終點(diǎn)處沒有石子）。所有相鄰的整數(shù)之間用一個(gè)空格隔開。之間用一個(gè)空格隔開?！据敵鑫募敵鑫募?輸出文件輸出文件river.out只包括一個(gè)整數(shù)，表示青蛙過河最少需只包括一個(gè)整數(shù)，表示青蛙過河最少需要踩到的石子數(shù)。要踩到的石子數(shù)?！緲永斎霕永斎搿?02 3

18、52 3 5 6 7【樣例輸出樣例輸出】2【數(shù)據(jù)規(guī)模數(shù)據(jù)規(guī)模】對于對于30%的數(shù)據(jù)，的數(shù)據(jù)，L = 10000；對于全部的數(shù)據(jù)，對于全部的數(shù)據(jù)，L = 109。 分析 由于不能往回跳，很容易想到用動(dòng)態(tài)規(guī)劃解決這個(gè)題目。由于不能往回跳，很容易想到用動(dòng)態(tài)規(guī)劃解決這個(gè)題目。 設(shè)設(shè)f(i)表示跳到第表示跳到第i個(gè)點(diǎn)需要踩到的最少石子數(shù)，則很容易個(gè)點(diǎn)需要踩到的最少石子數(shù)，則很容易寫出動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程寫出動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程:1)-Tf(L1),.,f(Lminf(L),Ans i T)k(S 1k)-f(i i T)k(S k)-f(imin)(0)0(點(diǎn)有石子第點(diǎn)沒有石子第iff 時(shí)間復(fù)雜度是

19、時(shí)間復(fù)雜度是O(L*(T-S)，但本題的，但本題的L高達(dá)高達(dá)109，根本無，根本無法承受法承受! 進(jìn)一步分析 我們先來考慮這樣一個(gè)問題：長度為我們先來考慮這樣一個(gè)問題：長度為k的一段沒有的一段沒有石子的獨(dú)木橋，判斷是否存在一種跳法從一端正石子的獨(dú)木橋，判斷是否存在一種跳法從一端正好跳到另一端。好跳到另一端。 若若S=MaxK，都可以從一端，都可以從一端正好跳到另一端。正好跳到另一端。 題設(shè)中題設(shè)中1=S=T=10，經(jīng)過簡單推導(dǎo)或者程序驗(yàn)證，經(jīng)過簡單推導(dǎo)或者程序驗(yàn)證就可以發(fā)現(xiàn)，取就可以發(fā)現(xiàn)，取MaxK=100就能滿足所有區(qū)間。就能滿足所有區(qū)間。 于是我們可以分兩種情況討論：于是我們可以分兩種情況

20、討論：1. S=T時(shí)：時(shí)：這時(shí)候由于每一步只能按固定步長跳，所以若第這時(shí)候由于每一步只能按固定步長跳，所以若第i個(gè)位置上個(gè)位置上有石子并且有石子并且i mod S=0那么這個(gè)石子就一定要被踩到。這是那么這個(gè)石子就一定要被踩到。這是我們只需要統(tǒng)計(jì)石子的位置中哪些是我們只需要統(tǒng)計(jì)石子的位置中哪些是S的倍數(shù)即可。復(fù)雜度的倍數(shù)即可。復(fù)雜度O(M)2. SMaxK+2*T，我們就將這段區(qū)域縮短成長度為，我們就將這段區(qū)域縮短成長度為MaxK+2*T?？梢宰C明處理之后的最優(yōu)值和原先的最優(yōu)值相。可以證明處理之后的最優(yōu)值和原先的最優(yōu)值相同。同。ab如上圖所示，白色點(diǎn)表示連續(xù)的一長段長度大于如上圖所示，白色點(diǎn)表示

21、連續(xù)的一長段長度大于MaxK+2*T的空地，黑色點(diǎn)表示石子。設(shè)原先的最優(yōu)解中，白色段的第的空地，黑色點(diǎn)表示石子。設(shè)原先的最優(yōu)解中，白色段的第一個(gè)被跳到的位置一個(gè)被跳到的位置a，最后一個(gè)被跳到的位置是，最后一個(gè)被跳到的位置是b，則在做壓，則在做壓縮處理之后，縮處理之后，a和和b的距離仍然大于的距離仍然大于MaxK，由上面的結(jié)論可，由上面的結(jié)論可知，必存在一種跳法從知，必存在一種跳法從a正好跳到正好跳到b，而且不經(jīng)過任何石子。，而且不經(jīng)過任何石子。 所以原來的最優(yōu)解必然在處理之后的最優(yōu)解所以原來的最優(yōu)解必然在處理之后的最優(yōu)解解集中。解集中。 經(jīng)過這樣的壓縮處理，獨(dú)木橋的長度經(jīng)過這樣的壓縮處理，獨(dú)木

22、橋的長度L最多最多為為(M+1)*(MaxK+2*T)+M，大約，大約12000左右。左右。壓縮之后再用先前的動(dòng)態(tài)規(guī)劃求解，復(fù)雜度壓縮之后再用先前的動(dòng)態(tài)規(guī)劃求解，復(fù)雜度就簡化成了就簡化成了O(L*(T-S)，已經(jīng)可以在時(shí)限內(nèi)出，已經(jīng)可以在時(shí)限內(nèi)出解了。解了。 這樣本題就得到了解決。這樣本題就得到了解決。背包類動(dòng)態(tài)規(guī)劃問題背包類動(dòng)態(tài)規(guī)劃問題經(jīng)典的背包問題（經(jīng)典的背包問題（01背包）背包） 有有N件物品件物品; 第第i件物品件物品Wi公斤公斤; 第第i件物品價(jià)值件物品價(jià)值Ci元元; 現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車; 問選取裝載哪些物品，使得卡車運(yùn)送的問選取裝載哪些物品，使得卡車運(yùn)送

23、的總價(jià)值最大？總價(jià)值最大？搜索法 對于每種物品，要么裝上卡車，要么不裝，因此，對于每種物品，要么裝上卡車，要么不裝，因此，N種種物品的裝箱方案共有物品的裝箱方案共有2N種。種。 按每種物品進(jìn)行搜索，方法如下：按每種物品進(jìn)行搜索，方法如下： 對第對第i種物品進(jìn)行搜索種物品進(jìn)行搜索 如果所有的物品都搜索完，則更新最優(yōu)解如果所有的物品都搜索完，則更新最優(yōu)解 如果當(dāng)前的估計(jì)達(dá)不到最優(yōu)解，則回溯如果當(dāng)前的估計(jì)達(dá)不到最優(yōu)解，則回溯 如果第如果第i種物品能放，則放，并標(biāo)記，否則選下一個(gè)種物品能放，則放，并標(biāo)記，否則選下一個(gè)物品物品 清除標(biāo)記清除標(biāo)記 回溯回溯動(dòng)態(tài)規(guī)劃 可以按每個(gè)物品進(jìn)行規(guī)劃，同樣每種物品有選

24、和不選兩種選擇 設(shè)F(i,j)表示前i件物品載重為j的最大效益，則有 1=i=N, 0=j=wi then /背包容量夠大 fi,j:=max(fi-1,j-wi+ci,fi-1,j)else /背包容量不足 fi,j:=fi-1,j;end;滿背包問題（滿背包問題（01背包）背包） 有有N件物品件物品; 第第i件物品件物品Wi公斤公斤; 第第i件物品價(jià)值件物品價(jià)值Ci元元; 現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車; 問選取裝載哪些物品，使得卡車開車正問選取裝載哪些物品，使得卡車開車正好裝滿時(shí)，運(yùn)送的總價(jià)值最大？好裝滿時(shí)，運(yùn)送的總價(jià)值最大？若無法裝滿卡車，則輸出無解。若無法裝滿卡車，則

25、輸出無解。動(dòng)態(tài)規(guī)劃 設(shè)F(i,j)表示前i件物品背包為j的最大效益，則有 1=i=N, 0=j=N 初值：初值：F(0,j)=0， F(1,j)= - F(N,M)即答案 顯然時(shí)間復(fù)雜度為O(NM)種物品不裝載第種物品裝載第ijiFiiCiwjiFMaxjiF), 1(,), 1(),(帶條件的背包問題（帶條件的背包問題（1） 有有N件物品件物品; 第第i件物品件物品Wi公斤公斤; 第第i件物品價(jià)值件物品價(jià)值Ci元元; 第第i件物品可能帶件物品可能帶02個(gè)附件；個(gè)附件； 若裝載附件，必須裝載主件，反之沒有約束；若裝載附件，必須裝載主件，反之沒有約束； 現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的

26、卡車; 問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？大？分析 假設(shè)只有主件的情況假設(shè)只有主件的情況 ，顯然與經(jīng)典背包問題完，顯然與經(jīng)典背包問題完全相同！全相同！ 現(xiàn)在每個(gè)物品有附件，我們可以分成現(xiàn)在每個(gè)物品有附件，我們可以分成4種方案種方案 僅裝載主件僅裝載主件 裝載主件裝載主件+第第1個(gè)附件個(gè)附件 裝載主件裝載主件+第第2個(gè)附件個(gè)附件 裝載主件裝載主件+2個(gè)附件個(gè)附件 由于上述由于上述4種并列，這是幾種不同的決策同時(shí)規(guī)種并列，這是幾種不同的決策同時(shí)規(guī)劃即可劃即可動(dòng)態(tài)規(guī)劃 設(shè)設(shè)F(i,j)表示前表示前i件物品背包為件物品背包為j的最優(yōu)解，則有，的最優(yōu)

27、解，則有， 1=i=N, 0=j=M 時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(NM)件附件選主件和，件附件選主件和第，件附件選主件和第，只選主件件物品不選第2/21)2-1w-, 1(2/2)2-, 1(1/1)1w-, 1(), 1(i), 1(),(iciciciwiiwjiFiciciwiwjiFiciciiwjiFiciwjiFjiFMaxjiF多層背包問題 有有N件物品件物品; 第第i件物品件物品Wi公斤公斤; 第第i件物品價(jià)值件物品價(jià)值Ci元元; 現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車; 第第i件物品限制最多只能取件物品限制最多只能取Xi個(gè)；個(gè)； 問選取裝載哪些物品，使得卡車運(yùn)送的總問選取

28、裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？價(jià)值最大？分析 我們可以類似我們可以類似01背包問題，將第背包問題，將第i種物品拆分成種物品拆分成xi個(gè)，這樣每個(gè)物品只有個(gè)，這樣每個(gè)物品只有1件了件了,如下圖如下圖: 然后對所有的物品采用動(dòng)態(tài)規(guī)劃即可。然后對所有的物品采用動(dòng)態(tài)規(guī)劃即可。 F(i,j)=max f(i-1,j-k*wi) + k*ci 0=k*wi=j完全背包問題 有有N件物品件物品; 第第i件物品件物品Wi公斤公斤; 第第i件物品價(jià)值件物品價(jià)值Ci元元; 現(xiàn)有一輛載重現(xiàn)有一輛載重M公斤的卡車公斤的卡車; 每次可以選取某種物品的任意多件裝載；每次可以選取某種物品的任意多件裝載； 問選取裝

29、載哪些物品，使得卡車運(yùn)送的總問選取裝載哪些物品，使得卡車運(yùn)送的總價(jià)值最大？價(jià)值最大？分析 類似多層背包問題將每個(gè)物品展開成類似多層背包問題將每個(gè)物品展開成Xi =m/wi個(gè)，然個(gè)，然后對所有的物品采用動(dòng)態(tài)規(guī)劃即可。后對所有的物品采用動(dòng)態(tài)規(guī)劃即可。 若兩件物品若兩件物品i、j滿足滿足ci=wj,則將物品則將物品i去掉去掉,不用考慮。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將不用考慮。這個(gè)優(yōu)化的正確性顯然：任何情況下都可將價(jià)值小費(fèi)用高的價(jià)值小費(fèi)用高的i換成物美價(jià)廉的換成物美價(jià)廉的j,得到至少不會更差的得到至少不會更差的方案。方案。 由于每種物品有選和不選兩種情況，可以將每種物品的由于每種物品有選和不選

30、兩種情況，可以將每種物品的2k個(gè)當(dāng)成一個(gè)整體考慮。這樣對于某種物品要選取多個(gè)個(gè)當(dāng)成一個(gè)整體考慮。這樣對于某種物品要選取多個(gè)，都可以由若干個(gè)，都可以由若干個(gè)2k個(gè)物品進(jìn)行組合個(gè)物品進(jìn)行組合 (即即2進(jìn)制數(shù)進(jìn)制數(shù))。例如。例如第第i種物品要選種物品要選10個(gè)，則個(gè)，則10=23+21 。 這樣第這樣第i種物品的個(gè)數(shù)為種物品的個(gè)數(shù)為k=2 (m/wi)物品，是一個(gè)很大物品，是一個(gè)很大的改進(jìn)。的改進(jìn)。 進(jìn)一步進(jìn)一步, 在計(jì)算在計(jì)算k時(shí)時(shí), K =2 (j/wi), j為當(dāng)前背包剩余空間。為當(dāng)前背包剩余空間。進(jìn)一步for i:=1 to n do / 動(dòng)態(tài)規(guī)劃，遞推求動(dòng)態(tài)規(guī)劃，遞推求ffor j:=1

31、to m dobeginif j=wi then /背包容量夠大背包容量夠大 fi,j:=max(fi,j-wi+ci,fi-1,j)else /背包容量不足背包容量不足 fi,j:=fi-1,j;end; 改進(jìn)程序 事實(shí)上，我們只關(guān)心剩余背包的最大值，也就是事實(shí)上，我們只關(guān)心剩余背包的最大值，也就是僅僅關(guān)心僅僅關(guān)心f(j),因此，在對因此，在對f(j)更新時(shí)，只要背包容更新時(shí)，只要背包容量可以，那么可以反復(fù)更新。程序如下：量可以，那么可以反復(fù)更新。程序如下：for i:=1 to n do / 動(dòng)態(tài)規(guī)劃，遞推求動(dòng)態(tài)規(guī)劃，遞推求ffor j:=0 to m dobeginif j=wi the

32、n /背包容量夠大背包容量夠大 fj:=max(fj-wi+ci,fj)end;思考題思考題1：機(jī)器分配：機(jī)器分配 M M臺設(shè)備，分給臺設(shè)備，分給N N個(gè)公司。個(gè)公司。 若公司若公司i i獲得獲得j j臺設(shè)備，則能產(chǎn)生臺設(shè)備，則能產(chǎn)生AijAij效益效益 問如何分配設(shè)備使得總效益最大？問如何分配設(shè)備使得總效益最大？ M M =15=15，N=10N=10。分析 用機(jī)器數(shù)來做狀態(tài)，數(shù)組f(i,j)表示前i個(gè)公司分配j臺機(jī)器的最大盈利。則狀態(tài)轉(zhuǎn)移方程為: f(i,j) =Maxfi-1，k + ai，j-j (1=i=N,1=j=M,0=k=j ) 初始值: f(0,0)=0 時(shí)間復(fù)雜度O(N*M

33、2)思考題思考題2：硬幣找零：硬幣找零l給定給定N枚硬幣枚硬幣l給定給定T元錢元錢l用這用這N枚硬幣找這枚硬幣找這T元錢，使得剩下的錢最元錢，使得剩下的錢最少。少。l剩下錢數(shù)最少的找零方案中的所需的最少剩下錢數(shù)最少的找零方案中的所需的最少硬幣數(shù)。硬幣數(shù)。lN=500,T=10000.分析分析l設(shè)設(shè)Fi表示需要找的錢數(shù)為表示需要找的錢數(shù)為i時(shí)所需要的最少時(shí)所需要的最少錢幣數(shù)。顯然有：錢幣數(shù)。顯然有：lFi=MinF i - Aj + 1 i T，1jNl初始值：初始值：F0=0。lAj表示其中表示其中 第第j種錢幣的面值。種錢幣的面值。l時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(N*T)。思考題思考題3：系統(tǒng)

34、可靠性：系統(tǒng)可靠性 一個(gè)系統(tǒng)由若干部件串聯(lián)而成，只要有一個(gè)部件一個(gè)系統(tǒng)由若干部件串聯(lián)而成，只要有一個(gè)部件故障，系統(tǒng)就不能正常運(yùn)行，為提高系統(tǒng)的可靠故障，系統(tǒng)就不能正常運(yùn)行，為提高系統(tǒng)的可靠性，每一部件都裝有備用件，一旦原部件故障，性，每一部件都裝有備用件，一旦原部件故障，備用件就自動(dòng)進(jìn)入系統(tǒng)。顯然備用件越多，系統(tǒng)備用件就自動(dòng)進(jìn)入系統(tǒng)。顯然備用件越多，系統(tǒng)可靠性越高，但費(fèi)用也越大，那么在一定總費(fèi)用可靠性越高，但費(fèi)用也越大，那么在一定總費(fèi)用限制下，系統(tǒng)的最高可靠性等于多少？限制下，系統(tǒng)的最高可靠性等于多少？ 給定一些系統(tǒng)備用件的單價(jià)給定一些系統(tǒng)備用件的單價(jià)CkCk，以及當(dāng)用，以及當(dāng)用MkMk個(gè)此個(gè)

35、此備用件時(shí)部件的正常工作概率備用件時(shí)部件的正常工作概率PkPk（MkMk），總費(fèi)用），總費(fèi)用上限上限C C。求系統(tǒng)可能的最高可靠性。求系統(tǒng)可能的最高可靠性。 樣例樣例輸入文件格式：輸入文件格式：第一行：第一行：n Cn C第二行：第二行：C1 P1(0) P1(1) C1 P1(0) P1(1) P1(X1) P1(X1) （0=X1=C/Ck0=X1=C/Ck） 第第n n 行：行：Cn Pn(0) Pn(1) Cn Pn(0) Pn(1) Pn(Xn) Pn(Xn) （0=Xn=C/Cn0=Xn=C/Cn）輸入：輸入：2 202 20 3 0.6 0.65 0.7 0.75 0.8 0.8

36、5 0.93 0.6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.9 0.95 5 0.7 0.75 0.8 0.9 0.95輸出：輸出：0.6375=0.750.6375=0.75* *0.850.85分析 設(shè)設(shè)f(i,j)f(i,j)表示將表示將j j的資金用到前的資金用到前i i項(xiàng)備用件項(xiàng)備用件中去的最大可靠性，則有中去的最大可靠性，則有 F(i,j)=F(i,j)= maxF(i-1,j maxF(i-1,jk k* *Costi)Costi)* *Pi,kPi,k 0=i=n, 0=j=C, 0=i=n, 0=j=C,0=0=k kj di

37、v Cost(j div Cost(i i) ) 初始：初始： F(0,0)=1F(0,0)=1 目標(biāo)：目標(biāo)： F(n,C)F(n,C) 時(shí)間復(fù)雜度：時(shí)間復(fù)雜度：O(kO(k* *n n* *C)C)，這里，這里k k是常數(shù)因子是常數(shù)因子，與數(shù)據(jù)相關(guān)，與數(shù)據(jù)相關(guān)總結(jié)總結(jié) 對于資源類動(dòng)態(tài)規(guī)劃問題，我們可以看出，問題描述必須對于資源類動(dòng)態(tài)規(guī)劃問題，我們可以看出，問題描述必須有一個(gè)基本要素：資源，有時(shí)這種資源可能是金錢、空間有一個(gè)基本要素：資源，有時(shí)這種資源可能是金錢、空間或者時(shí)間，問題就是要對這些資源如何分配，一種基本的或者時(shí)間，問題就是要對這些資源如何分配，一種基本的想法是將資源應(yīng)用于前想法是將

38、資源應(yīng)用于前i個(gè)階段，然后考慮第個(gè)階段，然后考慮第i個(gè)階段和前個(gè)階段和前i-1個(gè)階段之間的關(guān)系。個(gè)階段之間的關(guān)系。 設(shè)前設(shè)前i個(gè)點(diǎn)的消耗個(gè)點(diǎn)的消耗j的資源得到的最優(yōu)值，研究前的資源得到的最優(yōu)值，研究前i-1個(gè)點(diǎn)消個(gè)點(diǎn)消耗的資源的最優(yōu)值，利用第耗的資源的最優(yōu)值，利用第i個(gè)點(diǎn)決策轉(zhuǎn)移，如下圖。個(gè)點(diǎn)決策轉(zhuǎn)移，如下圖。 狀態(tài)轉(zhuǎn)移方程一般可寫成狀態(tài)轉(zhuǎn)移方程一般可寫成: f fi i(j) = min fi-1i-1 ( k) + ui (j,k) 區(qū)間類動(dòng)態(tài)規(guī)劃區(qū)間類動(dòng)態(tài)規(guī)劃整數(shù)劃分整數(shù)劃分 給出一個(gè)長度為給出一個(gè)長度為n的數(shù)的數(shù) 要在其中加要在其中加m-1個(gè)乘號，分成個(gè)乘號，分成m段段 這這m段的乘積

39、之和最大段的乘積之和最大 mn=20 有有T組數(shù)據(jù)，組數(shù)據(jù)，T=10000貪心法貪心法 盡可能平均分配各段，這樣最終的數(shù)值將會盡可能大。但盡可能平均分配各段，這樣最終的數(shù)值將會盡可能大。但有反例。如有反例。如191919分成分成3段段 19*19*19=6859但但191*91*9=156429，顯然乘積更大。，顯然乘積更大。 將一個(gè)數(shù)分成若干段乘積后比該數(shù)小，因?yàn)檩斎霐?shù)不超過將一個(gè)數(shù)分成若干段乘積后比該數(shù)小，因?yàn)檩斎霐?shù)不超過20位，因此不需高精度運(yùn)算。位，因此不需高精度運(yùn)算。 證明：證明： 假設(shè)假設(shè)AB分成分成A和和B,且且A,BA*B(相當(dāng)于相當(dāng)于B個(gè)個(gè)A相加相加) 同理可證明同理可證明A

40、,B為任意位也成立為任意位也成立動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 可以先預(yù)處理出原數(shù)第可以先預(yù)處理出原數(shù)第i到到j(luò)段的數(shù)值段的數(shù)值A(chǔ)i,j是多少，是多少，這樣轉(zhuǎn)移就方便了，預(yù)處理也要盡量降低復(fù)雜度。這樣轉(zhuǎn)移就方便了，預(yù)處理也要盡量降低復(fù)雜度。 Fi，j表示把這個(gè)數(shù)前表示把這個(gè)數(shù)前i位分成位分成j段得到的最大乘積。段得到的最大乘積。 Fi,j=maxFk,j-1*Ak+1,i 1ki=n, j=m 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為Om2n 由于有由于有10000組數(shù)據(jù)，因此估計(jì)時(shí)間復(fù)雜度為組數(shù)據(jù)，因此估計(jì)時(shí)間復(fù)雜度為10000*203=8*107 至于說輸出，記錄轉(zhuǎn)移的父親就可以了。至于說輸出，記錄轉(zhuǎn)移的父親就可以了。

41、石子合并 l 在一園形操場四周擺放在一園形操場四周擺放N堆石子堆石子(N100)；l 現(xiàn)要將石子有次序地合并成一堆；現(xiàn)要將石子有次序地合并成一堆；l 規(guī)定每次只能選相臨的兩堆合并成一堆規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的并將新的一堆的石子數(shù)一堆的石子數(shù),記為該次合并的得分。記為該次合并的得分。選擇一種合并石子的方案選擇一種合并石子的方案,使得做使得做N-1次合并次合并,得分的總和最少得分的總和最少 選擇一種合并石子的方案選擇一種合并石子的方案,使得做使得做N-1次合并次合并,得分的總和最大得分的總和最大示例貪心法 N=5 石子數(shù)分別為石子數(shù)分別為3 4 6 5 4 2。用貪心法的合并過

42、程如下：用貪心法的合并過程如下：第一次第一次 3 4 6 5 4 2得分得分 5第二次第二次 5 4 6 5 4得分得分9第三次第三次 9 6 5 4得分得分9第四次第四次 9 6 9得分得分15第五次第五次 15 9得分得分24第六次第六次24總分：總分：62然而有更好的方案：然而有更好的方案：第一次第一次3 4 6 5 4 2得分得分 7第二次第二次7 6 5 4 2得分得分13第三次第三次13 5 4 2得分得分6第四次第四次13 5 6得分得分11第五次第五次 13 11得分得分24第六次第六次24總分：總分：61顯然，貪心法是錯(cuò)誤的。顯然，貪心法是錯(cuò)誤的。 分析 假設(shè)只有假設(shè)只有2堆

43、石子，顯然只有堆石子，顯然只有1種合并方案種合并方案 如果有如果有3堆石子，則有堆石子，則有2種合并方案，種合并方案，(1,2),3)和和(1,(2,3) 如果有如果有k堆石子呢？堆石子呢？ 不管怎么合并，總之最后總會歸結(jié)為不管怎么合并，總之最后總會歸結(jié)為2堆，如果我們把最堆，如果我們把最后兩堆分開，左邊和右邊無論怎么合并，都必須滿足最優(yōu)后兩堆分開，左邊和右邊無論怎么合并，都必須滿足最優(yōu)合并方案，整個(gè)問題才能得到最優(yōu)解。如下圖：合并方案，整個(gè)問題才能得到最優(yōu)解。如下圖：動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 設(shè)設(shè)ti,j表示從第表示從第i堆到第堆到第j堆石子數(shù)總和。堆石子數(shù)總和。Fmax(i,j)表示將從第表示將從第i堆石子合并到第堆石子合并到第j堆石子的最大的得分堆石子的最大的得分Fmin(i,j)表示將從第表示將從第i堆石子合并到第堆石子合并到第j堆石子的最小的得分堆石子的最小的得分同理，同理， Fmaxi,i = 0，F(xiàn)mini,i = 0 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n3),), 1max(),max(),max(max1jitjkFkiFjiFjki,), 1min