動態(tài)規(guī)劃練習(xí)題及解答1

1、動態(tài)規(guī)劃練習(xí)題動態(tài)規(guī)劃練習(xí)題[題1]多米諾骨牌（DOMINO）問題描述：有一種多米諾骨牌是平面的，其正面被分成上下兩部分，每一部分的表面或者為空，或者被標(biāo)上1至6個點?，F(xiàn)有一行排列在桌面上：頂行骨牌的點數(shù)之和為6111=9；底行骨牌點數(shù)之和為1532=11。頂行和底行的差值是2。這個差值是兩行點數(shù)之和的差的絕對值。每個多米諾骨牌都可以上下倒置轉(zhuǎn)換，即上部變?yōu)橄虏?，下部變?yōu)樯喜俊，F(xiàn)在的任務(wù)是，以最少的翻轉(zhuǎn)次數(shù)，使得頂行和底行之間的差值最小

2、。對于上面這個例子，我們只需翻轉(zhuǎn)最后一個骨牌，就可以使得頂行和底行的差值為0，所以例子的答案為1。輸入格式：文件的第一行是一個整數(shù)n（1〈=n〈=1000〉，表示有n個多米諾骨牌在桌面上排成一行。接下來共有n行，每行包含兩個整數(shù)a、b（0〈=a、b〈=6，中間用空格分開〉。第I1行的a、b分別表示第I個多米諾骨牌的上部與下部的點數(shù)（0表示空）。輸出格式：只有一個整數(shù)在文件的第一行。這個整數(shù)表示翻動骨牌的最少次數(shù)，從而使得頂行和底行的差值

3、最小。[題2]Perfm巡回演出題目描述:Flute市的Phlharmoniker樂團2000年準(zhǔn)備到Harp市做一次大型演出本著普及古典音樂的目的樂團指揮L.Y.M準(zhǔn)備在到達(dá)Harp市之前先在周圍一些小城市作一段時間的巡回演出此后的幾天里音樂家們將每天搭乘一個航班從一個城市飛到另一個城市最后才到達(dá)目的地Harp市(樂團可多次在同一城市演出).由于航線的費用和班次每天都在變城市和城市之間都有一份循環(huán)的航班表每一時間每一方向航班表循環(huán)的周

4、期都可能不同.現(xiàn)要求尋找一張花費費用最小的演出表.輸入:輸入文件包括若干個場景.每個場景的描述由一對整數(shù)n(2=n=10)和k(1=k=1000)開始音樂家們要在這n個城市作巡回演出城市用1..n標(biāo)號其中1是起點Flute市n是終點Harp市接下來有n(n1)份航班表一份航班表一行描述每對城市之間的航線和價格第一組n1份航班表對應(yīng)從城市1到其他城市(23...n)的航班接下的n1行是從城市2到其他城市(134...n)的航班如此下去.每

5、份航班又一個整數(shù)d(1=d=30)開始表示航班表循環(huán)的周期接下來的d個非負(fù)整數(shù)表示12...d天對應(yīng)的兩個城市的航班的價格價格為零表示那天兩個城市之間沒有航班.例如“375080“表示第一天機票價格是75KOI第二天沒有航班第三天的機票是80KOI然后循環(huán):第四天又是75KOI第五天沒有航班如此循環(huán).輸入文件由n=k=0的場景結(jié)束.輸出:對每個場景如果樂團可能從城市1出發(fā)每天都要飛往另一個城市最后(經(jīng)過k天)抵達(dá)城市n則輸出這k個航班價

6、格之和的最小值.如果不可能存在這樣的巡回演出路線輸出0.樣例輸入:樣例輸出：動態(tài)規(guī)劃題參考程序：動態(tài)規(guī)劃題參考程序：題1：解決問題：例子的上下部分之差是6111（1532）=（61）（15）（13）（12）=2，而翻轉(zhuǎn)最后一個骨牌后，上下之差變?yōu)椋?1）（15）（13）（21）=0。由此看出，一個骨牌對翻轉(zhuǎn)策略造成影響的是上下兩數(shù)之差，骨牌上的數(shù)則是次要的了。這么一來，便把骨牌的放置狀態(tài)由8個數(shù)字變?yōu)?個：5421，翻轉(zhuǎn)時只需取該位數(shù)字

7、的相反數(shù)就行了。在本題中，因為各骨牌的翻轉(zhuǎn)順序沒有限定，所以不能按骨牌編號作為階段來劃分。怎么辦呢？考慮到隱含階段類型的問題可以按狀態(tài)最優(yōu)值的大小來劃分階段。于是，我們以骨牌序列上下兩部分的差值I作為狀態(tài)，把達(dá)到這一狀態(tài)的翻轉(zhuǎn)步數(shù)作為狀態(tài)值，記為f（I）。便有f（I）=minf（Ij）1（12〈=j=12j為偶數(shù)，且要求當(dāng)前狀態(tài)有差值為j2的骨牌）。這里，I不是無限增大或減小，其范圍取決于初始骨牌序列的數(shù)字差的和的大小。具體動態(tài)規(guī)劃時，

8、如例題，我們以f（2）=0起步，根據(jù)骨牌狀態(tài)，進(jìn)行一次翻轉(zhuǎn)，可得到f（12）=1，f（6）=1，f（2）=1，f（0）=1，由于出現(xiàn)了f（0），因此程序便可以結(jié)束，否則將根據(jù)四個新狀態(tài)繼續(xù)擴展，直至出現(xiàn)f（0）或者無法生成新狀態(tài)為止。注意：在各狀態(tài)，除記錄最少步數(shù)外，還需記錄到達(dá)這一狀態(tài)時各骨牌的放置情況；而當(dāng)?shù)竭_(dá)某一狀態(tài)發(fā)現(xiàn)已記錄有一種翻轉(zhuǎn)策略時，則取步數(shù)較小的一種。程序如下：programdominotypetp=array[1..

9、6]ofintegervart:array[1..6000]of^tp記錄骨牌擺放狀態(tài)f:array[6000..6000]ofinteger記錄達(dá)到某個差值的最少步數(shù)l:array[1..6000]ofinteger擴展隊列tt:tpijnmxyftre:integerf1f2:textprocedureinit程序初始化beginassign(f1domino.dat)reset(f1)assign(f2domino.out)rew