動(dòng)態(tài)規(guī)劃練習(xí)試題和解答

1、 .wd.動(dòng)態(tài)規(guī)劃練習(xí)題 題1 多米諾骨牌DOMINO問題描述：有一種多米諾骨牌是平面的，其正面被分成上下兩局部，每一局部的外表或者為空，或者被標(biāo)上1至6個(gè)點(diǎn)。現(xiàn)有一行排列在桌面上：頂行骨牌的點(diǎn)數(shù)之和為6+1+1+1=9；底行骨牌點(diǎn)數(shù)之和為1+5+3+2=11。頂行和底行的差值是2。這個(gè)差值是兩行點(diǎn)數(shù)之和的差的絕對(duì)值。每個(gè)多米諾骨牌都可以上下倒置轉(zhuǎn)換，即上部變?yōu)橄虏?，下部變?yōu)樯喜俊，F(xiàn)在的任務(wù)是，以最少的翻轉(zhuǎn)次數(shù)，使得頂行和底行之間的差值最小。對(duì)于上面這個(gè)例子，我們只需翻轉(zhuǎn)最后一個(gè)骨牌，就可以使得頂行和底行的差值為0，所以例子的答案為1。輸入格式：文件的第一行是一個(gè)整數(shù)n1=n=1000，表示有

2、n個(gè)多米諾骨牌在桌面上排成一行。接下來共有n行，每行包含兩個(gè)整數(shù)a、b0=a、b=6，中間用空格分開。第I+1行的a、b分別表示第I個(gè)多米諾骨牌的上部與下部的點(diǎn)數(shù)0表示空。輸出格式：只有一個(gè)整數(shù)在文件的第一行。這個(gè)整數(shù)表示翻動(dòng)骨牌的最少次數(shù)，從而使得頂行和底行的差值最小。題2 Perform巡回演出題目描述: Flute市的Phlharmoniker樂團(tuán)2000年準(zhǔn)備到Harp市做一次大型演出,本著普及古典音樂的目的,樂團(tuán)指揮L.Y.M準(zhǔn)備在到達(dá)Harp市之前先在周圍一些小城市作一段時(shí)間的巡回演出,此后的幾天里,音樂家們將每天搭乘一個(gè)航班從一個(gè)城市飛到另一個(gè)城市,最后才到達(dá)目的地Harp市(樂

3、團(tuán)可屢次在同一城市演出).由于航線的費(fèi)用和班次每天都在變,城市和城市之間都有一份循環(huán)的航班表,每一時(shí)間,每一方向,航班表循環(huán)的周期都可能不同.現(xiàn)要求尋找一張花費(fèi)費(fèi)用最小的演出表.輸入: 輸入文件包括假設(shè)干個(gè)場(chǎng)景.每個(gè)場(chǎng)景的描述由一對(duì)整數(shù)n(2<=n<=10)和k(1<=k<=1000)開場(chǎng),音樂家們要在這n個(gè)城市作巡回演出,城市用1.n標(biāo)號(hào),其中1是起點(diǎn)Flute市,n是終點(diǎn)Harp市,接下來有n*(n-1)份航班表,一份航班表一行,描述每對(duì)城市之間的航線和價(jià)格,第一組n-1份航班表對(duì)應(yīng)從城市1到其他城市(2,3,.n)的航班,接下的n-1行是從城市2到其他城市(1,3

4、,4.n)的航班,如此下去.每份航班又一個(gè)整數(shù)d(1<=d<=30)開場(chǎng),表示航班表循環(huán)的周期,接下來的d個(gè)非負(fù)整數(shù)表示1,2.d天對(duì)應(yīng)的兩個(gè)城市的航班的價(jià)格,價(jià)格為零表示那天兩個(gè)城市之間沒有航班.例如"3 75 0 80"表示第一天機(jī)票價(jià)格是75KOI,第二天沒有航班,第三天的機(jī)票是80KOI,然后循環(huán):第四天又是75KOI,第五天沒有航班,如此循環(huán).輸入文件由n=k=0的場(chǎng)景完畢.輸出:對(duì)每個(gè)場(chǎng)景如果樂團(tuán)可能從城市1出發(fā),每天都要飛往另一個(gè)城市,最后(經(jīng)過k天)抵達(dá)城市n,那么輸出這k個(gè)航班價(jià)格之和的最小值.如果不可能存在這樣的巡回演出路線,輸出0.樣例輸入

5、: 樣例輸出：3 6 4602 130 150 03 75 0 807 120 110 0 100 110 120 04 60 70 60 503 0 135 1402 70 802 32 0 701 800 0題3 復(fù)制書稿BOOKS 問題描述：假設(shè)有M本書編號(hào)為1，2，M，想將每本復(fù)制一份，M本書的頁(yè)數(shù)可能不同分別是P1，P2，PM。任務(wù)時(shí)將這M本書分給K個(gè)抄寫員K=M，每本書只能分配給一個(gè)抄寫員進(jìn)展復(fù)制，而每個(gè)抄寫員所分配到的書必須是連續(xù)順序的。意思是說，存在一個(gè)連續(xù)升序數(shù)列0=bob1b2<bk-1 <bk=m，這樣，第I號(hào)抄寫員得到的書稿是從bi-1+1到第bi本書。復(fù)制

6、工作是同時(shí)開場(chǎng)進(jìn)展的，并且每個(gè)抄寫員復(fù)制的速度都是一樣的。所以，復(fù)制完所有書稿所需時(shí)間取決于分配得到最多工作的那個(gè)抄寫員的復(fù)制時(shí)間。試找一個(gè)最優(yōu)分配方案，使分配給每一個(gè)抄寫員的頁(yè)數(shù)的最大值盡可能小如存在多個(gè)最優(yōu)方案，只輸出其中一種。輸入格式： 文件的第一行是兩個(gè)整數(shù)m和k (1=k=m=500)。第二行有m個(gè)整數(shù)P1，P2，Pm，這m個(gè)整數(shù)均為正整數(shù)且都不超過1000000。每?jī)蓚€(gè)整數(shù)之間用空格分開。輸出格式：文件有k行，每行有兩個(gè)正整數(shù)。整數(shù)之間用空格分開。第I行的兩個(gè)整數(shù)ai和bi，表示第I號(hào)抄寫員所分配得到的書稿的起始編號(hào)與終止編號(hào)。動(dòng)態(tài)規(guī)劃題參考程序：題1：解決問題：例子的上下局部之差

7、是6+1+1+1-1+5+3+2=6-1+1-5+1-3+1-2=-2，而翻轉(zhuǎn)最后一個(gè)骨牌后，上下之差變?yōu)?-1+1-5+1-3+2-1=0。由此看出，一個(gè)骨牌對(duì)翻轉(zhuǎn)策略造成影響的是上下兩數(shù)之差，骨牌上的數(shù)那么是次要的了。這么一來，便把骨牌的放置狀態(tài)由8個(gè)數(shù)字變?yōu)?個(gè)： 5 -4 -2 -1，翻轉(zhuǎn)時(shí)只需取該位數(shù)字的相反數(shù)就行了。在此題中，因?yàn)楦鞴桥频姆D(zhuǎn)順序沒有限定，所以不能按骨牌編號(hào)作為階段來劃分。怎么辦呢？考慮到隱含階段類型的問題可以按狀態(tài)最優(yōu)值的大小來劃分階段。于是，我們以骨牌序列上下兩局部的差值I作為狀態(tài)，把到達(dá)這一狀態(tài)的翻轉(zhuǎn)步數(shù)作為狀態(tài)值，記為fI。便有fI=minfI+j+1 -1

8、2=j<=12,j為偶數(shù)，且要求當(dāng)前狀態(tài)有差值為j/2的骨牌。這里，I不是無(wú)限增大或減小，其范圍取決于初始骨牌序列的數(shù)字差的和的大小。具體動(dòng)態(tài)規(guī)劃時(shí)，如例題，我們以f-2=0起步，根據(jù)骨牌狀態(tài)，進(jìn)展一次翻轉(zhuǎn)，可得到f-12=1，f6=1，f2=1，f0=1，由于出現(xiàn)了f0，因此程序便可以完畢，否那么將根據(jù)四個(gè)新狀態(tài)繼續(xù)擴(kuò)展，直至出現(xiàn)f0或者無(wú)法生成新狀態(tài)為止。注意：在各狀態(tài)，除記錄最少步數(shù)外，還需記錄到達(dá)這一狀態(tài)時(shí)各骨牌的放置情況；而當(dāng)?shù)竭_(dá)某一狀態(tài)發(fā)現(xiàn)已記錄有一種翻轉(zhuǎn)策略時(shí)，那么取步數(shù)較小的一種。程序如下：program domino;type tp=array1.6 of intege

9、r;var t:array1.6000 of tp; 記錄骨牌擺放狀態(tài)f:array-6000.6000 of integer;記錄到達(dá)某個(gè)差值的最少步數(shù)l:array1.6000 of integer;擴(kuò)展隊(duì)列tt:tp; i,j,n,m,x,y,ft,re:integer; f1,f2:text;procedure init;程序初始化begin assign(f1,'domino.dat'); reset(f1); assign(f2,'domino.out'); rewrite(f2); m:=0; ft:=0;re:=1;new(t1); fillch

10、ar(t1,sizeof(t1),0); fillchar(f,sizeof(f),0); fillchar(tt,sizeof(tt),0); readln(f1,n); for i:=1 to n do begin readln(f1,x,y); if x<>y then begin x:=x-y; inc(m,x); inc(ttabs(x); if x>0 then inc(t1x); end; end; if m=0 then begin writeln(f2,0); close(f2); halt; end; 處理步數(shù)為零的情況 l1:=m; fm:=1;end;

11、procedure main;主過程begin repeatfor ft:=ft+1 to re do以步數(shù)為階段擴(kuò)展?fàn)顟B(tài) begin x:=lft; for i:=1 to 6 do 不同差值的六種情況 begin if x<6 then if (tfti<tti)and(fx+i*2=0) then begin inc(re);lre:=x+i*2; flre:=fx+1; if lre=0 then 找到解便打印 begin writeln(f2,flre-1); close(f2); halt; end; new(tre); tre:=tft; inc(trei); end

12、; 差值增加 if x>-6 then if (tfti>0)and(fx-i*2=0) then begin inc(re);lre:=x-i*2; flre:=fx+1; if lre=0 then 找到解便打印 begin writeln(f2,flre-1); close(f2); halt; end; new(tre); tre:=tft; dec(trei); end; 差值減少 end; end; until ft=re; for i:=1 to 6 do if (fi>0)or(f-i>0) then begin if (f-i>0)and(fi=

13、0)or(f-i<fi) then x:=f-i else x:=fi; writeln(f2,x-1); i:=6; end; close(f2); 骨牌上下兩行點(diǎn)數(shù)之和的絕對(duì)值不為零end;begin init; main;end.題2：初看這道題,很容易便可以想到動(dòng)態(tài)規(guī)劃,因?yàn)榈趚天在第y個(gè)地方的最優(yōu)值只與第x-1天有關(guān),符合動(dòng)態(tài)規(guī)劃的無(wú)后效性原那么,即只與上一個(gè)狀態(tài)相關(guān)聯(lián),而某一天x航班價(jià)格不難求出S=C(x-1) mod m +1.我們用天數(shù)和地點(diǎn)來規(guī)劃用一個(gè)數(shù)組A1.1000,1.10來存儲(chǔ),Ai,j表示第i天到達(dá)第j個(gè)城市的最優(yōu)值,Ci,j,l表示i城市與j城市間第l天航班

14、價(jià)格,那么Ai,j=MinAi-1,l+Cl,j,i (l=1.n且Cl,j,i<>0),動(dòng)態(tài)規(guī)劃方程一出,盡可以放懷大笑了.示范程序:program perform_hh;var f,fout:text; p,l,i,j,n,k:integer; a:array 1.1000,1.10 of integer; 動(dòng)態(tài)規(guī)劃數(shù)組 c:array 1.10,1.10 of record 航班價(jià)格數(shù)組 num:integer; t:array 1.30 of integer; end; e:array 1.1000 of integer;procedure work;begin 人工賦第一

15、天各城市最優(yōu)值 for i:=1 to n do begin if c1,i.t1<>0 then a1,i:=c1,i.t1; end; for i:=2 to k do begin for j:=1 to n do begin for l:=1 to n do begin if (j<>l) and (cl,j.t(i-1) mod cl,j.num+1<>0) 判斷存在航班 and (ai,j=0) or (ai-1,l+cl,j.t(i-1) mod cl,j.num+1<ai,j) 判斷比當(dāng)前解優(yōu) then ai,j:=ai-1,l+cl,j

16、.t(i-1) mod cl,j.num+1; 賦值 end; end; end; ep:=ak,n; 第p個(gè)場(chǎng)景的最優(yōu)值end;procedure readfile; 讀文件begin assign(f,'PERFORM.DAT'); reset(f); assign(fout,'PERFORM.OUT'); rewrite(fout); readln(f,n,k); p:=0; while (n<>0) and (k<>0) do begin p:=p+1; fillchar(c,sizeof(c),0); fillchar(a,si

17、zeof(a),0); for i:=1 to n do begin for j:=1 to i-1 do begin read(f,ci,j.num); for l:=1 to ci,j.num do read(f,ci,j.tl); end; for j:=i+1 to n do begin read(f,ci,j.num); for l:=1 to ci,j.num do read(f,ci,j.tl); end; end; work; readln(f,n,k); end; 輸出各個(gè)場(chǎng)景的解 for i:=1 to p-1 do writeln(fout,ei); write(fout

18、,ep); close(f); close(fout);end;begin readfile;end.題3：解決問題：該題中M本書是順序排列的，K個(gè)抄寫員選擇數(shù)也是順序且連續(xù)的。不管以書的編號(hào)，還是以抄寫員標(biāo)號(hào)作為參變量劃分階段，都符合策略的最優(yōu)化原理和無(wú)后效性?？紤]到K=M，以抄寫員編號(hào)來劃分會(huì)方便些。設(shè)FI，J為前I個(gè)抄寫員復(fù)制前J本書的最小“頁(yè)數(shù)最大數(shù)。于是便有FI，J=MIN FI-1，V，TV+1，J 1=I=K，I=J=M-K+I，I-1=V=J-1。 其中TV+1，J表示從第V+1本書到第J本書的頁(yè)數(shù)和。起步時(shí)F1，1=P1。觀察函數(shù)遞推式，發(fā)現(xiàn)FI階段只依賴于FI-1階段的狀態(tài)

19、值，編程時(shí)可令數(shù)組F的范圍為01,1M，便于縮小空間復(fù)雜度。程序如下：program books;type tp=array1.500 of integer; tc=array1.500 of longint;var c:array1.500 of tp; 記錄路徑f:array0.1 of tc;狀態(tài)值t:tc;書本頁(yè)數(shù)和cc:tp;鏈接路徑 i,j,v,k,m,x,y,min,p1,p2:longint; f1,f2:text;procedure init;輸入局部begin assign(f1,'books.dat'); reset(f1); assign(f2,'books.out'); rewrite(f2); readln(f1,m,k); if k=1 then begin writeln(f2,1,' ',m); close(f2); halt; end; 當(dāng)k=1時(shí),作特殊處理 for i:=1 to m do begin read(f1,j); if i=1 then t1:=j else ti:=ti-1+j; 累加頁(yè)數(shù) end; for i:=1 to k do new(ci);end;procedure main;