動態(tài)規(guī)劃一

江蘇省丹陽高級中學(xué)　荊曉虹2014.7　贛榆

從一個例子談起

問題描述：

大J擺出一排長短不一的筷子，筷子的長度是一個正整數(shù)序列b1，b2，b3，…，bn，她問小L，拿掉最少數(shù)量的筷子，就可以使剩下的筷子從矮到高“排好隊(duì)”了呢？輸出留下的筷子隊(duì)形的長度，即形成高矮排隊(duì)的筷子的根數(shù)。

問題輸入：

一行多個用空格隔開的整數(shù)，表示每根筷子的長度。

問題輸出：

一個整數(shù)，表示最終隊(duì)形里筷子的根數(shù)。

輸入樣例：

13　7　9　16　38　24　37　18

輸出樣例：

5

數(shù)據(jù)限制：

0<n<=100

遞歸地定義最優(yōu)解的值b[1]=1, b[2]=1, b[3]=1 ,...... i-1

b[i]=max{b[j] | a[i]>=a[j]} + 1 j=1

完整的動態(tài)規(guī)劃求解的程序program ex1;

var i,j,n,len:integer;

a,b:array[1..100] of integer; begin

readln(n);

for i:=1 to n do

begin

read(a[i]);

b[i]:=1;

end;

☆如何運(yùn)用動態(tài)規(guī)劃

for i:=2 to n do

begin

len:=0;

for j:=1 to i-1 do

if (a[i]>=a[j]) and (b[j]>len) then len:=b[j]; if len>0 then b[i]:=len+1;

end;

…

構(gòu)建最優(yōu)解

len:=1;

for j:=2 to n do

if b[j]>len then len:=b[j]; writeln('maxlen=',len);end.

小結(jié)

?動態(tài)規(guī)劃是一種算法策略, 它采用了兩個主要的設(shè)計(jì)方法:

–表格化 - 利用數(shù)組存儲中間計(jì)算環(huán)節(jié)

–自底向上 - 從最底層子問題開始, 逐步上升計(jì)算, 最后得到問題的解?動態(tài)規(guī)劃主要適用于一類所謂的“最優(yōu)化”問題, 即求最大(或最小)值. 當(dāng)

分析問題的性質(zhì), 滿足如下二點(diǎn)時(shí), 就可采用動態(tài)規(guī)劃策略求解:–最優(yōu)子結(jié)構(gòu) - 問題的一個最優(yōu)解中包含著子問題的一個最優(yōu)解.

–重疊子問題 – 求解問題的解時(shí)要反復(fù)計(jì)算若干個子問題. 同理, 求解各個子問題時(shí)又要反復(fù)計(jì)算若干子子問題, 這些子子問題可能是新產(chǎn)生的, 也可能是重復(fù)產(chǎn)生的.

☆什么是動態(tài)規(guī)劃

動態(tài)規(guī)劃（Dynamic Programming）

動態(tài)規(guī)劃是運(yùn)籌學(xué)的一個分支。它是解決多階段決策過程最優(yōu)化問題的一種方法。1951年，美國數(shù)學(xué)家R.Bellman提出了解決這類問題的“最優(yōu)化原則”，1957年發(fā)表了他的名著《動態(tài)規(guī)劃》，該書是動態(tài)規(guī)劃方面的第一本著作。動態(tài)規(guī)劃問世以來，在工農(nóng)業(yè)生產(chǎn)、經(jīng)濟(jì)、軍事、工程技術(shù)等許多方面都得到了廣泛的應(yīng)用，取得了顯著的效果。

動態(tài)規(guī)劃成為了信息學(xué)競賽中必不可少的一個重要方法，幾乎在所有的國內(nèi)和國際信息學(xué)競賽中，都至少有一道動態(tài)規(guī)劃的題目。所以，掌握好動態(tài)規(guī)劃，是非常重要的。

☆什么是動態(tài)規(guī)劃

動態(tài)規(guī)劃中的相關(guān)概念：

1、階段

用動態(tài)規(guī)劃求解一個問題時(shí)，需要將問題的全過程恰當(dāng)?shù)貏澐殖扇舾蓚�相互聯(lián)系的階段，以便按一定的次序去求解。階段的劃分一般是根據(jù)時(shí)間和空間的自然特征來定的，一般要便于把問題轉(zhuǎn)化成多階段決策的過程。

2、狀態(tài)

狀態(tài)表示的是事物某一階段的性質(zhì)，狀態(tài)通過一個變量來描述，這個變量稱為狀態(tài)變量。各個狀態(tài)之間是可以相互轉(zhuǎn)換的。

☆什么是動態(tài)規(guī)劃

3、決策

對問題的處理中做出某種選擇性的行動就是決策。一個實(shí)際問題可能要有多次決策，在每一個階段中都需要有一次決策。一次決策就會從一個階段進(jìn)入另一個階段，狀態(tài)也就發(fā)生了轉(zhuǎn)移。

4、策略和最優(yōu)策略

所有階段按照約定的決策方法，依次排列構(gòu)成問題的求解全過程。這些決策的總體稱為策略。在實(shí)際問題中，從決策允許集合中找出最優(yōu)效果的策略稱為最優(yōu)策略。

☆什么是動態(tài)規(guī)劃

更多內(nèi)容請?jiān)L問久久建筑網(wǎng)
5、狀態(tài)轉(zhuǎn)移方程

前一階段的終點(diǎn)就是后一階段的起點(diǎn)，這種關(guān)系描述了由K階段到K+1階段狀態(tài)的演變規(guī)律，是關(guān)于兩個相鄰階段狀態(tài)的方程，稱為狀態(tài)轉(zhuǎn)移方程，是動態(tài)規(guī)劃的核心。

算法模式圖動態(tài)規(guī)劃

多個規(guī)劃(決策)當(dāng)前最優(yōu)決策

當(dāng)前非最優(yōu)決策

規(guī)劃方向

初始

階段當(dāng)前

階段i目標(biāo)階段

i向著目標(biāo)階段不斷改變(動態(tài))

當(dāng)前階段的決策僅受前一階段決策的影響,并決定下一個階段的決策求得的一個最優(yōu)解

如何運(yùn)用動態(tài)規(guī)劃

例2：題目名：K雙筷子（*.in/out/pas/cpp）

問題描述：

大J有很多根筷子，因?yàn)榭曜拥拈L度不一，很難判斷出哪兩根是一雙的。這天，家里來了K個客人，大J留下他們吃晚飯。加上小L和他的爸爸媽媽，共K+3個人。每人需要用一雙筷子。大J只好清理了一下筷子，共N根，長度為T1，T2，T3，…，TN�，F(xiàn)在她想用這些筷子組合成K+3雙，使每雙的筷子長度差的平方和最小。小L請你幫忙。

問題輸入：

輸入文件中共兩行，第一行為兩個用空格隔開的整數(shù)N，K。

第二行共有N個用空格隔開的整數(shù)，為Ti每個整數(shù)為1～50之間的數(shù)。

問題輸出：

輸出文件中僅一行。如果湊不齊K+3雙，輸出-1，否則輸出長度差平方和的最小值。

輸入樣例：

10 11 1 2 3 3 3 4 6 10 20

輸出樣例：

5

樣例說明：

第一雙 1 1

第二雙 2 3

第三雙 3 3

第四雙 4 6

(1-1)^2+(2-3)^2+(3-3)^2+(4-6)^2=5。

數(shù)據(jù)限制：

1<=N<=100，0<K<50

解結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)：

設(shè)定有n個元素的一維數(shù)組整型數(shù)組a和有n2個元素的二維數(shù)組整型數(shù)組opt；

a[i]表示第i個數(shù)的數(shù)值本身；

opt[i，j]表示前i根筷子配好j雙筷子時(shí)的最小長度差的平方和的大�。�

遞歸地定義最優(yōu)解的值opt賦初值（最大值）

Opt[0,0]=0

opt[i,j]=min{opt[i-1,j]

opt[i-2,j-1]+(a[i]-a[i-1])^2} 1<=i<=n,1<=j<=k+3

自底向上計(jì)算最優(yōu)解的值求解過程：

opt[1,1]=

…

Opt[2,1]=

…

Opt[3,1]= opt[3,2]=

完整的動態(tài)規(guī)劃求解的程序var

opt : array[0..maxn,0..53] of longint;

a : array[1..100] of integer;

n,k : integer;

i,j : integer;

procedure sort;

var

i,j,temp : integer;

begin

for i := 1 to n-1 do

for j := i+1 to n do

if (a[i]>a[j]) then

begin temp := a[i];

a[i] := a[j];

a[j] := temp;

end;

end;

readln(n,k);

for i := 1 to n do read(a[i]);

if (n<2*k+6) then begin

writeln(-1);

close(input); close(output); halt;

end;

sort;

fillchar(opt,sizeof(opt),$7F);

opt[0,0] := 0;

for i := 1 to n do

for j := 1 to k+3 do

if (i>=2*j) then

begin

if (opt[i-1,j]<opt[i,j]) then opt[i,j] := opt[i-1,j]; if (opt[i-2,j-1]+sqr(a[i]-a[i-1])<opt[i,j]) then opt[i,j] := opt[i-2,j-1]+sqr(a[i]-a[i-1]); end;

writeln(opt[n,k+3]);

end.

如何運(yùn)用動態(tài)規(guī)劃

題目名：包裝筷子（chop.in/out/pas/cpp）

問題描述：

大J收集的N根的不同的筷子，她對每根筷子都根據(jù)喜愛程度標(biāo)上一個整數(shù)，稱為喜愛度。這天她想帶一部分最喜愛的筷子送給好朋友。她找來一個盒子，想把筷子裝起來，為了在路上顛簸不會摩擦碰傷筷子，她找來一包棉花，用來填塞筷子之余的空隙。盒子里去掉棉花占據(jù)位置后，總?cè)萘窟�有Vmax，她想選擇一些筷子裝進(jìn)盒子，使得盒子里裝的筷子總喜愛度是所有裝載方案中最大的。

問題輸入：

第一行為兩個整數(shù)，依次表示盒子的可用容量V和所有的筷子數(shù)量N。 下面共有n行，每行有兩個用空格分隔的整數(shù)，依次表示某根筷子的體積和喜愛度。

問題輸出：

輸出僅一行為一個整數(shù)，表示盒子最終所裝筷子的最大總喜愛度。

如何運(yùn)用動態(tài)規(guī)劃輸入樣例：

10 52 62 36 55 44 6

輸出樣例：

15

數(shù)據(jù)限制：

1<=V<=1000，1<=N<=100

對于30%的數(shù)據(jù)，滿足：N<=10；對于100%的數(shù)據(jù)，滿足：N<=100。