..例談四種常見的動態(tài)規(guī)劃模型動態(tài)規(guī)劃是解決多階段決策最優(yōu)化問題的一種思想方法,本文主要結(jié)合一些例題,把一些常見的動態(tài)規(guī)劃模型,進行歸納總結(jié)?！惨?、背包模型可用動態(tài)規(guī)劃解決的背包問題,主要有01背包和完全背包。對于背包的類型,這邊就做個簡單的描述：n個物品要放到一個背包里,背包有個總?cè)萘縨,每個物品都有一個體積w[i]和價值v[i],問如何裝這些物品,使得背包里放的物品價值最大。這類型的題目,狀態(tài)表示為：f[j]表示背包容量不超過j時能夠裝的最大價值,則狀態(tài)轉(zhuǎn)移方程為：f[j]:=max{f[j-w[i]]+v[i]},邊界：f[0]:=0;簡單的程序框架為：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.這類型的題目應用挺廣的〔noip1996提高組第4題,noip2001普及組裝箱問題,noip2005普及組采藥等,下面一個例子,也是背包模型的簡單轉(zhuǎn)化。貨幣系統(tǒng)<money>[問題描述]母牛們不但創(chuàng)建了他們自己的政府而且選擇了建立了自己的貨幣系統(tǒng)。他們對貨幣的數(shù)值感到好奇。傳統(tǒng)地,一個貨幣系統(tǒng)是由1,5,10,20或25,50,100的單位面值組成的。母牛想知道用貨幣系統(tǒng)中的貨幣來構(gòu)造一個確定的面值,有多少種不同的方法。使用一個貨幣系統(tǒng){1,2,5,10,..}產(chǎn)生18單位面值的一些可能的方法是:18×1,9×2,8×2+2×1,3×5+2+1等等其它。寫一個程序來計算有多少種方法用給定的貨幣系統(tǒng)來構(gòu)造一個確定的面值。[輸入格式]貨幣系統(tǒng)中貨幣的種類數(shù)目是v<1≤v≤25>；要構(gòu)造的面值是n<1≤n≤10,000>；第1行:二個整數(shù),v和n；第2..v+1行：可用的貨幣v個整數(shù)<每行一個>。[輸出格式]單獨的一行包含那個可能的構(gòu)造的方案數(shù)。[輸入樣例]310125[輸出樣例]10[分析]：此題是個背包模型,只是問題的解是構(gòu)造方案數(shù),設w[j]為第j種幣值,狀態(tài)f[i]：構(gòu)造面值為i時可能的方案數(shù),則狀態(tài)轉(zhuǎn)移方程為：f[i]:=∑f[i-w[j]],i>=w[j],邊界：f[0]:=1;f[n]即為問題的解。注意：由于此題的數(shù)據(jù)規(guī)模比較大,所以要用到高精度加法,估計最大的數(shù)據(jù)可以達到73位,為節(jié)約程序時間和空間效率,還采用了萬進制的高精度加法。參考程序如下：varf:array[0..10000,1..20]ofinteger;long:array[0..10000]ofinteger;//存儲位數(shù)w:array[0..25]ofinteger;n,m,i,j,k:integer;procedureadd<r,t:integer>;//萬進制高精度加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;//每一個存4位,萬進制,這樣省時省空間f[t,i]:=f[t,i]mod10000;end;whilek>0do//進位處理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]]>;//輸出答案,由于每個存4位,所以有時需要補零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.〔二、資源分配模型資源分配模型的動態(tài)規(guī)劃,這類型的題目一般是：給定m個資源,分配給n個部門,第i個部門獲得j個資源有個盈利值,問如何分配這m個資源能使獲得的盈利最大,求最大盈利。這類型的題目一般用資源數(shù)做狀態(tài),數(shù)組f[i,j]表示前個i個部門分配j個資源的最大盈利,則狀態(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;資源分配類型典型應用是花店櫥窗<flower.pas>設置,沒做過的同學可以自己去練習一下,下面的一個例題,也是此類型的轉(zhuǎn)換。[問題描述]農(nóng)夫ion放完馬以后,需要把馬兒關(guān)回馬廄。為了做好這件事,ion讓馬排成一行跟著他入馬廄。他想出了一個就近入廄的辦法：讓前p1匹馬進入第一個馬廄,然后的p2匹馬進入第二個馬廄,如此類推。而且,他不想讓任何一個馬廄〔共k個留空,還有所有的馬都進入馬廄。已知ion只有黑色和白色兩種顏色的馬,然而并不是所有的馬都能相處融洽。假如有i匹黑馬和j匹白馬同在一個馬廄,那么它們之間的不愉快系數(shù)為i*j。馬廄總的不愉快系數(shù)等于k個馬廄的不愉快系數(shù)之和。請幫忙把n匹馬按順序放入k個馬廄中〔即求一種p1,p2…的安排方案,使得總的不愉快系數(shù)最小。[輸入格式]輸入第一行為一個n和k；〔n<=100,k<=n;輸入第二行為n個數(shù)0和1,0表示白馬,1表示黑馬[輸出格式]一行,最小的不愉快系數(shù)。樣例輸入32101樣例輸出1分析：設f[i,j]：表示將前i匹馬放入前j個馬廄,得到的最小不愉快系數(shù)。w[i,j]：表示將第i至第j匹馬放入同一個馬廄所得到的不愉快系數(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//動規(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ū)間類模型區(qū)間類模型的動態(tài)規(guī)劃,一般是要求整段區(qū)間的最優(yōu)值,子問題一般是把區(qū)間分成兩個子區(qū)間。一般用二維數(shù)組表示狀態(tài),例如f[i,j]表示從i到j的最優(yōu)值。則狀態(tài)轉(zhuǎn)移方程就是跟子區(qū)間之間的關(guān)系,下面我們用個典型的例子講解這個模型的應用。[問題描述]給定一個具有n〔n<50個頂點〔從1到n編號的凸多邊形,每個頂點的權(quán)均已知。問如何把這個凸多邊形劃分成n-2個互不相交的三角形,使得這些三角形頂點的權(quán)的乘積之和最??？輸入文件：第一行頂點數(shù)n第一行n個頂點〔從1到n的權(quán)值輸出格式：最小的和的值,各三角形組成的方式輸入示例：5122123245231輸出示例：theminimumis:12214884theformationof3triangle:345,153,123分析:這是一道很典型的區(qū)間模型動態(tài)規(guī)劃問題。設f[i,j]〔i<j表示從頂點i到頂點j的凸多邊形三角剖分后所得到的最大乘積,我們可以得到下面的動態(tài)轉(zhuǎn)移方程：f[i,j]=min{f[i,k]+f[k,j]+s[i]*s[j]*s[k]}<i<k<j>目標狀態(tài)為：f[1,n]但我們可以發(fā)現(xiàn),由于這里為乘積之和,在輸入數(shù)據(jù)較大時有可能超過長整形甚至實形的范圍,所以我們還需用高精度計算,但這是基本功,程序中就沒有寫了,請讀者自行完成。參考程序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;//動態(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é)點end;end;procedureprint<i,j:integer>;//輸出每個三角形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ū)間模型的動態(tài)規(guī)劃,在歷屆的信息學競賽,應用非常廣泛,如noi95的石子合并問題,noip2003普及組的數(shù)字游戲,noip2006提高組第1題等?！菜臉湫蛣討B(tài)規(guī)劃模型上面三種動態(tài)規(guī)劃都是建立在線性結(jié)構(gòu)上的,有順推和逆推兩種方法,下面我們介紹一種建立在‘樹’這個數(shù)據(jù)結(jié)構(gòu)上的動態(tài)規(guī)劃——樹型動態(tài)規(guī)劃模型。樹型動態(tài)規(guī)劃是建立在樹結(jié)構(gòu)上的動態(tài)規(guī)劃,所以階段很明顯,一般是通過孩子節(jié)點的最優(yōu)值推出父親節(jié)點的最優(yōu)值。一般以節(jié)點及相關(guān)信息為狀態(tài),動態(tài)轉(zhuǎn)移方程是也是根據(jù)父親節(jié)點跟孩子節(jié)點之間關(guān)系來建立的。通過根的子節(jié)點傳遞有用的信息給根,完后根得出最優(yōu)解的過程。下面結(jié)合一些例子,來介紹它的一般解法。例1:[問題描述]給你一棵樹T=<V,E,W>,其中V表示頂點集且|V|=n,E表示邊集。如果<v,u>屬于E,則W<v,u>表示<v,u>的長度。求兩點v,u,使得它們之間的路徑總長度最長。你只需要輸出這個最長長度即可。輸入格式:輸入第1行為n和邊數(shù)e接下來e行,每行三個數(shù)v,u,和w輸出格式:最長長度輸入樣例6512201340145025103610輸出樣例100分析：認真審題,其實此題是要在帶權(quán)樹上求最長鏈,一棵有根樹的最長鏈,可能出現(xiàn)如上圖的兩種情況設dep<i>表示以節(jié)點i為根的子樹的最大深度。F<i>表示以節(jié)點i為根的子樹中,包含節(jié)點i的最長鏈長度我們有:dep<i>=max{dep<j>+w<i,j>},其中j是i的子節(jié)點F<i>=max{dep<i>,dep<j>+w<i,j>+dep<k>+w<i,k>},其中j,k是i的子節(jié)點,且j<>k不難發(fā)現(xiàn),我們的狀態(tài)轉(zhuǎn)移方程是按照從下至上的順序計算的。做一遍DFS遍歷,在回朔的時候分別計算dep和F的值,關(guān)于F值的計算：由于節(jié)點j和k之間沒有關(guān)聯(lián),所以我們只需要選擇兩個<dep<j>+w<i,j>>最大的子節(jié)點進行累加即可。參考程序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的過程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二叉蘋果樹有一棵蘋果樹,如果樹枝有分叉,一定是分2叉〔就是說沒有只有1個兒子的結(jié)點這棵樹共有N個結(jié)點〔葉子點或者樹枝分叉點,編號為1-N,樹根編號一定是1。我們用一根樹