4種常見(jiàn)的動(dòng)態(tài)規(guī)劃模型

..例談四種常見(jiàn)的動(dòng)態(tài)規(guī)劃模型動(dòng)態(tài)規(guī)劃是解決多階段決策最優(yōu)化問(wèn)題的一種思想方法,本文主要結(jié)合一些例題,把一些常見(jiàn)的動(dòng)態(tài)規(guī)劃模型,進(jìn)行歸納總結(jié)?！惨弧⒈嘲Ｐ涂捎脛?dòng)態(tài)規(guī)劃解決的背包問(wèn)題,主要有01背包和完全背包。對(duì)于背包的類(lèi)型,這邊就做個(gè)簡(jiǎn)單的描述：n個(gè)物品要放到一個(gè)背包里,背包有個(gè)總?cè)萘縨,每個(gè)物品都有一個(gè)體積w[i]和價(jià)值v[i],問(wèn)如何裝這些物品,使得背包里放的物品價(jià)值最大。這類(lèi)型的題目,狀態(tài)表示為：f[j]表示背包容量不超過(guò)j時(shí)能夠裝的最大價(jià)值,則狀態(tài)轉(zhuǎn)移方程為：f[j]:=max{f[j-w[i]]+v[i]},邊界：f[0]:=0;簡(jiǎn)單的程序框架為：beginreadln<m,n>;fori:=1tondoreadln<w[i],v[i]>;f[0]:=0;fori:=1tomdoforj:=1tondobeginifi>=w[j]thent:=f[i-w[j]]+v[j];ift>f[i]thenf[i]:=t;end;writeln<f[m]>;end.這類(lèi)型的題目應(yīng)用挺廣的〔noip1996提高組第4題,noip2001普及組裝箱問(wèn)題,noip2005普及組采藥等,下面一個(gè)例子,也是背包模型的簡(jiǎn)單轉(zhuǎn)化。貨幣系統(tǒng)<money>[問(wèn)題描述]母牛們不但創(chuàng)建了他們自己的政府而且選擇了建立了自己的貨幣系統(tǒng)。他們對(duì)貨幣的數(shù)值感到好奇。傳統(tǒng)地,一個(gè)貨幣系統(tǒng)是由1,5,10,20或25,50,100的單位面值組成的。母牛想知道用貨幣系統(tǒng)中的貨幣來(lái)構(gòu)造一個(gè)確定的面值,有多少種不同的方法。使用一個(gè)貨幣系統(tǒng){1,2,5,10,..}產(chǎn)生18單位面值的一些可能的方法是:18×1,9×2,8×2+2×1,3×5+2+1等等其它。寫(xiě)一個(gè)程序來(lái)計(jì)算有多少種方法用給定的貨幣系統(tǒng)來(lái)構(gòu)造一個(gè)確定的面值。[輸入格式]貨幣系統(tǒng)中貨幣的種類(lèi)數(shù)目是v<1≤v≤25>；要構(gòu)造的面值是n<1≤n≤10,000>；第1行:二個(gè)整數(shù),v和n；第2..v+1行：可用的貨幣v個(gè)整數(shù)<每行一個(gè)>。[輸出格式]單獨(dú)的一行包含那個(gè)可能的構(gòu)造的方案數(shù)。[輸入樣例]310125[輸出樣例]10[分析]：此題是個(gè)背包模型,只是問(wèn)題的解是構(gòu)造方案數(shù),設(shè)w[j]為第j種幣值,狀態(tài)f[i]：構(gòu)造面值為i時(shí)可能的方案數(shù),則狀態(tài)轉(zhuǎn)移方程為：f[i]:=∑f[i-w[j]],i>=w[j],邊界：f[0]:=1;f[n]即為問(wèn)題的解。注意：由于此題的數(shù)據(jù)規(guī)模比較大,所以要用到高精度加法,估計(jì)最大的數(shù)據(jù)可以達(dá)到73位,為節(jié)約程序時(shí)間和空間效率,還采用了萬(wàn)進(jìn)制的高精度加法。參考程序如下：varf:array[0..10000,1..20]ofinteger;long:array[0..10000]ofinteger;//存儲(chǔ)位數(shù)w:array[0..25]ofinteger;n,m,i,j,k:integer;procedureadd<r,t:integer>;//萬(wàn)進(jìn)制高精度加vari,k:integer;beginiflong[t]<long[r]thenlong[t]:=long[r];k:=0;fori:=1tolong[t]dobeginf[t,i]:=<f[t,i]+f[r,i]+k>;k:=f[t,i]div10000;//每一個(gè)存4位,萬(wàn)進(jìn)制,這樣省時(shí)省空間f[t,i]:=f[t,i]mod10000;end;whilek>0do//進(jìn)位處理begininc<long[t]>;f[t,long[t]]:=kmod10000;k:=kdiv10000;end;end;proceduremain;vari,j:integer;beginf[0,1]:=1;long[0]:=1;fori:=1tomdoforj:=w[i]tondoadd<j-w[i],j>;write<f[n,long[n]]>;//輸出答案,由于每個(gè)存4位,所以有時(shí)需要補(bǔ)零fori:=long[n]-1downto1dobeginiff[n,i]<10thenwrite<'000'>elseiff[n,i]<100thenwrite<'00'>elseiff[n,i]<1000thenwrite<'0'>;write<f[n,i]>;end;end;beginassign<input,'money.in'>;reset<input>;assign<output,'money.out'>;rewrite<output>;readln<m,n>;fori:=1tomdoreadln<w[i]>;main;close<input>;close<output>;end.〔二、資源分配模型資源分配模型的動(dòng)態(tài)規(guī)劃,這類(lèi)型的題目一般是：給定m個(gè)資源,分配給n個(gè)部門(mén),第i個(gè)部門(mén)獲得j個(gè)資源有個(gè)盈利值,問(wèn)如何分配這m個(gè)資源能使獲得的盈利最大,求最大盈利。這類(lèi)型的題目一般用資源數(shù)做狀態(tài),數(shù)組f[i,j]表示前個(gè)i個(gè)部門(mén)分配j個(gè)資源的最大盈利,則狀態(tài)轉(zhuǎn)移方程為：f[i,j]:=max{f[i-1,k]+value[i,j-k]}<0<=k<=j>程序框架如下：vari,j,k:longint;beginfori:=1tondoforj:=0tomdofork:=0tojdoiff[i-1,k]+value[i,j-k]>f[i,j]thenf[i,j]:=f[i-1,k]+value[i,j-k];writeln<f[n,m]>;end;資源分配類(lèi)型典型應(yīng)用是花店櫥窗<flower.pas>設(shè)置,沒(méi)做過(guò)的同學(xué)可以自己去練習(xí)一下,下面的一個(gè)例題,也是此類(lèi)型的轉(zhuǎn)換。[問(wèn)題描述]農(nóng)夫ion放完馬以后,需要把馬兒關(guān)回馬廄。為了做好這件事,ion讓馬排成一行跟著他入馬廄。他想出了一個(gè)就近入廄的辦法：讓前p1匹馬進(jìn)入第一個(gè)馬廄,然后的p2匹馬進(jìn)入第二個(gè)馬廄,如此類(lèi)推。而且,他不想讓任何一個(gè)馬廄〔共k個(gè)留空,還有所有的馬都進(jìn)入馬廄。已知ion只有黑色和白色兩種顏色的馬,然而并不是所有的馬都能相處融洽。假如有i匹黑馬和j匹白馬同在一個(gè)馬廄,那么它們之間的不愉快系數(shù)為i*j。馬廄總的不愉快系數(shù)等于k個(gè)馬廄的不愉快系數(shù)之和。請(qǐng)幫忙把n匹馬按順序放入k個(gè)馬廄中〔即求一種p1,p2…的安排方案,使得總的不愉快系數(shù)最小。[輸入格式]輸入第一行為一個(gè)n和k；〔n<=100,k<=n;輸入第二行為n個(gè)數(shù)0和1,0表示白馬,1表示黑馬[輸出格式]一行,最小的不愉快系數(shù)。樣例輸入32101樣例輸出1分析：設(shè)f[i,j]：表示將前i匹馬放入前j個(gè)馬廄,得到的最小不愉快系數(shù)。w[i,j]：表示將第i至第j匹馬放入同一個(gè)馬廄所得到的不愉快系數(shù)。狀態(tài)轉(zhuǎn)移方程為：f[i,j]=min<f[k,j-1]+w[k+1,i]>{j-1<=k<i}注意邊界條件：f[i,1]:=w[1,i];f[i,i]:=0;參考程序如下：constmaxn=100;maxk=100;varf:array[1..maxn,1..maxk]oflongint;w:array[1..maxn,1..maxn]oflongint;a:array[1..maxn]oflongint;i,j,k,k1,n,s1,s2:integer;beginassign<input,'horse.in'>;reset<input>;assign<output,’horse.out’>;rewrite<output>;readln<n,k>;fori:=1tondoread<a[i]>;fori:=1tondo//求w[i,j]forj:=itondobegins1:=0;s2:=0;fork1:=itojdoifa[k1]=0theninc<s1>elseinc<s2>;w[i,j]:=s1*s2;end;fori:=1tondo//初始化forj:=1tokdof[i,j]:=maxint;fori:=1tondo//邊界條件beginf[i,i]:=0;f[i,1]:=w[1,i];end;forj:=1tokdo//動(dòng)規(guī)過(guò)程fori:=jtondofork1:=j-1toi-1doif<k1>0>and<j-1>=1>and<f[k1,j-1]<>maxint>thenf[i,j]:=min<f[k1,j-1]+w[k1+1,i],f[i,j]>writeln<f[n,k]>;close<input>;close<output>;end.〔三、區(qū)間類(lèi)模型區(qū)間類(lèi)模型的動(dòng)態(tài)規(guī)劃,一般是要求整段區(qū)間的最優(yōu)值,子問(wèn)題一般是把區(qū)間分成兩個(gè)子區(qū)間。一般用二維數(shù)組表示狀態(tài),例如f[i,j]表示從i到j(luò)的最優(yōu)值。則狀態(tài)轉(zhuǎn)移方程就是跟子區(qū)間之間的關(guān)系,下面我們用個(gè)典型的例子講解這個(gè)模型的應(yīng)用。[問(wèn)題描述]給定一個(gè)具有n〔n<50個(gè)頂點(diǎn)〔從1到n編號(hào)的凸多邊形,每個(gè)頂點(diǎn)的權(quán)均已知。問(wèn)如何把這個(gè)凸多邊形劃分成n-2個(gè)互不相交的三角形,使得這些三角形頂點(diǎn)的權(quán)的乘積之和最小？輸入文件：第一行頂點(diǎn)數(shù)n第一行n個(gè)頂點(diǎn)〔從1到n的權(quán)值輸出格式：最小的和的值,各三角形組成的方式輸入示例：5122123245231輸出示例：theminimumis:12214884theformationof3triangle:345,153,123分析:這是一道很典型的區(qū)間模型動(dòng)態(tài)規(guī)劃問(wèn)題。設(shè)f[i,j]〔i<j表示從頂點(diǎn)i到頂點(diǎn)j的凸多邊形三角剖分后所得到的最大乘積,我們可以得到下面的動(dòng)態(tài)轉(zhuǎn)移方程：f[i,j]=min{f[i,k]+f[k,j]+s[i]*s[j]*s[k]}<i<k<j>目標(biāo)狀態(tài)為：f[1,n]但我們可以發(fā)現(xiàn),由于這里為乘積之和,在輸入數(shù)據(jù)較大時(shí)有可能超過(guò)長(zhǎng)整形甚至實(shí)形的范圍,所以我們還需用高精度計(jì)算,但這是基本功,程序中就沒(méi)有寫(xiě)了,請(qǐng)讀者自行完成。參考程序vars:array[1..50]ofinteger;f:array[1..50,1..50]ofcomp;d:array[1..50,1..50]ofbyte;n:integer;procedureinit;vari:integer;beginreadln<n>;fori:=1tondoread<s[i]>;end;proceduredp;//動(dòng)態(tài)規(guī)劃vari,j,k:integer;beginfori:=1tondoforj:=i+1tondof[i,j]:=maxlongint;//賦初始值fori:=n-2downto1doforj:=i+2tondofork:=i+1toj-1doif<f[i,j]>f[i,k]+f[k,j]+s[i]*s[j]*s[k]>thenbeginf[i,j]:=f[i,k]+f[k,j]+s[i]*s[j]*s[k];d[i,j]:=k;//記錄父節(jié)點(diǎn)end;end;procedureprint<i,j:integer>;//輸出每個(gè)三角形beginifj=i+1thenexit;write<',',i,'',j,'',d[i,j]>;out<i,d[i,j]>;out<d[i,j],j>;end;procedureout;//輸出信息beginwriteln<'theminimumis:',f[1,n]:0:0>;writeln<'theformationof',n-2,'triangle:'>;write<1,'',n,''d[1,n]>;out<1,d[1,n]>;out<d[1,n],n>;end;begin//主程序init;dp;out;end.區(qū)間模型的動(dòng)態(tài)規(guī)劃,在歷屆的信息學(xué)競(jìng)賽,應(yīng)用非常廣泛,如noi95的石子合并問(wèn)題,noip2003普及組的數(shù)字游戲,noip2006提高組第1題等。〔四樹(shù)型動(dòng)態(tài)規(guī)劃模型上面三種動(dòng)態(tài)規(guī)劃都是建立在線(xiàn)性結(jié)構(gòu)上的,有順推和逆推兩種方法,下面我們介紹一種建立在‘樹(shù)’這個(gè)數(shù)據(jù)結(jié)構(gòu)上的動(dòng)態(tài)規(guī)劃——樹(shù)型動(dòng)態(tài)規(guī)劃模型。樹(shù)型動(dòng)態(tài)規(guī)劃是建立在樹(shù)結(jié)構(gòu)上的動(dòng)態(tài)規(guī)劃,所以階段很明顯,一般是通過(guò)孩子節(jié)點(diǎn)的最優(yōu)值推出父親節(jié)點(diǎn)的最優(yōu)值。一般以節(jié)點(diǎn)及相關(guān)信息為狀態(tài),動(dòng)態(tài)轉(zhuǎn)移方程是也是根據(jù)父親節(jié)點(diǎn)跟孩子節(jié)點(diǎn)之間關(guān)系來(lái)建立的。通過(guò)根的子節(jié)點(diǎn)傳遞有用的信息給根,完后根得出最優(yōu)解的過(guò)程。下面結(jié)合一些例子,來(lái)介紹它的一般解法。例1:[問(wèn)題描述]給你一棵樹(shù)T=<V,E,W>,其中V表示頂點(diǎn)集且|V|=n,E表示邊集。如果<v,u>屬于E,則W<v,u>表示<v,u>的長(zhǎng)度。求兩點(diǎn)v,u,使得它們之間的路徑總長(zhǎng)度最長(zhǎng)。你只需要輸出這個(gè)最長(zhǎng)長(zhǎng)度即可。輸入格式:輸入第1行為n和邊數(shù)e接下來(lái)e行,每行三個(gè)數(shù)v,u,和w輸出格式:最長(zhǎng)長(zhǎng)度輸入樣例6512201340145025103610輸出樣例100分析：認(rèn)真審題,其實(shí)此題是要在帶權(quán)樹(shù)上求最長(zhǎng)鏈,一棵有根樹(shù)的最長(zhǎng)鏈,可能出現(xiàn)如上圖的兩種情況設(shè)dep<i>表示以節(jié)點(diǎn)i為根的子樹(shù)的最大深度。F<i>表示以節(jié)點(diǎn)i為根的子樹(shù)中,包含節(jié)點(diǎn)i的最長(zhǎng)鏈長(zhǎng)度我們有:dep<i>=max{dep<j>+w<i,j>},其中j是i的子節(jié)點(diǎn)F<i>=max{dep<i>,dep<j>+w<i,j>+dep<k>+w<i,k>},其中j,k是i的子節(jié)點(diǎn),且j<>k不難發(fā)現(xiàn),我們的狀態(tài)轉(zhuǎn)移方程是按照從下至上的順序計(jì)算的。做一遍DFS遍歷,在回朔的時(shí)候分別計(jì)算dep和F的值,關(guān)于F值的計(jì)算：由于節(jié)點(diǎn)j和k之間沒(méi)有關(guān)聯(lián),所以我們只需要選擇兩個(gè)<dep<j>+w<i,j>>最大的子節(jié)點(diǎn)進(jìn)行累加即可。參考程序constmaxn=100;varn,v,ans:integer;w:array[0..maxn,0..maxn]ofinteger;dep:array[1..maxn]ofinteger;used:array[1..maxn]ofboolean;procedureinit;vari,j,x,y:integer;beginreadln<n,v>;fori:=0tondoforj:=0tondow[i,j]:=-1;fori:=1tovdobeginreadln<x,y,w[x,y]>;w[y,x]:=w[x,y];end;fillchar<used,sizeof<used>,true>;used[1]:=false;ans:=0;end;proceduredfs<x:integer>;//求dep和f的過(guò)程vari,max1,max2:integer;begindep[x]:=0;max1:=0;max2:=0;fori:=1tondoif<w[x,i]<>-1>and<used[i]>thenbeginused[i]:=false;dfs<i>;ifdep[i]+w[x,i]>=dep[x]thenbegindep[x]:=dep[i]+w[x,i];max2:=max1;max1:=dep[x];endelseifdep[i]+w[x,i]>max2thenmax2:=dep[i]+w[x,i];end;ifdep[x]>ansthenans:=dep[x];ifmax1+max2>ansthenans:=max1+max2;end;begininit;dfs<1>;writeln<ans>;end.例2、ural1018二叉蘋(píng)果樹(shù)有一棵蘋(píng)果樹(shù),如果樹(shù)枝有分叉,一定是分2叉〔就是說(shuō)沒(méi)有只有1個(gè)兒子的結(jié)點(diǎn)這棵樹(shù)共有N個(gè)結(jié)點(diǎn)〔葉子點(diǎn)或者樹(shù)枝分叉點(diǎn),編號(hào)為1-N,樹(shù)根編號(hào)一定是1。我們用一根樹(shù)