動(dòng)態(tài)規(guī)劃的技巧

1、動(dòng)態(tài)規(guī)劃的技巧階段的劃分和狀態(tài)的表示在動(dòng)態(tài)規(guī)劃的設(shè)計(jì)過程中，階段的劃分和狀態(tài)的表示是非常重要的兩步， 這兩步會(huì)直接影響該問題的計(jì)算復(fù)雜性，有時(shí)候階段劃分或狀態(tài)表示的 不合理還會(huì)使得動(dòng)態(tài)規(guī)劃法不適用。例9街道問題在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。這是一道簡(jiǎn)單而又典型的動(dòng)態(tài)規(guī)劃題，許多介紹動(dòng)態(tài)規(guī)劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的：按照?qǐng)D中的虛線來劃分階段，即階段變量k表示走過的步數(shù)，而狀態(tài)變 量xk表示當(dāng)前處于這一階段上的哪一點(diǎn)。這時(shí)的模型實(shí)際上已經(jīng)轉(zhuǎn)化成 了一個(gè)特殊的多段圖。用決策變量uk=0表示向右走，氣=1表示向上走， 則狀態(tài)轉(zhuǎn)移方程如下：x

2、k +l-uk e在寫規(guī)劃方程時(shí)，只要對(duì)兩條路徑走到同一個(gè)點(diǎn)的情況稍微處理一下， 減少可選的決策個(gè)數(shù)：+兩條邊均叫2min （工+1 （L兩條話長(zhǎng)尹如（岫即頃叫果）從這個(gè)例子可以看出，合理地劃分階段和選擇狀態(tài)可以給解題帶來方便。例 10 LITTLE SHOP OF FLOWERS(IOI99PROBLEMYou want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at l

3、east as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by int

4、egers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch /must be in a vase to the left of the vase containing bunch j whenever i j. Suppose, for example, you have a bunch of azaleas (id-n

5、umber=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnation

6、s. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers.Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer.

7、The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0.V A S E S12345Bunches1 (azaleas)723-5-24162 (begonias)521-410233 (carnations)-215-4-2020According to the table, azaleas, for example, would look great in vase 2, but they would look awful i

8、n vase 4.To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangemen

9、t.ASSUMPTIONS1 = F = 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F.F = V = 100 where V is the number of vases.-50 = A ,. = 50 where A ., is the aesthetic value obtained by putting/jthe flower bunch i into the vase j.INPUTThe input is a text file named flow

10、er.inp.The first line contains two numbers: F, V.The following F lines: Each of these lines contains V integers, so that A., is given as the jth number on the (i+1)st line of the input file.OUTPUTThe output must be a text file named flower.out consisting of two lines:The first line will contain the

11、sum of aesthetic values for your arrangement.The second line must present the arrangement as a list of F numbers, so that the kth number on this line identifies the vase in which the bunch k is put.EXAMPLEflower.inp:3 57 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 20flower.out:532 4 5EVALUATIONYour progra

12、m will be allowed to run 2 seconds.No partial credit can be obtained for a test case.本題雖然是IOI99中較為簡(jiǎn)單的一題，但其中大有文章可作。說它簡(jiǎn)單， 是因?yàn)樗行?，因此我們一眼便可看出這題應(yīng)該用動(dòng)態(tài)規(guī)劃來解決。但 是，如何動(dòng)態(tài)規(guī)劃呢？如何劃分階段，又如何選擇狀態(tài)呢？以花束的編號(hào)來劃分階段。在這里，第k階段布置第k束花，共有F束 花，有F+1個(gè)階段，增加第F+1階段是為了計(jì)算的方便；狀態(tài)變量Xkk表示第k束花所在的花瓶。而對(duì)于每一個(gè)狀態(tài)xk，決策uk就是第k+1 束花放置的花瓶號(hào)；最優(yōu)指標(biāo)函數(shù)fk(xk)表

13、示從第k束花到第n束花所 得到的最大美學(xué)值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F 是花的總數(shù)。狀態(tài)轉(zhuǎn)移方程為況十1規(guī)劃方程為Imax誑+1冬*三礦一局+L（A化 & ） + 7+1 （應(yīng)1 ）邊界條件為: 兀+1(勺44)二。, 事實(shí)上這是一個(gè)虛擬的邊界。最后要求的最大美學(xué)價(jià)值是方法1的規(guī)劃方程中的允許決策空間：xk+1MukMV-(F-k)+1比較麻煩，因 此有待改進(jìn)。還是以花束的編號(hào)來劃分階段，第k階段布置第k束花;狀態(tài)變量xk表示第k束花所在的花瓶；注意，這里我們考慮倒過來布置 花瓶，即從第F束花開始布置到第1束花。于是狀態(tài)變量uk表示第k-1 束花所在的花瓶；最優(yōu)

14、指標(biāo)fk(xk)表示從第一束花到第k束花所獲得的 美學(xué)價(jià)值；A(i,j)是花束i插在花瓶j中的美學(xué)值,V是花瓶總數(shù),F是花的 總數(shù)。則狀態(tài)轉(zhuǎn)移方程為：勤-1 =電規(guī)劃方程為：兀(&)二 max 0(*叫)+ 兀_(知_)增加的虛擬邊界條件為：席偵口)=。最后要求的最大美學(xué)價(jià)值是：牒礦E)可以看出，這種方法實(shí)質(zhì)上和方法1沒有區(qū)別，但是允許決策空間的表 示變得簡(jiǎn)單了。以花瓶的數(shù)目來劃分階段，第k個(gè)階段決定花瓶k中是否放花；狀態(tài)變 量xk表示前k個(gè)花瓶中放了多少花；而對(duì)于任意一個(gè)狀態(tài)xk，決策就 是第xk束花是否放在第k個(gè)花瓶中，用變量uk=1或0來表示。最優(yōu)指 標(biāo)函數(shù)fk(xk)表示前k個(gè)花瓶中插了 xk束花，所能取得的最大美學(xué)值。 注意，這里仍然是倒過來考慮。狀態(tài)轉(zhuǎn)移方程為靠-1 =xkuk規(guī)劃方程為1(%)二巴警以項(xiàng)去如十蛉用謚成)邊界條件為爪(0)二 0三種不同的方法都成功地解決了問題，只不過因?yàn)殡A段的劃分不同，狀 態(tài)的表示不同，決策的選擇