![動(dòng)態(tài)程序設(shè)計(jì)朱全民_第1頁(yè)](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/c29569f2-04fd-49ce-9d2b-db2be5cb202b/c29569f2-04fd-49ce-9d2b-db2be5cb202b1.gif)
![動(dòng)態(tài)程序設(shè)計(jì)朱全民_第2頁(yè)](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/c29569f2-04fd-49ce-9d2b-db2be5cb202b/c29569f2-04fd-49ce-9d2b-db2be5cb202b2.gif)
![動(dòng)態(tài)程序設(shè)計(jì)朱全民_第3頁(yè)](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/c29569f2-04fd-49ce-9d2b-db2be5cb202b/c29569f2-04fd-49ce-9d2b-db2be5cb202b3.gif)
![動(dòng)態(tài)程序設(shè)計(jì)朱全民_第4頁(yè)](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/c29569f2-04fd-49ce-9d2b-db2be5cb202b/c29569f2-04fd-49ce-9d2b-db2be5cb202b4.gif)
![動(dòng)態(tài)程序設(shè)計(jì)朱全民_第5頁(yè)](http://file3.renrendoc.com/fileroot_temp3/2022-3/10/c29569f2-04fd-49ce-9d2b-db2be5cb202b/c29569f2-04fd-49ce-9d2b-db2be5cb202b5.gif)
版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、動(dòng)態(tài)程序設(shè)計(jì)動(dòng)態(tài)程序設(shè)計(jì)朱全民基本原理1、多階段最優(yōu)化決策:、多階段最優(yōu)化決策:即由初始狀態(tài)開(kāi)始,通過(guò)對(duì)中間階段決策的選擇,達(dá)到結(jié)束狀態(tài)。這些決策形成了一個(gè)決策序列,同時(shí)確定了完成整個(gè)過(guò)程的一條最優(yōu)的活動(dòng)路線。帶權(quán)有向的多段圖 上一階段的狀態(tài)下一階段的狀態(tài)決策概念w 狀態(tài)狀態(tài)(State):表示事物的性質(zhì),是描述“動(dòng)態(tài)規(guī)劃”中的“單元”的量。亦是每一階段求解過(guò)程的出發(fā)點(diǎn)。w 階段階段(Stage):階段是一些性質(zhì)相近,可以同時(shí)處理同時(shí)處理的狀態(tài)集合,或者說(shuō),階段只是標(biāo)識(shí)那些處理方法相同、處理順序無(wú)關(guān)的狀態(tài)。w 決策決策(Decision):每個(gè)階段做出的某種選擇性的行動(dòng),是程序所需要完成的選擇
2、。w 狀態(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)=minxk(j)+u(i,j) 基本原理w 最優(yōu)性原理作為整個(gè)過(guò)程的最優(yōu)策略,它滿足:相對(duì)前面決策所形成的狀態(tài)而言,余下的子策略必然構(gòu)成“最優(yōu)子策略”。無(wú)后效性原則給定某一階段的狀態(tài),則在這一階段以后過(guò)程的發(fā)展不受這階段以前各段狀態(tài)的影響,所有各階段都確定時(shí),整個(gè)過(guò)程也就確定了。這個(gè)性質(zhì)意味著過(guò)程的歷史只能通過(guò)當(dāng)前的狀態(tài)去影響它的未來(lái)的發(fā)展,這個(gè)性質(zhì)稱為無(wú)后效性。機(jī)器分配
3、w 總公司擁有高效生產(chǎn)設(shè)備M臺(tái),準(zhǔn)備分給下屬的N個(gè)公司。各分公司若獲得這些設(shè)備,可以為國(guó)家提供一定的盈利。問(wèn):如何分配這M臺(tái)設(shè)備才能使國(guó)家得到的盈利最大?求出最大盈利值。其中M=15,N=10。分配原則:每個(gè)公司有權(quán)獲得任意數(shù)目的設(shè)備,但總臺(tái)數(shù)不得超過(guò)總設(shè)備數(shù)M。w 數(shù)據(jù)文件格式為:第一行保存兩個(gè)數(shù),第一個(gè)數(shù)是設(shè)備臺(tái)數(shù)M,第二個(gè)數(shù)是分公司數(shù)N。接下來(lái)是一個(gè)M*N的矩陣,表明了第I個(gè)公司分配J臺(tái)機(jī)器的盈利。 分析w 用機(jī)器數(shù)來(lái)做狀態(tài),數(shù)組FI,J表示前I個(gè)公司分配J臺(tái)機(jī)器的最大盈利。則狀態(tài)轉(zhuǎn)移方程為:w FI,J=MaxFI-1,K + ValueI,J-K (1=I=N,1=J=M,0=K=J
4、 )w 初始值: F(0,0)=0w 時(shí)間復(fù)雜度O(N*M2)最長(zhǎng)不下降序列 w 設(shè)有整數(shù)序列b1,b2,b3,bm,若存在下標(biāo)i1i2i3 in,且bi1bi2bi3 bin,則稱 b1,b2,b3,bm中有長(zhǎng)度為n的不下降序列bi1 , bi2 ,bi3 ,bin 。w 求序列b1,b2,b3,bm中所有長(zhǎng)度(n)最大不下降子序列w 輸入:整數(shù)序列。w 輸出:最大長(zhǎng)度n和所有長(zhǎng)度為n的序列個(gè)數(shù)。分析(1)設(shè)f(i)為前i個(gè)數(shù)中的最大不下降序列長(zhǎng)度 , 則w f(i)=maxf(j)+1 (1=ji=m, bjbi)w 邊界為F(1)=1(2)設(shè)t(i)為前i個(gè)數(shù)中最長(zhǎng)不下降序列的個(gè)數(shù),則w
5、 t(i)=t(j) (1=ji=m , bjbi, f(i)=f(j)-1) w 初始為t(i)=1w 當(dāng)f(i)=n時(shí),將t(i)累加w 舉例: 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í),邊界為t=4進(jìn)一步(3)求本質(zhì)不同的最長(zhǎng)不下降序列個(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 都是本質(zhì)不同的。 但對(duì)于 1 2 2 3 3 5 4 f 1 2 2 3 3
6、 5 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)算法w 上例顯然對(duì)于相兩個(gè)相同的數(shù),重復(fù)算了多次因此,我們對(duì)算法進(jìn)行改進(jìn):w 對(duì)原序列按b從小到大(當(dāng)bi=bj時(shí)按F從大到?。┡判颍鲈O(shè)Order(i)記錄新序列中的i個(gè)數(shù)在原序列中的位置??梢?jiàn),w 求t(i)時(shí),當(dāng)f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)時(shí),便不累加t(j)。這樣就避免了重復(fù)。w 上述算法的時(shí)間復(fù)雜度為O(n2) 凸多邊形三角劃分 w 給定一個(gè)具有N(N50)個(gè)頂點(diǎn)(從1到N編號(hào))的凸多邊形,每個(gè)頂點(diǎn)的權(quán)均已知。問(wèn)如何把這個(gè)凸多邊
7、形劃分成N-2個(gè)互不相交的三角形,使得這些三角形頂點(diǎn)的權(quán)的乘積之和最?。縲 輸入文件:第一行 頂點(diǎn)數(shù)Nw 第二行 N個(gè)頂點(diǎn)(從1到N)的權(quán)值w 輸出格式:最小的和的值w 各三角形組成的方式w 輸入示例:5w 122 123 245 231 w 輸出示例:The minimum is :12214884w The formation of 3 triangle:w 3 4 5, 1 5 3, 1 2 3 分析w 設(shè)FI,J(IJ)表示從頂點(diǎn)I到頂點(diǎn)J的凸多邊形三角剖分后所得到的最大乘積,我們可以得到下面的動(dòng)態(tài)轉(zhuǎn)移方程:w FI,J=MinFI,K+FK,J+SI*SJ*SK (0IKJ=N)w
8、初始條件:F1,2=0w 目標(biāo)狀態(tài):F1,Nw 但我們可以發(fā)現(xiàn),由于這里為乘積之和,在輸入數(shù)據(jù)較大時(shí)有可能超過(guò)長(zhǎng)整形范圍,所以還需用高精度計(jì)算 系統(tǒng)可靠性 w 一個(gè)系統(tǒng)由若干部件串聯(lián)而成,只要有一個(gè)部件故障,系統(tǒng)就不能正常運(yùn)行,為提高系統(tǒng)的可靠性,每一部件都裝有備用件,一旦原部件故障,備用件就自動(dòng)進(jìn)入系統(tǒng)。顯然備用件越多,系統(tǒng)可靠性越高,但費(fèi)用也越大,那么在一定總費(fèi)用限制下,系統(tǒng)的最高可靠性等于多少?w 給定一些系統(tǒng)備用件的單價(jià)Ck,以及當(dāng)用Mk個(gè)此備用件時(shí)部件的正常工作概率Pk(Mk),總費(fèi)用上限C。求系統(tǒng)可能的最高可靠性。 w 輸入文件格式:第一行:n C第二行:C1 P1(0) P1(1
9、) P1(X1) (0=X1=C/Ck) 第 n 行:Cn Pn(0) Pn(1) Pn(Xn) (0=Xn=C/Cn)分析w 例:輸入:2 20 3 0 .6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.8 0.9 0.95 輸出:0.6375w 設(shè)FI,money表示將money的資金用到前I項(xiàng)備用件中去的最大可靠性,則有w FI,money = maxFI-1 ,moneyk*CostI *PI,k w (0=I=n,0=K= money div Cost(I) )w 初始: F0,0=0w 目標(biāo): Fn,C快餐問(wèn)題 w Peter最近在R市開(kāi)
10、了一家快餐店,為了招攬顧客,該快餐店準(zhǔn)備推出一種套餐,該套餐由A個(gè)漢堡,B個(gè)薯?xiàng)l和C個(gè)飲料組成。價(jià)格便宜。為了提高產(chǎn)量,Peter從著名的麥當(dāng)勞公司引進(jìn)了N條生產(chǎn)線。所有的生產(chǎn)線都可以生產(chǎn)漢堡,薯?xiàng)l和飲料,由于每條生產(chǎn)線每天所能提供的生產(chǎn)時(shí)間是有限的、不同的,而漢堡,薯?xiàng)l和飲料的單位生產(chǎn)時(shí)間又不同。這使得Peter很為難,不知道如何安排生產(chǎn)才能使一天中生產(chǎn)的套餐產(chǎn)量最大。請(qǐng)你編一程序,計(jì)算一天中套餐的最大生產(chǎn)量。為簡(jiǎn)單起見(jiàn),假設(shè)漢堡、薯?xiàng)l和飲料的日產(chǎn)量不超過(guò)100個(gè)。w 輸入:第一行為三個(gè)不超過(guò)100的正整數(shù)A、B、C中間以一個(gè)空格分開(kāi)。第二行為3個(gè)不超過(guò)100的正整數(shù)p1,p2,p3分別為漢
11、堡,薯?xiàng)l和飲料的單位生產(chǎn)耗時(shí)。中間以一個(gè)空格分開(kāi)。第三行為N(0=0=10),第四行為N個(gè)不超過(guò)10000的正整數(shù),分別為各條生產(chǎn)流水線每天提供的生產(chǎn)時(shí)間,中間以一個(gè)空格分開(kāi)。w 輸出:每天套餐的最大產(chǎn)量。 分析w 本題是一個(gè)非常典型的資源分配問(wèn)題。由于每條生產(chǎn)線的生產(chǎn)是相互獨(dú)立,不互相影響的,所以此題可以以生產(chǎn)線為階段用動(dòng)態(tài)規(guī)劃求解。w 狀態(tài)表示:用pi,j,k表示前i條生產(chǎn)線生產(chǎn)j個(gè)漢堡,k個(gè)薯?xiàng)l的情況下最多可生產(chǎn)飲料的個(gè)數(shù)。w 用ri,j,k表示第i條生產(chǎn)線生產(chǎn)j個(gè)漢堡,k個(gè)薯?xiàng)l的情況下最多可生產(chǎn)飲料的個(gè)數(shù)。w 態(tài)轉(zhuǎn)移方程 : pi,j,k = Maxpi-1,j1,k1+ri,j-j1
12、,k-k1 ( 0=j1=j=100,0=k1=k=100, 且(j-j1)*p1+(k-k1)*p2=Ti-第i條生產(chǎn)線的生產(chǎn)時(shí)間 )w ri,j-j1,k-k1=(Ti-(j-j1)*p1+(k-k1)*p2) div p3 ;w 此算法的時(shí)間復(fù)雜度為O(N*1004), 優(yōu)化w 在本題中,可以在動(dòng)態(tài)規(guī)劃方法中加入了貪心算法思想:即首先計(jì)算出每天生產(chǎn)套數(shù)的上限值(由A,B,C計(jì)算,即min100 div A,100 div B,100 div c),接著,用貪心法計(jì)算出這N條流水線可以生產(chǎn)的套數(shù),并與上限比較,大于則輸出上限值并退出,否則再調(diào)用動(dòng)態(tài)規(guī)劃;同時(shí),在運(yùn)行動(dòng)態(tài)規(guī)劃的過(guò)程中,也可以
13、每完成一階段工作便與上限值進(jìn)行比較,這樣以來(lái),便可望在動(dòng)態(tài)規(guī)劃完成前提前結(jié)束程序。其算法設(shè)計(jì)為:w S1:讀入數(shù)據(jù)。w S2:貪心求上限并計(jì)算出一可行解,判斷是否需進(jìn)行下一步。w S3:動(dòng)態(tài)規(guī)劃求解。w S4:輸出。其他優(yōu)化方法w 1.存儲(chǔ)結(jié)構(gòu):由于每一階段狀態(tài)只與上一階段狀態(tài)有關(guān),所以我們可以只用兩個(gè)100*100的數(shù)組滾動(dòng)實(shí)現(xiàn)。但考慮到滾動(dòng)是有大量的賦值,可以改進(jìn)為動(dòng)態(tài)數(shù)組,每次交換時(shí)只需交換指針即可,這樣比原來(lái)數(shù)組間賦值要快。w 2.減少循環(huán)次數(shù):在計(jì)算每一階段狀態(tài)過(guò)程中無(wú)疑要用到4重循環(huán),我們可以這樣修改每一重循環(huán)的起始值和終數(shù),其中q1,q2為A,B上限值。w 原起始值 改進(jìn)后的起始
14、值wfor i:=1 to n do for i:=1 to n do wfor j:=0 to toti div p1 do for j:=0 to min(q1,toti div p1) dowfor k:=0 to (toti-p1*j) div p2 do for k:=0 to min(q2,(toti-p1*j)div p2) dowfor j1:=0 to j do for j1 := max(0,j-ti div p1) to min(j,toti-1 div p1) dow for k1 := 0 to k do for k1:=max(0,k-(ti-(j-j1)*p1)
15、div p2) to min(k,(toti-1-p1*j1)div p2) do 石子合并 w 在一園形操場(chǎng)四周擺放N堆石子(N100),現(xiàn)要將石子有次序地合并成一堆.規(guī)定每次只能選相臨的兩堆合并成一堆,并將新的一堆的石子數(shù),記為該次合并的得分。編一程序,由文件讀入堆數(shù)N及每堆石子數(shù)(20),(1)選擇一種合并石子的方案,使得做N-1次合并,得分的總和最少 (2) 選擇一種合并石子的方案,使得做N-1次合并,得分的總和最大w 輸入數(shù)據(jù): 第一行為石子堆數(shù)N; 第二行為每堆石子數(shù),每?jī)蓚€(gè)數(shù)之間用一空格分隔.w 輸出數(shù)據(jù) :從第1至第N行為得分最小的合并方案. 第N+1行為空行.從N+2到2N+
16、1行是得分最大的合并方案. 示例貪心法 N=5 石子數(shù)分別為3 4 6 5 4 2。用貪心法的合并過(guò)程如下:第一次 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然而仔細(xì)琢磨后,發(fā)現(xiàn)更好的方案:第一次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ò)誤的。 動(dòng)態(tài)規(guī)劃 w 用datai,j表示將從第i顆石子開(kāi)始的接下來(lái)j顆石子合并所得的分值,w maxi,j
17、表示將從第i顆石子開(kāi)始的接下來(lái)j顆石子合并可能的最大值,那么:w maxi,j = max(maxi, k + maxi + k, j k + datai,k + datai+k, jk) (2=k=j)w maxi,1 = 0w 同樣的,我們用mini,j表示將第從第i顆石子開(kāi)始的接下來(lái)j顆石子合并所得的最小值,可以得到類似的方程:w mini,j = min(mini, k + mini + k, j k + datai,k + datai+k, j k) (0=k=j)w mini,0 = 0w 這樣,我們完美地解決了這道題。時(shí)間復(fù)雜度也是O(n2)。積木游戲 w 一種積木游戲,游戲者有
18、N塊編號(hào)依次為1,2,N的長(zhǎng)方體積木。第I塊積木通過(guò)同一頂點(diǎn)三條邊的長(zhǎng)度分別為ai,bi,ci(i=1,2,N),1 從N塊積木中選出若干塊,并將他們摞成M(1= M = N)根柱子,編號(hào)依次為1,2,M,要求第k根柱子的任意一塊積木的編號(hào)都必須大于第K-1根柱子任意一塊積木的編號(hào)(2=K=n),x,y是上面一塊積木接觸面的兩條邊(x=y),則一定滿足m.=x和n=y;w 下面的積木的編號(hào)要小于上面的積木的編號(hào)。w 請(qǐng)你編一程序,尋找一種游戲方案,使得所有能摞成的M根柱子的高度之和最大。積木游戲w 輸入數(shù)據(jù):w 文件的第一行是兩個(gè)正整數(shù)N和M(1= M = N =100),分別表示積木總數(shù)和要
19、求摞成的柱子數(shù)。這兩個(gè)數(shù)之間用一個(gè)空格符隔開(kāi)。接下來(lái)的N行是編號(hào)從1到N個(gè)積木的尺寸,每行有三個(gè)1至500之間的整數(shù),分別表示該積木三條邊的長(zhǎng)度。同一行相鄰兩個(gè)數(shù)之間用一個(gè)空格符隔開(kāi)。w 輸出數(shù)據(jù):w 文件只有一行,是一個(gè)整數(shù),表示所求得的游戲方案中M根柱子的高度之和 分析w 設(shè)(1) fi,j,k表示以第i塊積木的第k面為第j根柱子的頂面的最優(yōu)方案的高度總和; (2)blocki,k 記錄每個(gè)積木的三條邊信息(blocki,4:=blocki,1; blocki,5:=blocki,2)。其中blocki,j+2表示當(dāng)把第i塊積木的第j面朝上時(shí)所對(duì)應(yīng)的高,即所增加的高度;(3)cani,k,
20、p,kc表示第I塊積木以其第k面朝上,第p塊積木以第kc面朝上時(shí),能否將積木I放在積木p的上面。1表示能,0表示不能。對(duì)于fi,j,k, 有兩種可能: 1. 除去第I塊積木,第j根柱子的最上面的積木為編號(hào)為p的,若第p塊積木以第kc面朝上,必須保證當(dāng)?shù)贗塊積木以k面朝上時(shí)能夠被放在上面,即cani,k,p,kc=1; 2. 第i塊積木是第j根柱子的第一塊積木,第j-1根柱子的最上面為第p塊積木,則此時(shí)第p塊積木可以以任意一面朝上。則有:動(dòng)態(tài)規(guī)劃)31, 11 (2, 1,max) 1, 31 , 11 (2,maxmax,kcipjiblockkcjpfkcpkicankcipjiblockk
21、cjpfkjif且w 邊界條件:w f1,1,1:=block1,1,3; f1,1,2:=block1,1,4; f1,1,3:=block1,1,5;w fi,0,k:=0; (1= i = n, 1= k = 3);w 時(shí)間復(fù)雜度為O(n2*m) 免費(fèi)餡餅 w SERKOI最新推出了一種叫做“免費(fèi)餡餅”的游戲。w 游戲在一個(gè)舞臺(tái)上進(jìn)行。舞臺(tái)的寬度為W格,天幕的高度為H格,游戲者占一格。開(kāi)始時(shí),游戲者站在舞臺(tái)的正中央正中央,手里拿著一個(gè)托盤(pán)。w 游戲開(kāi)始后,從舞臺(tái)天幕頂端的格子中不斷出現(xiàn)餡餅并垂直下落。游戲者左右移動(dòng)去接餡餅。游戲者每秒可以向左或右移動(dòng)一格或兩格,也可以站在愿地不動(dòng)。w 餡
22、餅有很多種,游戲者事先根據(jù)自己的口味,對(duì)各種餡餅依次打了分。同時(shí)在8-308電腦的遙控下,各種餡餅下落的速度也是不一樣的,下落速度以格/秒為單位。當(dāng)餡餅在某一秒末恰好恰好到達(dá)游戲者所在的格子中,游戲者就收集到了這塊餡餅。w 寫(xiě)一個(gè)程序,幫助我們的游戲者收集餡餅,使得收集的餡餅的分?jǐn)?shù)之和最大。免費(fèi)餡餅w 輸入數(shù)據(jù):輸入文件的第一行是用空格分開(kāi)的兩個(gè)正整數(shù),分別給出了舞臺(tái)的寬度W(199之間的奇數(shù))和高度H(1 100之間的整數(shù))。w 接下來(lái)依餡餅的初始下落時(shí)間順序給出了一塊餡餅信息。由四個(gè)正整數(shù)組成,分別表示了餡餅的初始下落時(shí)刻(0 1000秒),水平位置、下落速度(1 100)以及分值。游戲開(kāi)
23、始時(shí)刻為0。從1開(kāi)始自左向右依次對(duì)水平方向的每格編號(hào)。w 輸出數(shù)據(jù):輸出文件的第一行給出了一個(gè)正整數(shù),表示你的程序所收集到的最大分?jǐn)?shù)之和。分析w 我們將問(wèn)題中的餡餅信息用一個(gè)表格存儲(chǔ)。表格的第I行第J列表示的是游戲者在第I秒到達(dá)第J列所能取得的分值。那么問(wèn)題便變成了一個(gè)類似數(shù)字三角形的問(wèn)題:從表格的第一行開(kāi)始往下走,每次只能向左或右移動(dòng)一格或兩格,或不移動(dòng)走到下一行。怎樣走才能得到最大的分值。w 因此,我們很容易想到用動(dòng)態(tài)規(guī)劃求解。w FI,J表示游戲進(jìn)行到第表示游戲進(jìn)行到第I秒,這時(shí)游戲者站在第秒,這時(shí)游戲者站在第J列時(shí)列時(shí)所能得到的最大分值。那么動(dòng)態(tài)轉(zhuǎn)移方程為:所能得到的最大分值。那么動(dòng)態(tài)
24、轉(zhuǎn)移方程為: FI,J = Max FI-1,K + 餡餅的分值餡餅的分值 ( J-2=K=J+2 )商店購(gòu)物 某商店中每種商品都有一個(gè)價(jià)格。例如,一朵花的價(jià)格是2 ICU(ICU 是信息學(xué)競(jìng)賽的貨幣的單位);一個(gè)花瓶的價(jià)格是5 ICU。為了吸引更多的顧客,商店提供了特殊優(yōu)惠價(jià)。 特殊優(yōu)惠商品是把一種或幾種商品分成一組。并降價(jià)銷售。例如:3朵花的價(jià)格不是6而是5 ICU ;2個(gè)花瓶加1朵花是10 ICU不是12 ICU。 編一個(gè)程序,計(jì)算某個(gè)顧客所購(gòu)商品應(yīng)付的費(fèi)用。要充分利用優(yōu)惠價(jià)以使顧客付款最小。請(qǐng)注意,你不能變更顧客所購(gòu)商品的種類及數(shù)量,即使增加某些商品會(huì)使付款總數(shù)減小也不允許你作出任何變
25、更。假定各種商品價(jià)格用優(yōu)惠價(jià)如上所述,并且某顧客購(gòu)買物品為:3朵花和2個(gè)花瓶。那么顧客應(yīng)付款為14 ICU因?yàn)? 1朵花加2個(gè)花瓶: 優(yōu)惠價(jià):10 ICU 2朵花 正常價(jià): 4 ICU商店購(gòu)物輸入數(shù)據(jù) 第一個(gè)文件INPUTTXT的格式為:第一行是一個(gè)數(shù)字B(0B5),表示所購(gòu)商品種類數(shù)。下面共B行,每行中含3個(gè)數(shù)C,K,P。C 代表商品的編碼(每種商品有一個(gè)唯一的編碼),1C999。K代表該種商品購(gòu)買總數(shù),1K5。P 是該種商品的正常單價(jià)(每件商品的價(jià)格),1P999。請(qǐng)注意,購(gòu)物筐中最多可放5*525件商品。第二個(gè)文件OFFERTXT的格式為:第一行是一個(gè)數(shù)字S(0S99),表示共有S種優(yōu)惠
26、。下面共S行,每一行描述一種優(yōu)惠商品的組合中商品的種類。下面接著是幾個(gè)數(shù)字對(duì)(C,K),其中C代表商品編碼,1C9 99。K代表該種商品在此組合中的數(shù)量,1K5。本行最后一個(gè)數(shù)字P(1 P9999)代表此商品組合的優(yōu)惠價(jià)。當(dāng)然, 優(yōu)惠價(jià)要低于該組合中商品正常價(jià)之總和。輸出數(shù)據(jù) 在輸出文件OUTPUTTXT中寫(xiě) 一個(gè)數(shù)字(占一行), 該數(shù)字表示顧客所購(gòu)商品(輸入文件指明所購(gòu)商品)應(yīng)付的最低貨款。 分析w 由于動(dòng)態(tài)規(guī)劃要滿足無(wú)后效性和最優(yōu)化原理,所以我們來(lái)分析此題是否滿足以上兩點(diǎn)。首先確定狀態(tài),商品不超過(guò)5種,而每種采購(gòu)的數(shù)量又不超過(guò)5,那么用一個(gè)五元組來(lái)表示第i種商品買Ai的最小費(fèi)用。w F F
27、(A A1 1,A A2 2,A A3 3,A A4 4,A A5 5) (1 1)w 考慮這個(gè)狀態(tài)的由來(lái),當(dāng)然,我們不用優(yōu)惠商品也可以買,顯然這樣不是最優(yōu)。于是如果我們能夠使用第i條商品組合的話,狀態(tài)就b變?yōu)榱耍簑 F F(A A1 1-S-SI1I1,A A2 2-S-SI2I2,A A3 3-S-SI3I3,A A4 4-S-SI4I4,A A5 5-S-SI5I5) (2 2)w 這樣的話,狀態(tài)1的費(fèi)用為狀態(tài)2的費(fèi)用加上Si的費(fèi)用,而狀態(tài)2的費(fèi)用必須最低(很顯然,用反證法即可),同時(shí),我們也不管狀態(tài)2是如何來(lái)的(因?yàn)槊恳粋€(gè)優(yōu)惠商品組合的使用是沒(méi)有限制的),所以本題既滿足無(wú)后效性,又符合
28、最優(yōu)化原理,同時(shí)還有大量重疊子問(wèn)題產(chǎn)生,動(dòng)態(tài)規(guī)劃解決此題是最好不過(guò)了。狀態(tài)轉(zhuǎn)移方程w F a, b, c, d, e = MinFa-Si1,b-Si2,c-Si3,d-Si4,e-Si5+SaleCostSi (0=i=S, 0=a, b, c, d, e=5)初始條件為: F a, b, c, d, e = Cost1*a+Cost2*b+Cost3*c+Cost4*d+Cost5*e添括號(hào)問(wèn)題 w 有一個(gè)由數(shù)字1,2,. ,9組成的數(shù)字串(長(zhǎng)度不超過(guò)200),問(wèn)如何將M(M=20)個(gè)加號(hào)(+)插入到這個(gè)數(shù)字串中,使所形成的算術(shù)表達(dá)式的值最小。請(qǐng)編一個(gè)程序解決這個(gè)問(wèn)題。w 注意:w 加號(hào)不
29、能加在數(shù)字串的最前面或最末尾,也不應(yīng)有兩個(gè)或兩個(gè)以上的加號(hào)相鄰。w M保證小于數(shù)字串的長(zhǎng)度。w 例如:數(shù)字串79846,若需要加入兩個(gè)加號(hào),則最佳方案為79+8+46,算術(shù)表達(dá)式的值133。w 輸入格式w 從鍵盤(pán)讀入輸入文件名。數(shù)字串在輸入文件的第一行行首(數(shù)字串中間無(wú)空格且不折行),的值在輸入文件的第二行行首。w 輸出格式w 在屏幕上輸出所求得的最小和的精確值。分析w 考慮到數(shù)據(jù)的規(guī)模超過(guò)了長(zhǎng)整型,我們注意在解題過(guò)程中采用高精度算法.w 規(guī)劃方程:w FI,J = MIN FI-1,K + NUMK+1,J (I-1=K=J-1)w 邊界值:F0,I := NUM1,I ;w FI,J表示前
30、J個(gè)數(shù)字中添上I個(gè)加號(hào)后得到的最小值。w NUMI,J表示數(shù)字串第I位到第J位的數(shù)w 上述問(wèn)題的每一步,都只與上一步有關(guān)。因此可以采用滾動(dòng)數(shù)組w 程序的時(shí)間效率約為 20 * 200 * 200 最長(zhǎng)前綴 w 一些生物體的復(fù)雜結(jié)構(gòu)可以用其基元的序列表示,而一個(gè)基元用一個(gè)大寫(xiě)英文字符串表示。生物學(xué)家的一個(gè)問(wèn)題就是一個(gè)這樣的長(zhǎng)序列分解為基元(字符串)的序列。對(duì)于給定的基元集合P,如果可以從中選出N個(gè)基元P1,P2,P3,.,Pn,將它們各自對(duì)應(yīng)的字符串依次連接后得到一個(gè)字符串S,稱S可以由基元集合P構(gòu)成。在從P中挑選基元時(shí),一個(gè)基元可以使用多次,也可不用。例如,序列 ABABACABAAB 可以由
31、基元集合A,AB,BA,CA,BBC 構(gòu)成。w 字符串的前K個(gè)字符為該字符串的前綴,其長(zhǎng)度為K。請(qǐng)寫(xiě)一個(gè)程序,對(duì)于輸入的基元集合P和字符串T,求出一個(gè)可以由基元集合P構(gòu)成的字符串T的前綴,要求該前綴的長(zhǎng)度盡可能長(zhǎng),輸出其長(zhǎng)度。最長(zhǎng)前綴w 輸入數(shù)據(jù):有兩個(gè)輸入文件 INPUT.TXT,DATA.TXTINPUT.TXT 的第一行是基元集合P中的基元數(shù)目N(1=N=100),隨后有2N行,每?jī)尚忻枋鲆粋€(gè)基元,第一行為該基元的長(zhǎng)度L(1=L=20)。隨后一行是一個(gè)長(zhǎng)度為L(zhǎng)的大寫(xiě)英文字符串,表示該基元。每個(gè)基元互不相同。DATA.TXT 描述要處理的字符串T,每一行行首有一個(gè)大寫(xiě)字母,最后一行是一個(gè)字
32、符.,表示字符串結(jié)束。T的長(zhǎng)度最小為1,最大不超過(guò)500000。w 輸出數(shù)據(jù):OUTPUT.TXT。只有一行,一個(gè)數(shù)字,表示可以由P構(gòu)成的T的最長(zhǎng)前綴的長(zhǎng)度。分析w 本題可以簡(jiǎn)述為: 從一個(gè)集合里選出若干個(gè)基元,使其組成字符串T的前綴,求最長(zhǎng)前綴的長(zhǎng)度. w 對(duì)于T的每個(gè)字符,其狀態(tài)可分為兩種:w 在此之前的所有字符(包括本身)可匹配(true)、不可匹配(false)。(可匹配是指可以由集合里的基元組成)w 用Fi表示第i個(gè)字符的狀態(tài),finda,b表示由第a至b位的字符組成的子串是否存在于集合中,則,F(xiàn)i = Fi or (Fk and findk+1,j) (0=k=i-1)w 初始條件
33、: if i=0 then Fi:= true else Fi:= false分析w 由于T的長(zhǎng)度最大達(dá)500000,無(wú)法存放所有狀態(tài),但集合里基元長(zhǎng)度不超過(guò)20,因此可只保留當(dāng)前20位字符與狀態(tài)。當(dāng)20位字符都不可以匹配時(shí),停止運(yùn)算,最后一個(gè)狀態(tài)為true的字符的位置,即為所求。w 為了便于操作,可用字符串表示狀態(tài),0表false、1表true.w 為了便于查找,可將基元按長(zhǎng)度存儲(chǔ)。w 形如:si,j,表示長(zhǎng)度為 i的第 j個(gè)基元。w 亦可采用樹(shù)的結(jié)構(gòu)存儲(chǔ)基元,構(gòu)造一種多叉樹(shù)(最多26叉),查找時(shí)順著相應(yīng)字母,定位到相應(yīng)分支。這樣速度要快些,但程序更復(fù)雜。大家可以比較一下。w 按樹(shù)結(jié)構(gòu)算,時(shí)
34、間復(fù)雜度為O(500000*L*L),勉強(qiáng)可以承受。多邊形 w 多角形是一個(gè)單人玩的游戲,開(kāi)始時(shí)有一個(gè)N個(gè)頂點(diǎn)的多邊形。如圖,這里N N=4。每個(gè)頂點(diǎn)有一個(gè)整數(shù)標(biāo)記,每條邊上有一個(gè)“+”號(hào)或“*”號(hào)。邊從1編號(hào)到N。 第一步,一條邊被拿走;隨后各步包括如下:w 選擇一條邊E和連接著E的兩個(gè)頂點(diǎn)V V1和 V V2;w 得到一個(gè)新的頂點(diǎn),標(biāo)記為V1與V2通過(guò)邊E E上的運(yùn)算符運(yùn)算的結(jié)果。w 最后,游戲中沒(méi)有邊,游戲的得分為僅剩余的一個(gè)頂點(diǎn)的值。 -7425+*1234+*樣例 -7 4 2 5 + * 1 2 4 + 42+*24-24+2-40寫(xiě)一個(gè)程序,對(duì)于給定一個(gè)多邊形,計(jì)算出可能的最高得
35、分,并且列出得到這個(gè)分?jǐn)?shù)的過(guò)程。分析 分析w 我們?cè)谶@條“線”當(dāng)中繼續(xù)刪邊,并且每次刪邊都使被刪邊兩旁的點(diǎn)按邊上的操作符合并,圖五。這樣進(jìn)行了n-1次刪邊操作后,“線”變成了一個(gè)點(diǎn)。我們的目的,就是安排刪邊的順序,使最后的點(diǎn)上的數(shù)盡可能的大。w 拿到題目之后,我們馬上可以想到用枚舉法枚舉刪邊的先后順序。但邊數(shù)最大可以達(dá)到50,枚舉的復(fù)雜將會(huì)有50!。因此枚舉算法馬上被排除了。 w 對(duì)最優(yōu)化問(wèn)題的求解,我們往往可以使用動(dòng)態(tài)規(guī)劃來(lái)解決。這道題是不是可以使用動(dòng)態(tài)規(guī)劃呢?w 我們先對(duì)題目進(jìn)行一些變化原題中頂點(diǎn)上的數(shù)可以為負(fù)數(shù),現(xiàn)在我們規(guī)定這個(gè)數(shù)一定大于等于0;原題中邊可以為乘號(hào),現(xiàn)在我們規(guī)定只能為加號(hào)
36、。w 題意改變后,我們想到了什么?對(duì)!“石子合并”。動(dòng)態(tài)規(guī)劃w 我們先枚舉第一次刪掉的邊,然后再對(duì)每種狀態(tài)進(jìn)行動(dòng)態(tài)規(guī)劃求最大值 w 用f(I,j)表示從j開(kāi)始,進(jìn)行i次刪邊操作所能得到的最大值,num(i)表示第i個(gè)頂點(diǎn)上的數(shù),那么:)(), 1 (),(),(max),(11inumifkikjfikfjifik進(jìn)一步分析w 現(xiàn)在我們來(lái)考慮加入乘號(hào)后的情況。w 由于所有的頂點(diǎn)上的數(shù)都為非負(fù)數(shù),因此即使有了乘法,函數(shù)f的無(wú)后效性并不被破壞。我們可以在前一方程的基礎(chǔ)上進(jìn)行改進(jìn):(opr(i)表示第i條邊上的操作符) )(), 1 (),(max),(11inumifkikjikactjifiky
37、2)f(x2,*y1)f(x1, - 1)-opr(x2y2)f(x2,y1)f(x1, 1)-opr(x2)2, 2, 1, 1(時(shí),當(dāng)時(shí),當(dāng)yxyxAct進(jìn)一步分析w 最后,我們?cè)试S頂點(diǎn)上出現(xiàn)負(fù)數(shù)。以前的方程還適不適用呢?w 這個(gè)例子的最優(yōu)解應(yīng)該是(3+2)*(-9)*(-5)=250,然而如果沿用以前的方程,得出的解將是(-10)*3+2)*(-5)=140。為什么?w 我們發(fā)現(xiàn),兩個(gè)負(fù)數(shù)的積為正數(shù);這兩個(gè)負(fù)數(shù)越小,它們的積越大。我們從前的方程,只是盡量使得局部解最大,而從來(lái)沒(méi)有想過(guò)負(fù)數(shù)的積為正數(shù)這個(gè)問(wèn)題。 -932-5*圖六+最終?w 我們引入函數(shù)fmin和fmax來(lái)解決這個(gè)問(wèn)題。fm
38、ax(I,j) 表示從j開(kāi)始,進(jìn)行i次刪邊操作所能得到的最大值,fmin(I,j) 表示從j開(kāi)始,進(jìn)行i次刪邊操作所能得到的最小值 。)(), 1 (),min(min),min(),max(max),max(1111inumifkikjikactjifkikjikactjifikik函數(shù)actmax與actmin的構(gòu)造是十分關(guān)鍵的。首先討論actmax(x1,y1,x2,y2)的構(gòu)造:當(dāng)opr(x2-1)=+時(shí),actmax=fmax(x1,y1)+fmax(x2,y2)當(dāng)opr(x2-1)=*時(shí), actmax=max(fmax(x1,y1)*fmax(x2,y2),fmin(x1,y1)
39、*fmin(x2,y2) 完美解決w 接下來(lái)討論actmin(x1,y1,x2,y2)的構(gòu)造:w 當(dāng)opr(x2-1)=+時(shí),actmin=fmin(x1,y1)+fmin(x2,y2)w opr(x2-1)=*時(shí), actmin=min(fmax(x1,y1)*fmin(x2,y2),fmin(x1,y1)*fmax(x2,y2)w 到此為止,整個(gè)問(wèn)題圓滿解決了。算法的空間復(fù)雜度為n2,算法時(shí)間復(fù)雜度為n4(先要枚舉每一條邊,然后再用復(fù)雜度為n3的動(dòng)態(tài)規(guī)劃解決)。選課 w 大學(xué)里實(shí)行學(xué)分。每門(mén)課程都有一定的學(xué)分,學(xué)生只要選修了這門(mén)課并考核通過(guò)就能獲得相應(yīng)的學(xué)分。學(xué)生最后的學(xué)分是他選修的各門(mén)課
40、的學(xué)分的總和。w 每個(gè)學(xué)生都要選擇規(guī)定數(shù)量的課程。其中有些課程可以直接選修,有些課程需要一定的基礎(chǔ)知識(shí),必須在選了其它的一些課程的基礎(chǔ)上才能選修。例如,數(shù)據(jù)結(jié)構(gòu)必須在選修了高級(jí)語(yǔ)言程序設(shè)計(jì)之后才能選修。我們稱高級(jí)語(yǔ)言程序設(shè)計(jì)是數(shù)據(jù)結(jié)構(gòu)的先修課。每門(mén)課的直接先修課最多只有一門(mén)。兩門(mén)課也可能存在相同的先修課。為便于表述每門(mén)課都有一個(gè)課號(hào),課號(hào)依次為1,2,3,。 選課w 下面舉例說(shuō)明w 上例中1是2的先修課,即如果要選修2,則1必定已被選過(guò)。同樣,如果要選修3,那么1和2都一定已被選修過(guò)。w 學(xué)生不可能學(xué)完大學(xué)所開(kāi)設(shè)的所有課程,因此必須在入學(xué)時(shí)選定自己要學(xué)的課程。每個(gè)學(xué)生可選課程的總數(shù)是給定的?,F(xiàn)
41、在請(qǐng)你找出一種選課方案,使得你能得到學(xué)分最多,并且必須滿足先修課優(yōu)先的原則。假定課程之間不存在時(shí)間上的沖突。選課w 輸入輸入 輸入文件的第一行包括兩個(gè)正整數(shù)M、N(中間用一個(gè)空格隔開(kāi))其中M表示待選課程總數(shù)(1M1000),N表示學(xué)生可以選的課程總數(shù)(1NM)。 以下M行每行代表一門(mén)課,課號(hào)依次為1,2M。每行有兩個(gè)數(shù)(用一個(gè)空格隔開(kāi)),第一個(gè)數(shù)為這門(mén)課的先修課的課號(hào)(若不存在先修課則該項(xiàng)為0),第二個(gè)數(shù)為這門(mén)課的學(xué)分。學(xué)分是不超過(guò)10的正整數(shù)。w 輸出輸出 輸出文件第一行只有一個(gè)數(shù),即實(shí)際所選課程的學(xué)分總數(shù)。以下N行每行有一個(gè)數(shù),表示學(xué)生所選課程的課號(hào)。樣例分析7 42 20 10 42 1
42、7 17 62 2表12157346圖202157346圖1分析w 們可以選取某一個(gè)點(diǎn)k的條件只是它的父節(jié)點(diǎn)已經(jīng)被選取或者它自己為根節(jié)點(diǎn);而且我們不論如(何取k的子孫節(jié)點(diǎn),都不會(huì)影響到它父節(jié)點(diǎn)的選取情況,這滿足無(wú)后效性原則。于是我們猜測(cè),是不是可以以節(jié)點(diǎn)為階段,進(jìn)行動(dòng)態(tài)規(guī)劃呢?w 我們用函數(shù)f(I,j)表示以第i個(gè)節(jié)點(diǎn)為父節(jié)點(diǎn),取j個(gè)子節(jié)點(diǎn)的最佳代價(jià),則:w 可是如此規(guī)劃,其效率與搜索毫無(wú)差別,雖然我們可以再次用動(dòng)態(tài)規(guī)劃來(lái)使它的復(fù)雜度變?yōu)槠椒郊?jí),但顯得過(guò)于麻煩。 jnchnchjnchnchnchjnchnichnchnchjchinchinchifnchchfnchchfjif1111221
43、13) 1(21),()2, 2()1, 1(max),(改造樹(shù)w 轉(zhuǎn)變?yōu)槎鏄?shù)。如果兩節(jié)點(diǎn)a,b同為兄弟,則將b設(shè)為a的右節(jié)點(diǎn);如果節(jié)點(diǎn)b是節(jié)點(diǎn)a的兒子,則將節(jié)點(diǎn)b設(shè)為節(jié)點(diǎn)a的左節(jié)點(diǎn)。樹(shù)改造完成后如圖3。w 我們用函數(shù)f(I,j)表示以第i個(gè)節(jié)點(diǎn)為父節(jié)點(diǎn),取j個(gè)子節(jié)點(diǎn)的最佳代價(jià),這和前一個(gè)函數(shù)表示的意義是一致的,但方程有了很大的改變:023014765圖3動(dòng)態(tài)規(guī)劃w 1=i=m,1=j=n,0=kj w 這個(gè)方程的時(shí)間復(fù)雜度最大為n3,十分優(yōu)秀了。w 在具體實(shí)現(xiàn)這道題時(shí),我們可以自頂而下,用遞歸進(jìn)行樹(shù)的遍歷求解 max),()1,(),(),(iskjrightcfkleftcfjright
44、cfjifHPC (Winter Camp 2001) 描述抽象為:描述抽象為:A類任務(wù):A1,A2,AmB類任務(wù):B1,B2,BnP個(gè)接點(diǎn):1,2,P在節(jié)點(diǎn)i連續(xù)處理x個(gè)A、B類任務(wù)的時(shí)間 Kia x2、 Kib x2節(jié)點(diǎn)i轉(zhuǎn)入工作狀態(tài)A、B類任務(wù)的啟動(dòng)時(shí)間 Tia, Tib輸入:輸入:1=Na , Nb=60,1=P=20 1=Tia, Tib =1000, 1=Kia, Kib 1p 1 P1的情況:w 第一個(gè)節(jié)點(diǎn)負(fù)責(zé)了i個(gè)任務(wù)A和j個(gè)任務(wù)B,則w 剩下的a i個(gè)任務(wù)A和b j個(gè)任務(wù)B都必須由后p 1個(gè)節(jié)點(diǎn)完成。w 設(shè)f(p, a, b)表示在后p個(gè)節(jié)點(diǎn)上處理a個(gè)A類任務(wù),b個(gè)B類任務(wù)所
45、需的最少時(shí)間。有: f(p, a, b) = min(0ia, 0jb)maxg(i, j), f(p 1, a i, b j) 總結(jié):w 由于計(jì)算f(p)時(shí),只需用到f(p 1)的結(jié)果,故可以使用滾動(dòng)數(shù)組。這樣,計(jì)算過(guò)程中,只需保存ga, gb, g, f(p 1), f(p)這5個(gè)大小為n2的數(shù)組,故空間復(fù)雜度是O(n2)。w 計(jì)算數(shù)組g的復(fù)雜度為O(n3),一共有p個(gè)節(jié)點(diǎn),故時(shí)間復(fù)雜度是O(pn3)。計(jì)算數(shù)組f的復(fù)雜度為O(pn4)。所以,總的時(shí)間復(fù)雜度為O(pn4)。w 在這個(gè)例子中,我們用f來(lái)表示目標(biāo)問(wèn)題。在求f之前,先要求出g,而在求g的時(shí)候,也采用了動(dòng)態(tài)規(guī)劃。我們稱之為多次動(dòng)態(tài)規(guī)
46、劃。很多題目中,動(dòng)態(tài)規(guī)劃并不是單一出現(xiàn)的,但有些例子中,這種多層次的結(jié)構(gòu)并不明顯,下一個(gè)例子將討論這個(gè)問(wèn)題。交叉匹配交叉匹配 描述:兩行正整數(shù)。第一行中有一個(gè)數(shù)和第二行中的一個(gè)數(shù)都為r,將這兩個(gè)數(shù)用線段連起來(lái)。稱這條線段為r匹配線段。例如下圖就顯示了一條3匹配線段和一條2匹配線段。34622137對(duì)于給定的輸入,找到畫(huà)出最多的匹配線段的方式,使得:1)每條a匹配線段恰好和一條b匹配線段相交,且ab,a, b指代任何值,并非特定值。2)不存在兩條線段都從一個(gè)數(shù)出發(fā)。計(jì)算出匹配線段的最多個(gè)數(shù)。分析:w an:存儲(chǔ)第一行的數(shù) bm:存儲(chǔ)第二行的數(shù)w 設(shè) f(i, j):表示如下圖所示的兩行數(shù)據(jù),可以
47、畫(huà)出的最多的匹配線段數(shù)。 a1a2Aib1b2Bj沒(méi)有從ai出發(fā)的匹配線段 解為f(i-1,j)a1a2Aib1b2Bja1a2Aib1b2Bj2. 沒(méi)有從bj出發(fā)的匹配線段 解為f(i,j-1) 3.ai和bj處,各引出一條匹配線段,這時(shí)必須aibj。設(shè)ai = bv,bj = au。從ai向bv,bj向au各引一條匹配線段,這兩條線段必然相交。這種情況的解即為f(u 1, v 1) + 2。 a1a2Au-1b1b2Bu-1Au AiBu Bjiuuajbjvvbiajbiavufjifjifjif112)1, 1()1,(), 1(max),(且且其中該算法的復(fù)雜度:O(nm)2)。優(yōu)化
48、 ?w 從什么地方入手呢?w 是否要改變思路?w 有更好的狀態(tài)轉(zhuǎn)移方程嗎?從問(wèn)題的特性入手!如果存在au = bj,且u u i,則用bj向au的匹配線段,代替bj向au的匹配線段,所得到的解不會(huì)變差。因此,u的選擇是越靠后越好。同理,v的選擇也是越靠后越好。,2) 1, 1() 1,(), 1(max),(uajbiuuuuajbvbiajvvvvbiajbiavufjifjifjif使得且不存在使得且不存在其中a1a2Aub1b2BvAuAiBj對(duì)于確定的i和j,相應(yīng)的u和v的值也是確定的,這些值可以預(yù)先求出。而求法也是利用動(dòng)態(tài)規(guī)劃。設(shè)相應(yīng)u和v的值分別為ui, j和vi, j。 11 1) 1,(),( 11 1), 1(),(iajbjiajbjivjivjbiaijbiajiujiu這樣,原動(dòng)態(tài)轉(zhuǎn)移方程可變?yōu)椋?2) 1),(, 1),() 1,(), 1(max),(jbiajivjiufjifjifjif該算法需要保存f,u,v等數(shù)組,空間復(fù)雜度是O(nm)。計(jì)算f,u,v的時(shí)間復(fù)雜度是O(nm),因此總的時(shí)間復(fù)雜度也還是O(nm)。Codes (IOI 1999) 1. 碼字集合 2. 一個(gè)文本,碼字埋藏在文本之中求文本能覆蓋的碼字長(zhǎng)度之和最大。要求: 所
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年全球及中國(guó)醫(yī)用全自動(dòng)凝血分析儀行業(yè)頭部企業(yè)市場(chǎng)占有率及排名調(diào)研報(bào)告
- 2025年全球及中國(guó)企業(yè)級(jí)機(jī)械硬盤(pán)和固態(tài)硬盤(pán)行業(yè)頭部企業(yè)市場(chǎng)占有率及排名調(diào)研報(bào)告
- 2025-2030全球3D晶體管行業(yè)調(diào)研及趨勢(shì)分析報(bào)告
- 2025-2030全球立式不銹鋼離心泵行業(yè)調(diào)研及趨勢(shì)分析報(bào)告
- 2025-2030全球汽車電池試驗(yàn)箱行業(yè)調(diào)研及趨勢(shì)分析報(bào)告
- 2025年全球及中國(guó)游戲人工智能NPC行業(yè)頭部企業(yè)市場(chǎng)占有率及排名調(diào)研報(bào)告
- 2025-2030全球自動(dòng)藥敏分析儀行業(yè)調(diào)研及趨勢(shì)分析報(bào)告
- 2025年全球及中國(guó)無(wú)線藍(lán)牙肉類溫度計(jì)行業(yè)頭部企業(yè)市場(chǎng)占有率及排名調(diào)研報(bào)告
- 2025年全球及中國(guó)固定橋式坐標(biāo)測(cè)量機(jī)行業(yè)頭部企業(yè)市場(chǎng)占有率及排名調(diào)研報(bào)告
- 2025年全球及中國(guó)萬(wàn)能材料實(shí)驗(yàn)機(jī)行業(yè)頭部企業(yè)市場(chǎng)占有率及排名調(diào)研報(bào)告
- 2025-2030年中國(guó)清真食品行業(yè)運(yùn)行狀況及投資發(fā)展前景預(yù)測(cè)報(bào)告
- 廣東省茂名市電白區(qū)2024-2025學(xué)年七年級(jí)上學(xué)期期末質(zhì)量監(jiān)測(cè)生物學(xué)試卷(含答案)
- 《教育強(qiáng)國(guó)建設(shè)規(guī)劃綱要(2024-2035年)》全文
- 山東省濱州市2024-2025學(xué)年高二上學(xué)期期末地理試題( 含答案)
- 2025年河南洛陽(yáng)市孟津區(qū)引進(jìn)研究生學(xué)歷人才50人歷年高頻重點(diǎn)提升(共500題)附帶答案詳解
- 2025年度軍人軍事秘密保護(hù)保密協(xié)議與信息安全風(fēng)險(xiǎn)評(píng)估合同3篇
- 數(shù)字化轉(zhuǎn)型中的職業(yè)能力重構(gòu)
- 運(yùn)用PDCA降低住院患者跌倒-墜床發(fā)生率
- 2025屆高中數(shù)學(xué)一輪復(fù)習(xí)專練:橢圓(含解析)
- 立春氣象與生活影響模板
- 中國(guó)服裝零售行業(yè)發(fā)展環(huán)境、市場(chǎng)運(yùn)行格局及前景研究報(bào)告-智研咨詢(2025版)
評(píng)論
0/150
提交評(píng)論