網(wǎng)上找的一些算法動(dòng)態(tài)深入

1、第八章動(dòng)態(tài)規(guī)劃第一節(jié)引言在分治法一章中，為了解決一個(gè)大，總是想方設(shè)法把它分成兩個(gè)或多個(gè)更?。蝗缓蠓謩e解決每個(gè)小問(wèn)題；再把各小問(wèn)題的解答組合起來(lái)，即到原問(wèn)題的解答；小問(wèn)題通常與原問(wèn)題本質(zhì)相似，只是規(guī)模小些，一般都可以用遞歸的方法來(lái)解決，如 hanoi塔問(wèn)題和快速排序都是應(yīng)用這種方法的典型例子。然而常常有些問(wèn)題難以用分治法來(lái)求解，當(dāng)把問(wèn)題分解成若干個(gè)子問(wèn)題，使之能夠從這些子問(wèn)題的解得到原問(wèn)題的解時(shí)，子問(wèn)題的數(shù)目太多，這樣，如果把每個(gè)子問(wèn)題再分解，必將得到的子問(wèn)題，以至于最后解決問(wèn)題需要耗費(fèi)指數(shù)時(shí)間。往往在這類問(wèn)題中子問(wèn)題的數(shù)目其實(shí)只有多項(xiàng)式多個(gè)，于是在上述算法中，一定有些子問(wèn)題被重復(fù)計(jì)算了許多次。

2、如果能夠保存已解決的子問(wèn)題的，而在需要時(shí)簡(jiǎn)單查一下，這樣就可以避免大量的重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間的算法。為了實(shí)現(xiàn)上述方法，用一個(gè)數(shù)組來(lái)所有已解決的子問(wèn)題的。無(wú)論子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果存入數(shù)組中，這種方法在程序設(shè)計(jì)中被稱為動(dòng)態(tài)規(guī)劃，請(qǐng)看下面的實(shí)例。例 8_1: 數(shù)字三角形(IOI94)問(wèn)題描述 如下所示為一個(gè)數(shù)字三角形：73824817504 42 6 5請(qǐng)編一個(gè)程序計(jì)算從頂至底的某處的一條路徑，使該路徑所經(jīng)過(guò)的數(shù)字的總和最大。每一步可沿直線向下或右斜線向下走；1三角形行數(shù)100；三角形中的數(shù)字為整數(shù) 0，1，99；輸入輸入文件第一行為一個(gè)自然數(shù)，表示數(shù)字三角形的行

3、數(shù) n，接下來(lái)的 n 行表示一個(gè)數(shù)字三角形。輸出輸出文件僅有一行包含一個(gè)整數(shù)表示要求的最大總和。輸入樣例 573824817504 42 6 5輸出樣例30問(wèn)題分析 假設(shè)從頂至數(shù)字三角形的某一位置的所有路徑中，所經(jīng)過(guò)的數(shù)字的總和最大的那條路徑稱之為該位置的最大路徑。由于問(wèn)題規(guī)定每一步只能沿直線或右斜線向下走，若要走到某一位置，則其前一位置必為其左上方或正上方兩個(gè)位置之一，由此可知，當(dāng)前位置的最優(yōu)路徑必定與其左上方或正上方兩個(gè)位置的最優(yōu)路徑有關(guān)，且來(lái)自于其中更優(yōu)的一個(gè)。可以用一個(gè)兩維數(shù)組a數(shù)字三角形中的數(shù)，aI,j表示數(shù)字三角形中第 I 行第j 列的數(shù)，再用一個(gè)兩維數(shù)組 maxsum每個(gè)位置的最

4、優(yōu)路徑的數(shù)字總和。計(jì)算 maxsum 數(shù)組可以象計(jì)算三角一樣用逐行遞推的方法實(shí)現(xiàn)，具體細(xì)節(jié)請(qǐng)看程序。參考程序Progr8_1(Input, Output)； const maxline=100；var i,j,t,line:eger；a,max:array 1.maxline,1.maxline ofeger；function maxsum(i,j: beginif i=lineeger):eger；then maxsum:=ai,jelse if maxsum(i+1,j)maxsum(i+1,j+1) then maxsum:=maxsum(i+1,j)+ai,jelse maxsum:=

5、maxsum(i+1,j+1)+ai,jend；begin mainwrite(Input number of line(=ai,j+maxi-1,j-1then maxi,j:=ai,j+maxi-1,jelse maxi,j:=ai,j+maxi-1,j-1；maxi,i:=maxi-1,i-1+ai,i end；t:=0；for i:=1 to line doif tmaxline,i then t:=maxline,i；wrin(Theum sum is:,t)end.第二節(jié)動(dòng)態(tài)規(guī)劃的基本剛剛過(guò)動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)方法的一個(gè)例子，現(xiàn)在來(lái)看看什么時(shí)候應(yīng)用這個(gè)方法。從應(yīng)用的角度看，對(duì)一個(gè)具體問(wèn)

6、題在什么樣的情況下需要有一個(gè)動(dòng)態(tài)程序設(shè)計(jì)解？在這一節(jié)里，要介紹適合采用動(dòng)態(tài)程序設(shè)計(jì)方法的最優(yōu)化問(wèn)題中的二個(gè)要素：最優(yōu)結(jié)構(gòu)和重復(fù)子問(wèn)題。還要另一個(gè)稱作化的方法，以充分利用子問(wèn)題的性質(zhì)。一、最優(yōu)結(jié)構(gòu)用動(dòng)態(tài)程序設(shè)計(jì)方法來(lái)解決一個(gè)問(wèn)題的第一步是刻劃一個(gè)最優(yōu)解的結(jié)構(gòu)。說(shuō)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，如果該問(wèn)題的最優(yōu)解中包含了一個(gè)或多個(gè)子問(wèn)題的最優(yōu)解。當(dāng)一個(gè)問(wèn)題呈現(xiàn)出最優(yōu)子結(jié)構(gòu)時(shí)，動(dòng)態(tài)程序設(shè)計(jì)可能就是一個(gè)合適的候選方法了。在例 1 中，發(fā)現(xiàn)數(shù)字三角形問(wèn)題具有最優(yōu)子結(jié)構(gòu)。具體來(lái)說(shuō)，當(dāng)前位置的最優(yōu)路徑必定與其左上方或正上方兩個(gè)位置的最優(yōu)路徑有關(guān)，且來(lái)自于其中更優(yōu)的一個(gè)，即問(wèn)題的最優(yōu)解包含了其中一個(gè)子問(wèn)題的最優(yōu)解

7、。如果把問(wèn)題稍微改變一下：將三角形中的數(shù)字改為-100100 之間的整數(shù)，計(jì)算從頂至底的某處的一條路徑，使該路徑所經(jīng)過(guò)的數(shù)字的總和最接近于零。這個(gè)問(wèn)題就不具有最優(yōu)子結(jié)構(gòu)性質(zhì)了，因?yàn)樽訂?wèn)題最優(yōu)(最接近于零)反而可能造成問(wèn)題的解遠(yuǎn)離零，這樣的反例是不難構(gòu)造的，改變以后顯然就不能用動(dòng)態(tài)規(guī)劃的方法解決。二、子問(wèn)題適合于動(dòng)態(tài)規(guī)劃方法解決的最優(yōu)化問(wèn)題必須具有的第二個(gè)要素是子問(wèn)題空間要較小，也就是用來(lái)問(wèn)題的一個(gè)遞歸算法可反復(fù)地解同樣的子問(wèn)題，而不是產(chǎn)生新的子問(wèn)題，即子問(wèn)題的總數(shù)是問(wèn)題規(guī)模的一個(gè)多項(xiàng)式。當(dāng)一個(gè)遞歸算法不斷地遇到同一問(wèn)題時(shí)，說(shuō)該最優(yōu)化問(wèn)題包含有子問(wèn)題。相反地，適合用分治法解決往往在遞歸的每一步都

8、子問(wèn)題，對(duì)每個(gè)子問(wèn)題只解產(chǎn)生出全新來(lái)，如快速排序算法。動(dòng)態(tài)總是充分得用一次，把解放在一個(gè)數(shù)組中，需要時(shí)直接查看就行。為說(shuō)明子問(wèn)題性質(zhì)，對(duì)數(shù)字三角形問(wèn)題編一個(gè)遞歸算法，該算法的源程序如下：可以看出用遞推的方法對(duì)每個(gè)子問(wèn)題(求 maxsumI,j)只通過(guò)運(yùn)行兩個(gè)程序進(jìn)行對(duì)比，求一次，子問(wèn)題總數(shù)為 O(n*n)，時(shí)間復(fù)雜度也是 O(n*n)。而用遞歸的方法，由于子問(wèn)題，如求 maxsum(I,j)和 maxsum(I,j+1)都要調(diào)用子問(wèn)題 maxsum(I-1,j)，從而造成子問(wèn)題的大量重復(fù)調(diào)用，其運(yùn)行時(shí)間呈指數(shù)增長(zhǎng)，從實(shí)際運(yùn)行時(shí)間看，與分析出的理論值完全符合。三、化動(dòng)態(tài)規(guī)劃算法一般都是用自底向上

9、的遞推來(lái)實(shí)現(xiàn)，具體來(lái)說(shuō)就是從遞歸式的邊界條件出發(fā)，按問(wèn)題規(guī)模從小到大依次求出每個(gè)子問(wèn)題的最優(yōu)解，直至求出問(wèn)題最終的最優(yōu)解為止，這一過(guò)程通?？捎醚h(huán)結(jié)構(gòu)實(shí)現(xiàn)，如源程序一就是如此。那么動(dòng)態(tài)規(guī)劃算法能不能用自頂向下的遞歸策略加以優(yōu)化來(lái)實(shí)現(xiàn)呢？首先讓看直接遞歸到底慢在什么地方？顯然是因?yàn)槎啻沃貜?fù)解相同的子問(wèn)題所致，如果來(lái)看每個(gè)子問(wèn)題的最優(yōu)解在第一次遞歸求出后保存起來(lái)，今后遇到要遞歸求相同的子問(wèn)題的最優(yōu)解時(shí)，先看一看這個(gè)子問(wèn)題解過(guò)沒(méi)有，如解過(guò)即不再進(jìn)行遞歸調(diào)用，直接將前面求得的最優(yōu)解取出使用。這就是化的方法，它的時(shí)間復(fù)雜度與自底向上的遞推一致。一個(gè)化的遞歸算法需要開(kāi)辟一個(gè)數(shù)組用來(lái)每個(gè)子問(wèn)題的最優(yōu)解，開(kāi)始

10、時(shí)該數(shù)組中每個(gè)元素都包含一個(gè)特殊值，表示該子問(wèn)題的最優(yōu)解尚未解出，當(dāng)在遞歸算法中一般來(lái)說(shuō)，只要該問(wèn)題可以劃分成規(guī)模更小的子問(wèn)題，并且原問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問(wèn)題實(shí)例分解為更小的、相似的子問(wèn)題，并策略。子問(wèn)題的解而避免計(jì)算重復(fù)的子問(wèn)題，以解決最優(yōu)化問(wèn)題的算法由此可知，動(dòng)態(tài)規(guī)劃法與分治法類似，它們都是將問(wèn)題實(shí)例歸納為更小的、相似的子問(wèn)題，并通過(guò)求解子問(wèn)題產(chǎn)生一個(gè)全局最優(yōu)解。其中分治法中的各個(gè)子問(wèn)題是獨(dú)立的（即不包含公共的子問(wèn)題），因此一旦遞歸地求出各子問(wèn)題的解后，便可自下而上地將子問(wèn)

11、題的解合并成問(wèn)題的解。但的是，如果各子問(wèn)題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問(wèn)題。解決上述問(wèn)題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問(wèn)題，這類問(wèn)題會(huì)有多種可能的解，每個(gè)有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)（最大或最?。┙狻Ｈ舸嬖诙鄠€(gè)最優(yōu)解的話，它只取其中的一個(gè)。在求解過(guò)程中，該方法也是通過(guò)求解局部子問(wèn)題的解達(dá)到全局最優(yōu)解，但與分治法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問(wèn)題不獨(dú)立，（亦即各子問(wèn)題可包含公共的子子問(wèn)題）也允許其通過(guò)自身子問(wèn)題的解作出選擇，該方法對(duì)每一個(gè)子問(wèn)題只解一次，并將結(jié)果保存起來(lái)，避免每次碰到時(shí)都要重復(fù)計(jì)算。因此，動(dòng)態(tài)規(guī)劃法所針對(duì)有一個(gè)顯著的特征，即它所對(duì)應(yīng)的

12、子問(wèn)題樹(shù)中的子問(wèn)題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問(wèn)題，只在第一次遇到時(shí)加以求解，并把保存起來(lái)，讓以后再遇到時(shí)直接，不必重新求解。第三節(jié)動(dòng)態(tài)規(guī)劃算法的基本步驟設(shè)計(jì)一個(gè)動(dòng)態(tài)規(guī)劃算法，通?？砂匆韵聨讉€(gè)步驟進(jìn)行：分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。遞歸地定義最優(yōu)值。（3）以自底向上的方式或自頂向下的化方法（備忘錄法）計(jì)算出最優(yōu)值。（4）根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造一個(gè)最優(yōu)解。步驟（1）（3）是動(dòng)態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步驟（4）可以省略，若需要求出問(wèn)題的一個(gè)最優(yōu)解，則必須執(zhí)行步驟（4）。此時(shí)，在步驟（3）中計(jì)算最優(yōu)值時(shí)，通常需的信息，以便在步驟（4

13、）中，根據(jù)所的信息，快速地構(gòu)造出一個(gè)最優(yōu)解。下面以求最長(zhǎng)公共子序列(LCS)問(wèn)題為例說(shuō)明這一過(guò)程。例 8_2: 最長(zhǎng)公共子序列問(wèn)題描述 一個(gè)給定序列的子序列是在該序列中刪去若干元素后得到的序列。確切地說(shuō)，若給定序列 X=，則另一序列 Z=是 X 的子序列是指存在一個(gè)嚴(yán)格遞增的下標(biāo)序列，使得對(duì)于所有 j=1,2,k 有：例如，序列 Z=是序列 X=的子序列，相應(yīng)的遞增下標(biāo)序列為。給定兩個(gè)序列 X 和 Y，當(dāng)另一序列 Z 既是 X 的子序列又是 Y 的子序列時(shí)，稱 Z 是序列 X 和Y 的公共子序列。例如，若 X=和 Y=，則序列是X 和Y 的一個(gè)公共子序列，序列也是 X 和Y 的一個(gè)公共子序列。

14、而且，后者是 X和Y 的一個(gè)最長(zhǎng)公共子序列，因?yàn)?X 和Y 沒(méi)有長(zhǎng)度大于 4 的公共子序列。給定兩個(gè)序列 X=和 Y=，要求找出 X 和Y 的一個(gè)最長(zhǎng)公共子序列。輸入輸入文件共有兩行，每行為一個(gè)由大寫字母X 和Y。輸出的長(zhǎng)度不超過(guò) 200 的字符串，表示序列輸出文件第一行為一個(gè)非負(fù)整數(shù)，表示所求得的最長(zhǎng)公共子序列的長(zhǎng)度，若不存在公共子序列，則輸出文件僅有一行輸出一個(gè)整數(shù) 0，否則在輸出文件的第二行輸出所求得的最長(zhǎng)公共子序列(也用一個(gè)大寫字母組成的字符串表示)，若符合條件的最長(zhǎng)公共子序列不止一個(gè)，只需輸出其中任意的一個(gè)。輸入樣例 LCS.INABCBDABBDCABA輸出樣例 LCS.OUT 4

15、BCBA評(píng)分標(biāo)準(zhǔn) 若輸出的最長(zhǎng)公共子序列的長(zhǎng)度正確，則得 5 分；若輸出的最長(zhǎng)公共子序列也正確，則再得 5 分。問(wèn)題分析動(dòng)態(tài)規(guī)劃算法可有效地解此問(wèn)題。下面?zhèn)€解此問(wèn)題的有效算法。1.最長(zhǎng)公共子序列的結(jié)構(gòu)按照動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)的各個(gè)步驟來(lái)設(shè)計(jì)一解最長(zhǎng)公共子序列問(wèn)題時(shí)最容易想到的算法是窮舉搜索法，即對(duì)X 的每一個(gè)子序列，檢查它是否也是Y 的子序列，從而確定它是否為X 和Y 的公共子序列，并且在檢查過(guò)程中選出最長(zhǎng)的公共子序列。X 的所有子序列都檢查過(guò)后即可求出X 和Y 的最長(zhǎng)公共子序列。X 的一個(gè)子序列相應(yīng)于下標(biāo)序列1,2, m的一個(gè)子序列，因此，X 共有 2m 個(gè)不同子序列，從而窮舉搜索法需要指數(shù)時(shí)間

16、。事實(shí)上，最長(zhǎng)公共子序列問(wèn)題也有最優(yōu)子結(jié)構(gòu)性質(zhì)，因?yàn)槎ɡ? LCS 的最優(yōu)子結(jié)構(gòu)性質(zhì)有如下定理：設(shè)序列 X=和 Y=的一個(gè)最長(zhǎng)公共子序列 Z=，則：若xm=yn，則 zk=xm=yn 且Zk-1 是Xm-1 和Yn-1 的最長(zhǎng)公共子序列；若xmyn 且zkxm ，則Z 是Xm-1 和Y 的最長(zhǎng)公共子序列；若xmyn 且zkyn ，則 Z 是X 和Yn-1 的最長(zhǎng)公共子序列。其中 Xm-1=，Yn-1=，Zk-1=。證明：用反證法。若 zkxm，則是 X 和 Y 的長(zhǎng)度為 k 十 1 的公共子序列。這與 Z 是X 和Y 的一個(gè)最長(zhǎng)公共子序列。因此，必有 zk=xm=yn。由此可知 Zk-1 是X

17、m-1 和Yn-1的一個(gè)長(zhǎng)度為k-1 的公共子序列。若Xm-1 和Yn-1 有一個(gè)長(zhǎng)度大于k-1 的公共子序列W，則將xm加在其尾部將產(chǎn)生 X 和 Y 的一個(gè)長(zhǎng)度大于 k 的公共子序列。此為一個(gè)最長(zhǎng)公共子序列。故 Zk-1 是 Xm-1 和 Yn-1 的由于 zkxm，Z 是 Xm-1 和 Y 的一個(gè)公共子序列。若 Xm-1 和 Y 有一個(gè)長(zhǎng)度大于 k 的公共子序列 W，則 W 也是 X 和 Y 的一個(gè)長(zhǎng)度大于 k 的公共子序列。這與 Z 是 X 和 Y 的一個(gè)最長(zhǎng)公共子序列。由此即知Z 是Xm-1 和Y 的一個(gè)最長(zhǎng)公共子序列。這個(gè)定理告訴，兩個(gè)序列的最長(zhǎng)公共子序列包含了這兩個(gè)序列的前綴的最長(zhǎng)

18、公共子序列。因此，最長(zhǎng)公共子序列問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2. 子問(wèn)題性質(zhì)由最長(zhǎng)公共子序列問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)可知，要找出 X=和 Y=的最長(zhǎng)公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)xm=yn 時(shí)，找出Xm-1 和Yn-1 的最長(zhǎng)公共子序列，然后在其尾部加上 xm(=yn)即X 和Y 的一個(gè)最長(zhǎng)公共子序列。當(dāng) xmyn 時(shí)，必須解兩個(gè)子問(wèn)題，即找出 Xm-1 和Y 的一個(gè)最長(zhǎng)公共子序列及X 和Yn-1 的一個(gè)最長(zhǎng)公共子序列。這兩個(gè)公共子序列中較長(zhǎng)者即為X 和Y 的一個(gè)最長(zhǎng)公共子序列。由此遞歸結(jié)構(gòu)容易看到最長(zhǎng)公共子序列問(wèn)題具有子問(wèn)題性質(zhì)。例如，在計(jì)算X 和Y 的最長(zhǎng)公共子序列時(shí)，可能要計(jì)算出 X 和

19、Yn-1 及Xm-1 和Y 的最長(zhǎng)公共子序列。而這兩個(gè)子問(wèn)題都包含一個(gè)公共子問(wèn)題，即計(jì)算Xm-1 和Yn-1 的最長(zhǎng)公共子序列。來(lái)建立子問(wèn)題的最優(yōu)值的遞歸關(guān)系。用 ci,j序列 Xi 和 Yj 的最長(zhǎng)公共子序列的長(zhǎng)度。其中 Xi=，Yj=。當(dāng) i=0 或 j=0 時(shí)，空序列是 Xi 和 Yj的最長(zhǎng)公共子序列，故ci,j=0。其他情況下，由定理可建立遞歸關(guān)系如下：3.計(jì)算最優(yōu)值直接利用上式容易寫出一個(gè)計(jì)算 ci,j的遞歸算法，但其計(jì)算時(shí)間是隨輸入長(zhǎng)度指數(shù)增長(zhǎng)的。由于在所考慮的子問(wèn)題空間中，總共只有 O(m*n)個(gè)不同的子問(wèn)題，因此，用動(dòng)態(tài)規(guī)劃算法自底向上地計(jì)算最優(yōu)值能提高算法的效率。計(jì)算最長(zhǎng)公共

20、子序列長(zhǎng)度的動(dòng)態(tài)規(guī)劃算CS_LENGTH(X,Y)以序列 X=和Y=作為輸入。輸出兩個(gè)數(shù)組 c0.mXi 與 Yj 的最長(zhǎng)公共子序列的長(zhǎng)度，bi,j,0.n和 b1.m ,1.n。其中 ci,j指示 ci,j的值是由哪一個(gè)子問(wèn)題的解達(dá)到的，這在構(gòu)造最長(zhǎng)公共子序列時(shí)要用到。最后，X 和 Y 的最長(zhǎng)公共子序列的長(zhǎng)度于cm,n中。由于每個(gè)數(shù)組單元的計(jì)算耗費(fèi) (1)時(shí)間，算CS_LENGTH 耗時(shí) (mn)。4.構(gòu)造最長(zhǎng)公共子序列由算CS_LENGTH 計(jì)算得到的數(shù)組b 可用于快速構(gòu)造序列 X=和 Y=的最長(zhǎng)公共子序列。首先從 bm,n開(kāi)始，沿著其中的箭頭所指的方向在數(shù)組 b 中搜索。當(dāng) bi,j中遇

21、到時(shí)，表示 Xi 與 Yj 的最長(zhǎng)公共子序列是由 Xi-1 與 Yj-1 的最長(zhǎng)公共子序列在尾部加上 xi 得到的子序列；當(dāng) bi,j中遇到時(shí)，表示 Xi 與 Yj 的最長(zhǎng)公共子序列和Xi-1 與Yj 的最長(zhǎng)公共子序列相同；當(dāng) bi,j中遇到時(shí)，表示 Xi 與Yj 的最長(zhǎng)公共子序列和Xi 與Yj-1 的最長(zhǎng)公共子序列相同。下面的算CS(b,X,i,j)實(shí)現(xiàn)根據(jù) b 的內(nèi)容打印出Xi 與Yj 的最長(zhǎng)公共子序列。在算CS 中，每一次的遞歸調(diào)用使i 或j 減 1，因此算法的計(jì)算時(shí)間為 O(m+n)。參考程序Progr8_2(Input, Output)； const maxlen=200；var i

22、,j:long；c:array0.maxlen,0.maxlen of byte；x,y,z:string；beginassign(input,lcs.in)； reset(input)； readln(x)；readln(y)； close(input)； fillchar(c,sizeof(c),0)； for i:=1 to length(x) dofor j:=1 to length(y) do if xi=yjthen ci,j:=ci-1,j-1+1else if ci-1,jci,j-1then ci,j:=ci-1,jelse ci,j:=ci,j-1；z:=； i:=leng

23、th(x)； j:=length(y)；assign(output,lcs.out)； rewrite(output)；wrin(ci,j)；while (i0) and (j0) do if xi=yjthen begin z:=xi+z；i:=i-1；j:=j-1else if ci-1,jci,j-1endthen elseif z then wriclose(output)i:=i-1 j:=j-1；n(z)；end.第四節(jié)應(yīng)用舉例例 8_3: BUY LOW, BUY LOWER問(wèn)題描述 “低價(jià)”這條建議是在奶牛市場(chǎng)取得成功的一半規(guī)則。要想被認(rèn)為是偉大的投資者，你必須遵循以下建議:“

24、低價(jià)；再低價(jià)”。每次你一支,你必須用低于次它的價(jià)格它。買的次數(shù)越多越好!你的目標(biāo)是在遵循以上建議的前提下，求你最多能的次數(shù)。你將被給出一段時(shí)間內(nèi)一支每天的出售價(jià)(216 范圍內(nèi)的正整數(shù))，你可以選擇在哪些天這支。每次都必須遵循“低價(jià)購(gòu)買；再低價(jià)”的原則。寫一個(gè)程序計(jì)算最大次數(shù)。這里是某支的價(jià)格日期 1 2 3 4 5 6 7價(jià)格 68 69 54 64 68 64 70最優(yōu)秀的投資者可以：8 9 10 1167 78 62 98最多 4 次1287，可行方案中的一種是：日期價(jià)格2 5 6 1069 68 64 62輸入第 1 行: N (1 = N = 5000)，天數(shù)第 2 行: N 個(gè)數(shù)，

25、是每天的價(jià)格。次數(shù)和擁有最大次數(shù)的方案數(shù)(=231)的價(jià)格隊(duì)列一樣的時(shí)候）,這 2 種方案被認(rèn)為輸出 輸出文件僅一行包含兩個(gè)數(shù):最大當(dāng)二種方案“看起來(lái)一樣”時(shí)（就是說(shuō)它們是相同的。輸入樣例 BUYLOW.IN 1268 69 54 64 68 64 70 67 78 62 98 87 輸出樣例 BUYLOW.OUT4 2問(wèn)題分析 問(wèn)題的第一部分是要求輸入數(shù)據(jù)串中的一個(gè)最長(zhǎng)下降序列的長(zhǎng)度，可使用動(dòng)態(tài)規(guī)劃的方法，具體做法是從序列的最后一個(gè)元素開(kāi)始，依次求出以第i 個(gè)元素為第一個(gè)元素時(shí)的最長(zhǎng)下降序列的長(zhǎng)度 leni，顯然 lenn=1，leni=max(lenj+1)，其中 ia5=2和 len3=

26、1,len2=2 且 a2=3a3=1t4=1，由 len5=1,len2=2 且 a2=3a5=2t2=t5+t3=2，對(duì)應(yīng)a2,a3和a2,a5 兩個(gè)不同的以 a2 起頭的最長(zhǎng)下降序列， 最終由 len4=2,len1=3 且a1=5a4=4 和len2=2,len1=3 且 a1=5a2=3t1=t4+t2=1+2=3，所以本例中最長(zhǎng)下降序列總數(shù)為 3，分別為5,4,2,5,3,2和5,3,1。對(duì)于有相同元素的序列來(lái)說(shuō)，如序列 a=(5,4,1,4,2)，其中有兩個(gè)相同的元素 4，前面的推導(dǎo)過(guò)程不變，最后一步推導(dǎo)受兩個(gè)相同元素的影響，不能能簡(jiǎn)單相加，由于 a2=a4=4，對(duì)于所有的以 a

27、4 起頭的最長(zhǎng)下降序列，只要將 a4 改為 a2 即到同樣長(zhǎng)度的下降序列，所以 t4中的統(tǒng)計(jì)的序列在 t2中也統(tǒng)計(jì)在內(nèi)了，當(dāng)序列中有相同元素時(shí)，為避免重復(fù)計(jì)數(shù)，從后向前遞推時(shí)當(dāng)后面的元素遇到前面的相同元素時(shí)則不再向前推。程序中為了方便處理，在整個(gè)序列前設(shè)置了一個(gè)標(biāo)致元素 a0=maxlong，將 len0置為 maxlen+1。參考程序Progr8_3(Input, Output)； const maxn=5000；var i,j,n,l,maxlen:long；a,len,t:array 0.maxn of long beginassign(input,buylow.in)； reset(i

28、nput)； assign(output,buylow.out)； rewrite(output)；readln(n)；forfor fori:=1 to n do read(ai)； i:=1 to n do leni:=1； i:=n-1 downto 1 dofor j:=i+1 to n doif (aj=leni)then leni:=lenj+1；maxlen:=1； for i:=1 to na0:=maxlongf lenimaxlen then maxlen:=leni； len0:=maxlen+1；f leni=1 then ti:=1 else ti:=0；for i:

29、=0 for l:=1 beginforto nto maxlen doi:=n downto 1 do if leni=l thenbeginj:=i-1；while (j=0) and (ajai) do beginif (ajai) and (lenj=l+1) then dec(j)end；end；inc(tj,ti)；end；wrin(maxlen, ,t0)；close(input)；close(output)；end.例 8_4: 回文詞問(wèn)題描述 回文詞是一種對(duì)稱的字符串也就是說(shuō)，一個(gè)回文詞，從左到右讀和從右到左讀得到的結(jié)果是一樣的。任意給定一個(gè)字符串，通過(guò)若干字符，都可以變成一

30、個(gè)回文詞。你的任務(wù)是寫一個(gè)程序，求出將給定字符串變成回文詞所需的最少字符數(shù)。比如字符串“Ab3bd”，在兩個(gè)字符后可以變成一個(gè)回文詞（“dAb3bAd”“Adb3bdA”）。然而，兩個(gè)以下的字符無(wú)法使它變成一個(gè)回文詞。輸入輸入文件的文件名是 PALIN.IN。文件的第一行包含一個(gè)整數(shù)N，表示給定字符串的長(zhǎng)度，3N5000。文件的第二行是一個(gè)長(zhǎng)度為 N 的字符串。字符串僅由大寫字母“A”到“Z”，小寫字母“a”到“z”和數(shù)字“0”到“9”輸出。大寫字母和小寫字母將被認(rèn)為是不同的。輸出文件名是 PALIN.OUT，文件只有一行，包含一個(gè)整數(shù)，表示需要的最少字符數(shù)。輸入樣例 PALIN.IN 5Ab

31、3bd輸出樣例 PALIN.OUT 2問(wèn)題分析一、算法A簡(jiǎn)單地說(shuō)，問(wèn)題等價(jià)于：將原串 St 從某處截?cái)啵蔀?St1.j和 STj+1.n，求 St1.j和Stj+1.n的倒序串的最長(zhǎng)公共子序列的長(zhǎng)度。（不失一般性，設(shè) jn-j）比如樣例：Ab3bd，有“Ab3”和“bd”的倒序“db”，其公共子序列最長(zhǎng)為 1“b”。也就是說(shuō)，該段公共序列是不需要經(jīng)過(guò)處理就滿足回文要求的，而其余的字符則需要進(jìn)行復(fù)制。所以添加的字符數(shù)應(yīng)為n-2*Length（SubString）。而注意到，有時(shí)某個(gè)字符可作為對(duì)稱中心出現(xiàn)，不須被（例如上例中的“3”），所以若前一個(gè)子串的最后一個(gè)字符未出現(xiàn)在求得的公共子串中，則將

32、它作為對(duì)稱中心，最少要添加n-2*Length（SubString）-1 個(gè)字符。求解的方程可表示為：Minn-2*MaxLongestSub(St1.j, Stn.j+1)(n div 2 jn),n-2*MaxLongestSub(St1.j, Stn.j+2)-1 (n div 2 jn) 其中：LongestSub(St1,St2)表示 St1 和St2 的最長(zhǎng)公共子序列的長(zhǎng)度,Sti.j 表示原串中從第i 位到第j 位依次的一個(gè)新字符串。對(duì)于最長(zhǎng)公共子序列的求解分析，設(shè)現(xiàn)在要求字符串St1 和St2 的最長(zhǎng)公共子序列，其長(zhǎng)度分別為 L1，L2。 動(dòng)態(tài)規(guī)劃求解的過(guò)程是眾所周知的： 令

33、Li,j表示 St1 的前 i 位與 St2 的前 j 位的最長(zhǎng)公共序列長(zhǎng)度， 則：Li,j=Max Li-1,j-1+1, Li,j-1, Li-1,j 若St1i=St2jMax Li,j-1, Li-1,j若St1i=St2j( 1iL1 , 1jL2 , 顯然 i 或j 為 0 時(shí),L 值為 0)。于是，LongestSub=LL1,L2?；谠诒绢}的這種算法中，似乎對(duì)于最長(zhǎng)公共子序列的求解要被多次應(yīng)用，然而其中重復(fù)計(jì)算頗多，可直接求原串 St 及其倒序串St的最長(zhǎng)公共序列，在該過(guò)程中完成上述的若干過(guò)程。for i:=1 to n dofor j:=1 to smaller(n-i,n

34、 div 2) do以St 的前 i 位匹配 St的前 j 位，避免重復(fù)計(jì)算，同時(shí)要滿足： i+j=n, j=n-1then如果 i+j=n 或 i+j=n-1，說(shuō)明找到可行解若n-Li,j*2-(n-i-j)優(yōu)于當(dāng)前最優(yōu)，更新之end；節(jié)約起見(jiàn)，根據(jù)遞推的特點(diǎn)，可用一維數(shù)組替代二維進(jìn)行迭代。二、算法B使用類似數(shù)字三角形或最小代價(jià)子母樹(shù)的動(dòng)態(tài)規(guī)劃過(guò)程。令 Costi,j表示將原串 St 從第j 位開(kāi)始長(zhǎng)度為i 的子串SubString 變成回文詞的最小添加字符數(shù)。按SubString 的長(zhǎng)度大小依次進(jìn)行遞推求解：Costi,j= Costi-2,j+1Min Costi-1,j+1, Cost

35、i-1,j+1+1（2in，1jn-i+1） 顯然，當(dāng) i=1 或 0 時(shí)，Cost 值均為 0。參考程序若Stj=Sti+j-1,即首尾對(duì)稱若StjSti+j-1。Progrtype8_4(Input, Output)；arr=array0.5000 ofvareger；h1,m1,s1,ms1,h2,m2,s2,ms2:word； ch,ch1:array1.5000 of char； a,b:arr；min,n,b1,b2:eger；procedure init；var i:begineger；assign(input,palin.in)；reset(input)；readln(n)；f

36、or i:=1 to n do beginread(chi)； ch1n-i+1:=chi；end； close(input)；end；function smaller(a,b:begineger):eger；if ab then smaller:=b else smaller:=a；end；proceduret；varx,i,j:begineger；fillchar(a,sizeof(a),0)； min:=n；for i:=1 to n do beginb2:=0；for j:=1 to smaller(n-i,n div 2) do beginb1:=b2； b2:=aj；if chi=

37、ch1j then begin if b1+1ajthen aj:=b1+1； endelse if aj-1aj then aj:=aj-1； if i+j=n-1 thenbeginx:=n-aj*2-(n-i-j)； if minx then min:=x；end； end；end；assign(output,palin.out)； rewrite(output)；wrin(min)；close(output)end；begin main init；t；end.例 8_5: 花店櫥窗布置問(wèn)題描述 假設(shè)你想以最美觀的方式布置花店的櫥窗?，F(xiàn)在你有F 束不同品種的花束，同時(shí)你也有至少同樣數(shù)量的

38、花瓶被按順序擺成一行。這些花瓶的位置固定于架子上，并從 1至V 順序，V 是花瓶的數(shù)目，從左至右排列，則最左邊的是花瓶 1，最右邊的是花瓶V?；ㄊ梢砸苿?dòng)，并且每束花用 1 至F 間的整數(shù)唯一標(biāo)識(shí)。標(biāo)識(shí)花束的整數(shù)決定了花束在花瓶中的順序，如果IJ，則令花束I 必須放在花束J 左邊的花瓶中。例如，假設(shè)一束杜鵑花的標(biāo)識(shí)數(shù)為 1，一束秋海棠的標(biāo)識(shí)數(shù)為 2，一束康乃馨的標(biāo)識(shí)數(shù)為 3，所有的花束在放入花瓶時(shí)必須保持其標(biāo)識(shí)數(shù)的順序，即：杜鵑花必須放在秋海棠左邊的花瓶中，秋海棠必須放在康乃馨左邊的花瓶中。如果花瓶的數(shù)目大于花束的數(shù)目。則多余的花瓶必須空置，且每個(gè)花瓶中只能放一束花。每一個(gè)花瓶都具有各自的特點(diǎn)

39、。因此，當(dāng)各個(gè)花瓶中放入不同的花束時(shí)，會(huì)產(chǎn)生不同的美學(xué)效果，并以美學(xué)值（一個(gè)整數(shù)）來(lái)表示，空置花瓶的美學(xué)值為零。在上述例子中，花瓶與花束的不同搭配所具有的美學(xué)值，如表 8_1 所示。表 8_1例如，根據(jù)上表，杜鵑花放在花瓶 2 中，會(huì)顯得非常好看；但若放在花瓶 4 中則顯得十分難看。為取得最佳美學(xué)效果，你必須在保持花束順序的前提下，使花束的擺放取得最大的美學(xué)值。如果有不止一種的擺放方式具有最大的美學(xué)值，則其中任何一直擺放方式都可以接受，但你只要輸出任意一種擺放方式。假設(shè)條件:1F100，其中 F 為花束的數(shù)量，花束FV100，其中 V 是花瓶的數(shù)量。從 1 至F。-50Aij50，其中 Aij

40、 是花束i 在花瓶 j 中的美學(xué)值。輸入花瓶12345花束1 (杜鵑花)723-5-24162 (秋海棠)521-410233 (康乃馨)-215-4-2020輸入文件名flower.inp，第一行包含兩個(gè)數(shù)：F，V。隨后的 F 行中，每行包含 V 個(gè)整數(shù)，Aij 即為輸入文件中第（i+1 ）行中的第 j 個(gè)數(shù)。輸出輸出文件名為 flower.out，文件應(yīng)包含兩行：第一行是程序所產(chǎn)生擺放方式的美學(xué)值。第二行必須用F 個(gè)數(shù)表示擺放方式，即該行的第K 個(gè)數(shù)表示花束K 所在的花瓶的。輸入樣例flower.inp375523215 24 16-4 10 23-21 5 -4 -20 20輸出樣例 f

41、lower.out 532 4 5問(wèn)題分析 本題雖然是較為簡(jiǎn)單的一題，但其中大有文章可作。說(shuō)它簡(jiǎn)單，是因?yàn)樗行?，因此一眼便可看出這題應(yīng)該用動(dòng)態(tài)規(guī)劃來(lái)解決。但是，如何動(dòng)態(tài)規(guī)劃呢？如何劃分階段，又如何選擇狀態(tài)呢？方法 1：以花束的數(shù)目來(lái)劃分階段。在這里，階段變量 k 表示的就是要布置的花束數(shù)目（前 k 束花），狀態(tài)變量 sk 表示第k 束花所在的花瓶。而對(duì)于每一個(gè)狀態(tài) sk，決策就是第 k-1束花應(yīng)該放在哪個(gè)花瓶，用 uk 表示。最優(yōu)指標(biāo)函數(shù) fk(sk)表示前 k 束花，其中第 k 束插在第sk 個(gè)花瓶中，所能取得的最大美學(xué)值。狀態(tài)轉(zhuǎn)移方程為：兩種劃分階段的方法，引出了兩種狀態(tài)表示法，兩種規(guī)劃

42、方式，但是卻都成功地解決了問(wèn)題。只不過(guò)因?yàn)闆Q策的選擇有多有少，所以算法的時(shí)間復(fù)雜度也就不同。這個(gè)例子具有很大的普遍性。有很多的多階段決策問(wèn)題都有著不止一種的階段劃分方法，因而往往就有不止一種的規(guī)劃方法。有時(shí)各種方法所產(chǎn)生的效果是差不多的，但的時(shí)候，就像的例子一樣，兩種方在某個(gè)方面有些區(qū)別。所以，在用動(dòng)態(tài)規(guī)劃解題的時(shí)候，可以多想是否有其它的解法。對(duì)于不同的解法，要注意比較，好的算法好在哪里，差一點(diǎn)的算法差在哪里。從各種不同算法的比較中，可以更深刻地動(dòng)態(tài)規(guī)劃的構(gòu)思技巧。參考程序Progr varF,V8_5(Input, Output)；:byte； 花束和花瓶的數(shù)目A :array 1.100,

43、1.100 of short；Ai,j花束 i 放在花瓶j 中的美學(xué)值Best:array 0.100,0.100 ofeger；Besti,j前 i 束花放j 個(gè)花瓶中的最優(yōu)解Previous:array 1.100,1.100 of byte；Previousi,j在 Besti,j的最優(yōu)解中，花束 i-1 的位置procedure ReadIn； 讀入 vari,j :byte； beginreset(input)； readln(F,V)； for i:=1 to F do beginfor j:=1 to V do read(Ai,j)；readln； end； close(inpu

44、t)；end；procedure Work；規(guī)劃主過(guò)程vari,j,tbegin:byte；fillchar(Best0,sizeof(Best0),0)；for i:=1 to F do邊界條件for j:=i to V+i-F do beginBesti,j:=low(Besti,j)；for t:=i-1 to j-1 do 枚舉花束 i-1 的位置 if Besti-1,tBesti,j thenbegin更新當(dāng)前最優(yōu)解Besti,j:=Besti-1,t； Previousi,j:=t；end； inc(Besti,j,Ai,j)；end；end；procedure Prvar；打印

45、最優(yōu)解i,j :byte；Put :array 1.100 of byte； begini:=F；for j:=F+1 to V do 選擇全局最優(yōu)解 if BestF,jBestF,i theni:=j； i 最后一束花的位置 rewrite(output)；wri n(BestF,i)； for j:=F downto 1 do beginPutj:=i； i:=Previousj,i； end； write(Put1)；for i:=2 to F dowrite( ,Puti)；wrin；close(output)；end；begin mainassign(input,flower.in

46、p)； assign(output,flower.out)； ReadIn；Work；Pr；end.例 8_6: 郵局問(wèn)題描述 一些村莊被建在一條筆直的高速公路邊上。用一條坐標(biāo)軸來(lái)描述這條高速公路，每一個(gè)村莊的坐標(biāo)都是整數(shù)。沒(méi)有兩個(gè)村莊坐標(biāo)相同。兩個(gè)村莊間的距離，定義為它們的坐標(biāo)值差的絕對(duì)值。需要在一些村莊建立郵局當(dāng)然，并不是每一個(gè)村莊都必須建立郵局，郵局必須被建在村莊里，因此它的坐標(biāo)和它所在的村莊坐標(biāo)相同。每個(gè)村莊使用離它最近的那個(gè)郵局，建立這些郵局的原則是：所有村莊到各自所使用的郵局的距離總和最小。你的任務(wù)是編寫一個(gè)程序，在給定了每個(gè)村莊的坐標(biāo)和將要建立的郵局?jǐn)?shù)之后，按照上述原則，合理地選

47、擇這些郵局的位置。輸入輸入文件的文件名是T.IN。文件的第一行包含兩個(gè)整數(shù)：第一個(gè)整數(shù)是村莊的數(shù)目V，1V300；第二個(gè)整數(shù)是將建立的郵局?jǐn)?shù) P，1P30 且PV。文件的第二行遞增順序列出了 V 個(gè)整數(shù)。這 V 個(gè)整數(shù)分別表示了各村莊的位置坐標(biāo)。對(duì)于每一個(gè)位置坐標(biāo) X，1X10000。輸出輸出文件名是T.OUT。文件的第一行是一個(gè)整數(shù) S，表示你所求出的所有村莊到地離它最近的郵局的距離總和。相應(yīng)地，文件的第二行按照遞增順序列出了P 個(gè)整數(shù)，分別表示您所求出的每個(gè)郵局的建立位置。雖然對(duì)于同一個(gè) S，可能回有多種郵局建立的方案，單只需輸出其中的一種。輸入樣例10 51 2 3 6T.IN79 11

48、 22 44 50輸出樣例 92 7 22 44T.OUT50問(wèn)題分析 這道題采用動(dòng)態(tài)規(guī)劃的算法。階段的劃分標(biāo)準(zhǔn)是已安排的郵局?jǐn)?shù)和覆蓋的村莊數(shù)（所謂“某郵局覆蓋的村莊”是指使用該郵局的村莊）?，F(xiàn)以 Costi,j表示安排前 i個(gè)郵局給前j 個(gè)村莊使用，通過(guò)某種安排，使這j 個(gè)村莊分別到這i 個(gè)郵局中最近的一個(gè)的距離之和的所取到的最小值。另設(shè) NewCostA,B為：分配 A 至 B 這（B-A+1）個(gè)村莊使用一個(gè)新的郵局，通過(guò)某種安排新郵局段，使 A 至B 這（B-A+1）個(gè)村莊分別到這個(gè)新郵局的距離之和所取到的最小值。于是有：Costi,j=Min Costk,j-1+NewCostk+1,

49、i （其中，j-1kj）下面著重NewCost一下 NewCostA,B的求解。相當(dāng)于郵局?jǐn)?shù)為 1 的原問(wèn)題的一種特殊情況。即，給定 N 個(gè)村莊的 X 坐標(biāo)，要求安排一個(gè)郵局，使各村莊到該郵局的距離和為最小，求郵局坐標(biāo)。首先可以證明，最優(yōu)解必定可使得郵局坐落在一個(gè)村莊上。假設(shè)有一個(gè)最優(yōu)解，其郵局的坐標(biāo)為xP，且 xAxPxA+1，即該郵局在第 A 個(gè)村莊和第 A+1 個(gè)之間?？偩嚯x顯然，如果 2AN，則可取 xPxP，如此所得 Ds必優(yōu)于 Ds，而以 xP=xA 時(shí)為最優(yōu)；若 2AN，同理應(yīng)取 xP= xA+1；若 2A=N，則 xAxPxA+1無(wú)妨。接下來(lái)，一下到底把郵局建在哪里最為經(jīng)濟(jì)。設(shè)

50、把郵局建在第k 個(gè)村莊，總距離為：若這是一個(gè)最優(yōu)解，則必有：Ds（k）Ds（k-1），于是，同樣地，Ds（k）Ds（k+1）?？梢?jiàn)，k=N div 2 +1 時(shí)必為一個(gè)最優(yōu)解。在實(shí)現(xiàn)過(guò)程中，不妨先將所有NewCostA,B的值事先計(jì)算好，供規(guī)劃過(guò)程中隨時(shí)調(diào)用，以節(jié)省處理時(shí)間。參考程序Progrtype8_6(Input, Output)；node=recordcost:long；pre:end；eger；arr=array0.30 of node；arr1=array1.300 of varwork:array0.300 ofcor:array0.300 oflong；arr；eger；n,h

51、:eger；build:array1.300 ofmcost:array1.300 ofeger；arr1；procedure start； beginassign(input, reset(input)；assign(output,輸入輸出準(zhǔn)備t.in)；t.out)；rewrite(output)；end；procedure over；結(jié)束工作 beginclose(input)； close(output)；end；procedure init； vari:eger； beginreadln(n,h)； for i:=1 to n doread(cori)； readln；end；fun

52、ction mincost(a,b:在村莊a 與b 之間varsum,i,min,k:long；begineger；varhcor:eger):long；一個(gè)郵局，最小消耗hcor:=a+(b-a+1) div 2)； sum:=0；for i:=hcor-1 downto a dosum:=sum+corhcor-cori； for i:=hcor+1 to b dosum:=sum+cori-corhcor； mincost:=sum； hcor:=corhcor；end；function smaller(a,b:longbegin):long；if ab then smaller:=b

53、else smaller:=a；end；procedurevart； 規(guī)劃過(guò)程i,j,k,c,x,y,sum,min,sum1:long hc:eger；beginfor i:=1 to n do beginnew(mcosti)；for j:=1 to n do mcostij:=maxlong end；for i:=1 to n do mcostii:=0； for i:=1 to n dofor j:=i+1 to n do mcostij:=mincost(i,j,hc)；for i:=0 to n do beginnew(worki)； fillchar(worki,sizeof(worki),0)；end；for i:=2 to n do beginworki1.cost:=mcost1i； for j:=2