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

江蘇省丹陽(yáng)高級(jí)中學(xué)　荊曉虹2014.7　贛榆

從一個(gè)例子談起

問(wèn)題描述：

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

問(wèn)題輸入：

一行多個(gè)用空格隔開(kāi)的整數(shù)，表示每根筷子的長(zhǎng)度。

問(wèn)題輸出：

一個(gè)整數(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

完整的動(dòng)態(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)用動(dòng)態(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é)

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

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

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

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

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

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

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

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

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

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

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

1、階段

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

2、狀態(tài)

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

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

3、決策

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

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

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

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

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

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

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

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

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

規(guī)劃方向

初始

階段當(dāng)前

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

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

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

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

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

問(wèn)題描述：

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

問(wèn)題輸入：

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

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

問(wèn)題輸出：

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

輸入樣例：

10 11 1 2 3 3 3 4 6 10 20

輸出樣例：

5

樣例說(shuō)明：

第一雙 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個(gè)元素的一維數(shù)組整型數(shù)組a和有n2個(gè)元素的二維數(shù)組整型數(shù)組opt；

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

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

遞歸地定義最優(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)解的值求解過(guò)程：

opt[1,1]=

…

Opt[2,1]=

…

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

完整的動(dòng)態(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)用動(dòng)態(tài)規(guī)劃

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

問(wèn)題描述：

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

問(wèn)題輸入：

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

問(wèn)題輸出：

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

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

10 52 62 36 55 44 6

輸出樣例：

15

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

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

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