動態(tài)規(guī)劃經(jīng)典教程——多進(jìn)程動態(tài)規(guī)劃

多進(jìn)程動態(tài)規(guī)劃

從字面上就可以看出，所謂多進(jìn)程就是在原文題的基礎(chǔ)上要求將這個問題重復(fù)多次的總和最大。

具體怎么做看個例題吧。

例題28   方格取數(shù)   (fgqs.pas/c/cpp)   來源：NOIP2000(提高組)

【問題描述】

設(shè)有N*N的方格圖(N<=10,我們將其中的某些方格中填入正整數(shù),而其他的方格中則放入數(shù)字0。如下圖所示（見樣例）：

某人從圖的左上角的A 點(diǎn)出發(fā)，可以向下行走，也可以向右走，直到到達(dá)右下角的B點(diǎn)。在走過的路上，他可以取走方格中的數(shù)（取走后的方格中將變?yōu)閿?shù)字0）。

此人從A點(diǎn)到B 點(diǎn)共走兩次，試找出2條這樣的路徑，使得取得的數(shù)之和為最大。

【輸入文件】

輸入的第一行為一個整數(shù)N（表示N*N的方格圖），接下來的每行有三個整數(shù)，前兩個表示位置，第三個數(shù)為該位置上所放的數(shù)。一行單獨(dú)的0表示輸入結(jié)束。

【輸出文件】

只需輸出一個整數(shù)，表示2條路徑上取得的最大的和。

【輸入樣例】

8

2   3   13

2   6   6

3   5   7

4   4   14

5   2   21

5   6   4

6   3   15

7   2   14

0   0   0

【輸出樣例】

67

【問題分析】

這是一道很經(jīng)典的多進(jìn)程動態(tài)規(guī)劃題，如果只取一次，它的模型就是我們前面講的街道問題了，很簡單就可以實(shí)現(xiàn)?，F(xiàn)在要求取兩次，怎么辦呢？

一個自然的想法是：將前面的取過的數(shù)全賦成0，然后在取一次，感覺挺對的，樣例也過了。

但這樣做是錯的，第一次取的顯然是最大值，但第二次取的未必次大，所以也許兩條非最大的路，也許比一條最大一條小一點(diǎn)的路更優(yōu)。

看個例子：

0 0 2 0 3 0                      0 0 2 0 3 0

0 0 2 0 0 0                      0 0 2 0 0 0

0 0 2 0 2 0                      0 0 2 0 2 0

0 0 0 0 2 0                      0 0 0 0 2 0

0 0 0 0 2 0                      0 0 0 0 2 0

0 0 2 0 2 0                      0 0 2 0 2 0

圖1                                圖2

如上圖，圖1是按找上訴思路求得的解。圖中紅色路線是第一求得的最大值，顯然圖1紅色和紫色兩條路徑不如圖2藍(lán)色和綠色兩條路徑大。

既然這樣做不行，我們還得回到動態(tài)規(guī)劃的本質(zhì)來看代問題，我們在想想這個問題的狀態(tài)，對于走一次，走到矩陣的任意一個位置就是一個狀態(tài)，而要是走兩次，顯然走到矩陣的某個位置只是一個狀態(tài)的一部分，不能完整的描述整個狀態(tài)。那另一部分顯然就是第二次走到的位置了。如果我們把這兩部分合起來就是一個完整的狀態(tài)了。

于是，設(shè)計一個狀態(tài)opt[i1,j1,i2,j2]表示兩條路分別走到（i1,j1）點(diǎn)和（i2,j2）點(diǎn)時取到的最大值。顯然決策有4中（乘法原理一個點(diǎn)兩種*另一個點(diǎn)的兩中）

即（上，上）（上，左）（左，上）（左，左）上和左表示從哪個方向走到該點(diǎn)，當(dāng)然要注意走到同行，同列，同點(diǎn)時的情況（因?yàn)橐舐窂讲恢貜?fù)）。

狀態(tài)轉(zhuǎn)移方程：

max(opt[i1-1,j1,i2-1,j2],opt[i1,j1-1,i2-1,j2])+a[i1,j1]+a[i2,j2]   (1<=i1=i2<=n,1<=j1<=j2<=n)

max(opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])

(1<=j1=j2<=n,1<=i1<=i2<=n)

opt[i,j]=   max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],

opt[i1,j1-1,i2,j2-2])+a[i1,j1]+a[i2,j2]   (1<=i1,j1<=i2,j2<=n)

max(opt[i1-1,j1,i2-1,j2],opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2-1,j2],

opt[i1,j1-1,i2,j2-2])+a[i1,j1]   (1<=i1=i2<=n,1<=j1=j2<=n)

時間復(fù)雜度：狀態(tài)數(shù)O（N4）*轉(zhuǎn)移代價O（1）=總復(fù)雜度O（N4）

空間復(fù)雜度：O（N4）

由于數(shù)據(jù)很小所以這樣做雖然時間和空間復(fù)雜度都很高但還是可以AC的。

【源代碼1】

program fgqs;

const

fin='fgqs.in';

fout='fgqs.out';

maxn=11;

var

a:array[0..maxn,0..maxn] of longint;

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

n:longint;

procedure init;

var

i,j,w:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

read(n);

repeat

readln(i,j,w);

a[i,j]:=w;

until i=0;

close(input);

end;

function max(x,y:longint):longint;

begin

max:=y;

if x>y then max:=x;

end;

procedure main;

var

i1,i2,j1,j2:longint;

begin

for i1:=1 to n do

for j1:=1 to n do

for i2:=i1 to n do

for j2:=1 to j1 do

if (i1=i2) and (j1=j2) then

opt[i1,j1,i2,j2]:=opt[i1-1,j1,i2,j2-1]+a[i1,j1]

else if (i1=i2-1) and (j1=j2) then

opt[i1,j1,i2,j2]:=max(opt[i1-1,j1,i2,j2-1],opt[i1,j1-1,i2,j2-1])

+a[i1,j1]+a[i2,j2]

else if (i1=i2) and (j1=j2+1) then

opt[i1,j1,i2,j2]:=max(opt[i1-1,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2])

+a[i1,j1]+a[i2,j2]

else begin

opt[i1,j1,i2,j2]:=max(opt[i1-1,j1,i2,j2-1],opt[i1-1,j1,i2-1,j2]);

opt[i1,j1,i2,j2]:=max(opt[i1,j1,i2,j2],opt[i1,j1-1,i2,j2-1]);

opt[i1,j1,i2,j2]:=max(opt[i1,j1,i2,j2],opt[i1,j1-1,i2-1,j2]);

inc(opt[i1,j1,i2,j2],a[i1,j1]+a[i2,j2]);

end;

end;

procedure print;

begin

writeln(opt[n,n,n,n]);

close(output);

end;

begin

init;

main;

print;

end.

如果這個題的數(shù)據(jù)范圍在大點(diǎn)就得優(yōu)化了，怎么優(yōu)化這個程序呢？

上面說過對于時間空間都大的時候，首先想到的就是尋找特點(diǎn)，改變狀態(tài)的表示法，減少狀態(tài)的維數(shù)。

仔細(xì)分析我們發(fā)現(xiàn)，處于同行，同列的狀態(tài)，等價于另外一個點(diǎn)在對角線上的狀態(tài)。而這條對角線正是此題的階段。因?yàn)樵跔顟B(tài)轉(zhuǎn)移的時候后面的哪個點(diǎn)總是從固定的一個方向轉(zhuǎn)移來的。也就是說我們只要對角先上的狀態(tài)就可以省掉那些同行同列的狀態(tài)了。

做過N皇的同學(xué)一定知道怎么表示右上到左下的這幾條對角線，不知道的同學(xué)也沒關(guān)系,對于一個點(diǎn)（i,j）他對角右上角的點(diǎn)就是（i-1，j+1）所以可以看出這些點(diǎn)的和是定值，且值從2到N*2。

這樣用三個變量就可以表示這兩個點(diǎn)了，于是設(shè)計狀態(tài)opt[k,i1,i2]表示處于階段K時走到i1,i2的兩條路徑所取得的數(shù)的最大和。

用上面的思維不難想出動態(tài)轉(zhuǎn)移方程：

max(opt[k-1,i1-1,i2-1],opt[k-1,i1-1,i2],opt[k-1,i1,i2-1],opt[k-1,i1,i2])+a[i1,k-i1]+a[i2,k-i2](1<=i1,i2<=n,2<=k<=n*2,i1<>i2)

otp[k,i1,i2]=opt[k-1,i1-1,i2]+a[i1,k-i1](1<=i1,i2<=n,2<=k<=n*2,i1=i2)

【源代碼2】

program fgqs;

const

fin='fgqs.in';

fout='fgqs.out';

maxn=11;

var

a:array[0..maxn,0..maxn] of longint;

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

n:longint;

procedure init;

var

i,j,w:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

read(n);

repeat

readln(i,j,w);

a[i,j]:=w;

until i=0;

close(input);

end;

function max(x,y:longint):longint;

begin

max:=y;

if x>y then max:=x;

end;

procedure main;

var

k,i1,i2,j1,j2,mid:longint;

begin

for k:=2 to n*2 do

begin

for i1:=1 to n do

if (k-i1>0) and (k-i1<=n) then

for i2:=1 to n do

if (k-i2>0) and (k-i2<=n) then

begin

if i1=i2 then

opt[k,i1,i2]:=opt[k-1,i1-1,i2]+a[i1,k-i1]

else begin

opt[k,i1,i2]:=max(opt[k-1,i1,i2],opt[k-1,i1,i2-1]);

opt[k,i1,i2]:=max(opt[k,i1,i2],opt[k-1,i1-1,i2]);

opt[k,i1,i2]:=max(opt[k,i1,i2],opt[k-1,i1-1,i2-1]);

inc(opt[k,i1,i2],a[i1,k-i1]+a[i2,k-i2]);

end;

end;

end;

end;

procedure print;

begin

writeln(opt[n*2,n,n]);

close(output);

end;

begin

init;

main;

print;

end.

注：如果取多次，和取兩次道理一樣，只不過有多一次，狀態(tài)就多加一維，如果數(shù)據(jù)范圍很大，時間空間復(fù)雜度太高時可以用網(wǎng)絡(luò)流解這個問題，只是本人才疏學(xué)淺不能和大家分享了。