動態(tài)規(guī)劃經(jīng)典教程——第二節(jié)動態(tài)規(guī)劃分類討論

第二節(jié)動態(tài)規(guī)劃分類討論

這里用狀態(tài)維數(shù)對動態(tài)規(guī)劃進行了分類：

1.狀態(tài)是一維的

1．1下降/非降子序列問題：

問題描述：   {挖掘題目的本質(zhì)，一但抽象成這樣的描述就可以用這個方法解}

在一個無序的序列a1,a2,a3,a4…an里，找到一個最長的序列滿足：ai<=aj<=ak…<=am,且i<j<k…<m.（最長非降子序列）或ai>aj>ak…>am,且i>j>k…>m.（最長下降子序列）。

問題分析：

如果前i-1個數(shù)中用到ak (ak>ai或ak<=ai)構(gòu)成了一個的最長的序列加上第I個數(shù)ai就是前i個數(shù)中用到i的最長的序列了。那么求用到ak構(gòu)成的最長的序列有要求前k-1個數(shù)中……

從上面的分析可以看出這樣劃分問題滿足最優(yōu)子結(jié)構(gòu)，那滿足無后效性么？顯然對于第i個數(shù)時只考慮前i-1個數(shù),顯然滿足無后效性，可以用動態(tài)規(guī)劃解。

分析到這里動態(tài)規(guī)劃的三要素就不難得出了：如果按照序列編號劃分階段，設計一個狀態(tài)opt[i] 表示前i個數(shù)中用到第i個數(shù)所構(gòu)成的最優(yōu)解。那么決策就是在前i-1個狀態(tài)中找到最大的opt[j]使得aj>ai(或aj<=ai)，opt[j]+1就是opt[i]的值；用方程表示為：{我習慣了這種寫法，但不是狀態(tài)轉(zhuǎn)移方程的標準寫法 }

opt[i]=max(opt[j])+1   (0<=j<i 且aj<=ai)       {最長非降子序列}

opt[i]=max(opt[j])+1   (0<=j<i 且aj>ai)        {最長下降子序列}

實現(xiàn)求解的部分代碼：

opt[0]:=maxsize；{maxsize 為maxlongint或-maxlongint}

for   i:=1 to n do

for j:=0 to i-1 do

if ( a[j]>a[i]) and (opt[j]+1>opt[i]) then

opt[i]:=opt[j]+1;

ans:=-maxlongint;

for i:=1 to n do

if opt[i]>ans then ans:=opt[i];                {ans 為最終解}

復雜度：從上面的實現(xiàn)不難看出時間復雜度為O（N2），空間復雜度O（N）；

例題1   攔截導彈   (missile.pas/c/cpp)   來源：NOIP1999(提高組) 第一題

【問題描述】

某國為了防御敵國的導彈襲擊，發(fā)展出一種導彈攔截系統(tǒng)。但是這種導彈攔截系統(tǒng)有一個缺陷：雖然它的第一發(fā)炮彈能夠到達任意的高度，但是以后每一發(fā)炮彈都不能高于前一發(fā)的高度。某天，雷達捕捉到敵國的導彈來襲。由于該系統(tǒng)還在試用階段，所以只有一套系統(tǒng)，因此有可能不能攔截所有的導彈。

輸入導彈依次飛來的高度（雷達給出的高度數(shù)據(jù)是不大于30000的正整數(shù)），計算這套系統(tǒng)最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統(tǒng)。

【輸入文件】missile.in

單獨一行列出導彈依次飛來的高度。

【輸出文件】missile.out

兩行，分別是最多能攔截的導彈數(shù)，要攔截所有導彈最少要配備的系統(tǒng)數(shù)

【輸入樣例】

389 207 155 300 299 170 158 65

【輸出樣例】

6

2

【問題分析】

有經(jīng)驗的選手不難看出這是一個求最長非升子序列問題，顯然標準算法是動態(tài)規(guī)劃。

以導彈依次飛來的順序為階段，設計狀態(tài)opt[i]表示前i個導彈中攔截了導彈i可以攔截最多能攔截到的導彈的個數(shù)。

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

opt[i]=max(opt[j])+1   (h[i]>=h[j],0=<j<i)   {h[i]存，第i個導彈的高度}

最大的opt[i]就是最終的解。

這只解決了第一問，對于第二問最直觀的方法就是求完一次opt[i]后把剛才要打的導彈去掉，在求一次opt[i]直到打完所有的導彈，但這樣做就錯了。

不難舉出反例： 6 1 7 3 2

錯解： 6 3 2/1/7   正解：6 1/7 3 2

其實認真分析一下題就回發(fā)現(xiàn)：每一個導彈最終的結(jié)果都是要被打的，如果它后面有一個比它高的導彈，那打它的這個裝置無論如何也不能打那個導彈了，經(jīng)過這么一分析，這個問題便抽象成在已知序列里找最長上升序列的問題。

求最長上升序列和上面說的求最長非升序列是一樣的，這里就不多說了。

復雜度：時間復雜度為O（N2），空間復雜度為O（N）。

【源代碼】

program missile;

const

fin='missile.in';

fout='missile.out';

maxn=10000;

var

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

n,anslen,anstime:longint;

procedure   init;

var

x:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

n:=0;

repeat

inc(n);

read(a[n]);

until seekeof;

end;

procedure main;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

a[0]:=maxlongint;

for i:=1 to n do

for j:=i-1 downto 0 do

if (a[j]>=a[i]) and (opt[j]+1>opt[i]) then

opt[i]:=opt[j]+1;

anslen:=0;

for i:=1 to n do

if opt[i]>anslen then

anslen:=opt[i];

fillchar(opt,sizeof(opt),0);

a[0]:=-maxlongint;

for i:=1 to n do

for j:=i-1 downto 0 do

if (a[j]<a[i]) and (opt[j]+1>opt[i]) then

opt[i]:=opt[j]+1;

anstime:=0;

for i:=1 to n do

if opt[i]>anstime then

anstime:=opt[i];

end;

procedure print;

begin

writeln(anslen);

writeln(anstime);

close(input);

close(output);

end;

begin

init;

main;

print;

end.

例題二   合唱隊形   (chorus.pas/c/cpp)   來源：NOIP2004(提高組) 第一題

N位同學站成一排，音樂老師要請其中的(N-K)位同學出列，使得剩下的K位同學排成合唱隊形。

合唱隊形是指這樣的一種隊形：設K位同學從左到右依次編號為1，2…，K，他們的身高分別為T1，T2，…，TK，   則他們的身高滿足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任務是，已知所有N位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。

【輸入文件】

    輸入文件chorus.in的第一行是一個整數(shù)N(2<=N<=100)，表示同學的總數(shù)。第一行有n個整數(shù)，用空格分隔，第i個整數(shù)Ti(130<=Ti<=230)是第i位同學的身高(厘米)。

【輸出文件】

    輸出文件chorus.out包括一行，這一行只包含一個整數(shù)，就是最少需要幾位同學出列。

【樣例輸入】

8

186 186 150 200 160 130 197 220

【樣例輸出】

4

【數(shù)據(jù)規(guī)?！?/span>

對于50％的數(shù)據(jù)，保證有n<=20；

對于全部的數(shù)據(jù)，保證有n<=100。

【問題分析】

出列人數(shù)最少，也就是說留的人最多，也就是序列最長。

這樣分析就是典型的最長下降子序列問題。只要枚舉每一個人站中間時可以的到的最優(yōu)解。顯然它就等于，包括他在內(nèi)向左求最長上升子序列，向右求最長下降子序列。

我們看一下復雜度：

計算最長下降子序列的復雜度是O（N2），一共求N次，總復雜度是O（N3）。這樣的復雜度對于這個題的數(shù)據(jù)范圍來說是可以AC的。但有沒有更好的方法呢？

其實最長子序列只要一次就可以了。因為最長下降（上升）子序列不受中間人的影響。

只要用OPT1求一次最長上升子序列，OPT2求一次最長下降子序列。這樣答案就是N-max(opt1[i]+opt2[i]-1).

復雜度由O（N3）降到了O（N2）。

【源代碼】

program chorus;

const

fin='chorus.in';

fout='chorus.out';

maxn=200;

var

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

n,ans:longint;

procedure init;

var

i:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

readln(n);

for i:=1 to n do

read(a[i]);

end;

procedure main;

var

i,j:longint;

begin

a[0]:=-maxlongint;

for i:=1 to n do

for j:=i-1 downto 0 do

if (a[j]<a[i]) and (opt1[j]+1>opt1[i]) then

opt1[i]:=opt1[j]+1;

a[n+1]:=-maxlongint;

for i:=n downto 1 do

for j:=i+1 to n+1 do

if (a[j]<a[i]) and (opt2[j]+1>opt2[i]) then

opt2[i]:=opt2[j]+1;

ans:=0;

for i:=1 to n do

if opt1[i]+opt2[i]>ans then

ans:=opt1[i]+opt2[i];

end;

procedure print;

begin

writeln(n-ans+1);

close(input);

close(output);

end;

begin

init;

main;

print;

end.

例題3   Buy Low Buy Lower   (buylow.pas/c/cpp)   來源: USACO 4-3-1

【問題描述】

“逢低吸納”是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:

"逢低吸納,越低越買"

這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低.按照這個規(guī)則購買股票的次數(shù)越多越好，看看你最多能按這個規(guī)則買幾次。

給定連續(xù)的N天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。

以下面這個表為例, 某幾天的股價是:

天數(shù) 1   2   3   4   5   6   7   8   9   10 11 12

股價 68 69 54 64 68 64 70 67 78 62 98 87

這個例子中, 聰明的投資者(按上面的定義)，如果每次買股票時的股價都比上一次買時低，那么他最多能買4次股票。一種買法如下(可能有其他的買法):

天數(shù) 2   5   6   10

股價 69 68 64 62

【輸入文件】buylow.in

第1行: N (1 <= N <= 5000), 表示能買股票的天數(shù)。

第2行以下: N個正整數(shù) (可能分多行) ，第i個正整數(shù)表示第i天的股價. 這些正整數(shù)大小不會超過longint(pascal)/long(c++).

【輸出文件】buylow.out

只有一行，輸出兩個整數(shù)：

能夠買進股票的天數(shù)長度達到這個值的股票購買方案數(shù)量

在計算解的數(shù)量的時候，如果兩個解所組成的字符串相同，那么這樣的兩個解被認為是相同的（只能算做一個解）。因此，兩個不同的購買方案可能產(chǎn)生同一個字符串，這樣只能計算一次。

【輸入樣例】

12

68 69 54 64 68 64 70 67

78 62 98 87

【輸出樣例】

4 2

【問題分析】

從題目描述就可以看出這是最長下降子序列問題，于是求解第一問不是難事，以天數(shù)為階段，設計狀態(tài)opt[i] 表示前i天中要買第i天的股票所能得到的最大購買次數(shù)。

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

opt[i]=max(opt[j])+1   (a[i]>=a[j],0=<j<i)   {a[i]存第i天股價}

最大的opt[i]就是最終的解。

第二問呢，稍麻煩一點。

從問題的邊界出發(fā)考慮問題，當?shù)谝粏柷蟮靡粋€最優(yōu)解opt[i]=X時，

在1到N中如果還有另外一個opt[j]=x那么選取J的這個方案肯定是成立的。

是不是統(tǒng)計所有的opt[j]=x 的個數(shù)就是解了呢？

顯然沒那么簡單，因為選?。蔬@天的股票構(gòu)成的方案不見得＝１，看下面一個例子：

５　6   43?。?2

方案一：５４３１

方案二：５４３２

方案三：６４３１

方案四：６４３２

x=4

也就是所雖然opt[5]=X 和opt[6]=X但個數(shù)只有兩個，而實際上應該有四個方案，但在仔細觀察發(fā)現(xiàn)，構(gòu)成opt[5]=x 的這個方案中 opt[j]=x-1的方案數(shù)有兩個,opt[j]=x-2的有一個，opt[j]=x-3 的有一個……

顯然這是滿足低歸定義的設計函數(shù)F（i）表示前I張中用到第i張股票的方案數(shù)。

遞推式：

1   (i=0)

F(i)=

Sum(F(j))   (0<=j<=n,a[j]>a[i],opt[j]=opt[i]-1)   {sum 代表求和}

答案=sum(F(j))    {0<j<=n,opt[j]=x}

復雜度：

求解第一問時間復雜度是O(N2),求解第二問如果用遞推或遞歸+記憶化時間復雜度仍為O（N2）但要是用赤裸裸的遞歸那就復雜多了……，因為那樣造成了好多不必要的計算。

你認為這樣做就解決了這道題目了么？還沒有，還要注意一些東西：

（1）如果有兩個方案中出現(xiàn)序列一樣，視為一個方案，要需要加一個數(shù)組next用next[i] 記錄和第i個數(shù)情況一樣（即：opt[i]=opt[j] 且 a[i]=a[j]）可看做一個方案的最近的位置。

遞推時j只要走到next[i]即可。

（2）為了方便操作可以將a[n+1]賦值為-maxlongint這樣可以認為第n+1個一定可以買，答案就是sum(F(n+1))。

（3）看數(shù)據(jù)規(guī)模顯然要用高精度。

注：USACO上最后一個點錯了。我在程序中做了處理。

【源代碼】

program buylow;

const

fin='buylow.in';

fout='buylow.out';

maxn=5010;

maxsize=10;

jz=100000000;

type

arrtype=array[0..maxsize] of longint;

var

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

F:array[0..maxn] of arrtype;

n:longint;

procedure init;

var

i:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

readln(n);

if n=5 then                {最后一個點錯了，我只好這么寫了}

begin

writeln('2 5');

close(input);

close(output);

halt;

end;

for i:=1 to n do

read(a[i]);

end;

procedure Hinc(var x:arrtype;y:arrtype);

var

i,z:longint;

begin

z:=0;

for i:=1 to maxsize do

begin

z:=z div jz+x[i]+y[i];

x[i]:=z mod jz;

end;

end;

procedure main;

var

i,j:longint;

begin

a[0]:=maxlongint;

a[n+1]:=-maxlongint;

for i:=1 to n+1 do

for j:=0 to i-1 do

if (a[j]>a[i]) and (opt[j]+1>opt[i])   then

opt[i]:=opt[j]+1;

for i:=1 to n do

begin

j:=i-1;

while (j>0) and ((opt[i]<>opt[j]) or (a[i]<>a[j])) do

dec(j);

next[i]:=j;

end;

F[0,1]:=1;

for i:=1 to n+1 do

for j:=i-1 downto next[i] do

if (opt[j]=opt[i]-1) and (a[j]>a[i]) then

Hinc(F[i],F[j]);

end;

procedure print;

var

i,top,m:longint;

begin

write(opt[n+1]-1,' ');

top:=maxsize;

while (top>1) and (F[n+1][top]=0) do

dec(top);

write(F[n+1,top]);

for i:=top-1 downto 1 do

begin

m:=F[n+1,i];

while m<maxsize div 10 do

begin

write('0');

m:=m*10;

end;

write(F[n+1,i]);

end;

writeln;

close(input);

close(output);

end;

begin

init;

main;

print;

end.

例題4   船   (ships.pas/c/cpp)   來源：《奧賽經(jīng)典》（提高篇）

【問題描述】

PALMIA國家被一條河流分成南北兩岸，南北兩岸上各有N個村莊。北岸的每一個村莊有一個唯一的朋友在南岸，且他們的朋友村莊彼此不同。

每一對朋友村莊想要一條船來連接他們，他們向政府提出申請以獲得批準。由于河面上常常有霧，政府決定禁止船只航線相交（如果相交，則很可能導致碰船）。

你的任務是編寫一個程序，幫助政府官員決定批準哪些船只航線，使得不相交的航線數(shù)目最大。

【輸入文件】ships.in

輸入文件由幾組數(shù)據(jù)組成。每組數(shù)據(jù)的第一行有2個整數(shù)X，Y，中間有一個空格隔開，X代表PALMIA河的長度（10<=X<=6000），Y代表河的寬度（10<=Y<=100）。第二行包含整數(shù)N，表示分別坐落在南北兩岸上的村莊的數(shù)目（1<=N<=5000）。在接下來的N行中，每一行有兩個非負整數(shù)C，D，由一個空格隔開，分別表示這一對朋友村莊沿河岸與PALMIA河最西邊界的距離（C代表北岸的村莊，D代表南岸的村莊），不存在同岸又同位置的村莊。最后一組數(shù)據(jù)的下面僅有一行，是兩個0，也被一空格隔開。

【輸出文件】ships.out

對輸入文件的每一組數(shù)據(jù)，輸出文件應在連續(xù)的行中表示出最大可能滿足上述條件的航線的數(shù)目。

【輸入樣例】

30 4

7

22 4

2 6

10 3

15 12

9 8

17 17

4 2

0 0

【輸出樣例】

4

【問題分析】

這道題目相對來說思考難度較高，從字面意義上看不出問題的本質(zhì)來，有點無法下手的感覺。這里我給大家推薦兩種思考這類問題的方法。

法一：尋找規(guī)律法（我前面總結(jié)提到的第3個方法）

尋找規(guī)律自然要推幾組數(shù)據(jù)，首先當然有從樣例入手；

仔細觀察上圖：紅色航線是合法的，那么他們滿足什么規(guī)律呢？

C1    C2   C3   C4

北岸紅線的端點： 4     9    15   17

南岸紅線的端點： 2     8    12   17

D1    D2   D3   D4

不難看出無論線的斜率如何，都有這樣的規(guī)律：

C1<C2<C3<C4 且   D1<D2<D3<D4

如果我們把輸入數(shù)據(jù)排升序，問題變抽象為：

在一個序列（D）里找到最長的序列滿足DI<DJ<Dk……且i<j<k

這樣的話便是典型的最長非降子序列問題了。。。。

法二：邊界條件法（我前面總結(jié)提到的第4個方法）

邊界法其實就是把數(shù)據(jù)往小了縮，顯然N=1是答案是1。N=2時呢？

考慮這樣一組數(shù)據(jù)：

N=2

C1    D1

C2    D2

當 C1<C2 時，如果D1>D2 那么一定會相交，反之則不會相交。

當C1   >C2時，如果D1<D2 那么一定會相交，反之則不會相交。

N=3

C1    D1

C2    D2

C3    D3

……

其實不用在推導N=3了，有興趣的可以推導去?？?/span>N=2時就能得出：

對于任意兩條航線如果滿足Ci<Cj 且Di<Dj 則兩條航線不相交。這樣的話要想在一個序列里讓所有的航線都不相交那比然滿足，C1<C2<C3…Cans且D1<D2<D3…<Dans ，也就是將C排序后求出最長的滿足這個條件的序列的長度就是解。

這樣分析后顯然是一個最長非降子序列問題。

復雜度：排序可以用O（nlogn）的算法，求最長非降子序列時間復雜度是O(n2).

總復雜度為O（n2）.

【源代碼】

program ships;

const

fin='ships.in';

fout='ships.out';

maxn=5010;

type

retype=record

C,D:longint;

end;

var

x,y,n,ans:longint;

a:array[0..maxn] of retype;

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

procedure init;

var

i:longint;

begin

readln(n);

for i:=1 to n do

read(a[i].c,a[i].d);

end;

procedure quick(L,r:longint);

var

i,j,x:longint;

y:retype;

begin

i:=L;

j:=r;

x:=a[(i+j) div 2].c;

repeat

while a[i].c<x do

inc(i);

while a[j].c>x do

dec(j);

if i<=j then

begin

y:=a[i];

a[i]:=a[j];

a[j]:=y;

inc(i);

dec(j);

end;

until i>j;

if j>L then quick(L,j);

if i<r then quick(i,r);

end;

procedure main;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

quick(1,n);

for i:=1 to n do

for j:=0 to i-1 do

if (a[j].d<a[i].d) and (opt[j]+1>opt[i]) then

opt[i]:=opt[j]+1;

ans:=-maxlongint;

for i:=1 to n do

if ans<opt[i] then

ans:=opt[i];

writeln(ans);

end;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

read(x,y);

while (x+y<>0) do

begin

init;

main;

read(x,y);

end;

close(input);

close(output);

end.

1.2背包問題

首先說說背包問題的基本模型：

現(xiàn)有N個物品，每個物品的價值為V，重量為W。求用一個載重量為S的背包裝這寫物品，使得所裝物品的總價值最高。

背包問題用貪心和搜索解，當然效果不佳，不過在我的貪心和搜索總結(jié)中會說到。顯然標準的解法是動態(tài)規(guī)化，我在解決這個問題時習慣設計一維狀態(tài)，還可以設計二維的，二維狀態(tài)在下面會講，現(xiàn)在只討論用一維狀態(tài)實現(xiàn)背包問題。

背包問題的分類：

(1)小數(shù)背包:物品的重量是實數(shù)，如油，水等可以取1.67升……

(2)整數(shù)背包：<1>0/1背包：每個物品只能選一次，或不選。不能只選一部分

<2>部分背包：所選物品可以是一部分。

(3)多重背包：背包不只一個。

小數(shù)背包：在貪心總結(jié)中會細講。

整數(shù)背包：

部分背包：同小數(shù)背包。

0/1背包：這個問題是最經(jīng)常出現(xiàn)的問題，應該熟練掌握。

我們先看一下0/1背包的簡化版：

現(xiàn)有N個物品，每個物品重量為W，這些物品能否使在載重量為S的背包裝滿（即重量和正好為S）？如過不能那能使物品重量和最重達到多少？

針對這一問題我們以物品的個數(shù)分階段，設計一個狀態(tài)opt[i]表示載重量為i的背包可否裝滿，顯然opt[i]的基類型是boolean。

決策是什么呢？

當要裝第i個物品時，如果前i-1個物品可以使載重為 k的背包裝滿，那么載重為k+w[i]的背包就可以裝滿。于是對于一個opt[j]來說，只要opt[j-w[i]]是true（表示可裝滿）那opt[j]就可以裝滿，但要注意：針對每一個物品枚舉背包的載重量時如果這樣正向的推導會使同一個物品用好幾次，因為k+w[i]可裝滿那k+w[i]+w[i]就可裝滿，但實際上是裝不滿的因為物品只有一個。解決這個問題很簡單，只要逆向推導就OK了。

這樣劃分階段，設計狀態(tài)，滿足無后效性和么？

顯然對與一個每一個階段都是獨立的，物品的順序并不影響求解，因為裝物品的次序不限。而對于opt[j]只考慮opt[j-w[i]]而不考慮后面的，所以滿足無后效性。

有了上面的分析不難寫出狀態(tài)轉(zhuǎn)移方程：

opt[j]:=opt[j-w[1]]   {opt[j-w[i]]=true}

時間復雜度：

階段數(shù)O(S)*狀態(tài)數(shù)（O(N)）*轉(zhuǎn)移代價（O(1)）=O（SN）

下面看幾個例題：

例題5   裝箱問題   (pack.pas/c/cpp)   來源：NOIP2001(普及組) 第四題

【問題描述】

有一個箱子容量為V（正整數(shù)，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30＝，每個物品有一個體積（正整數(shù)）。

要求n個物品中，任取若干個裝入箱內(nèi)，使箱子的剩余空間為最小。

【輸入文件】

第一行一個正整數(shù)V表示箱子的容量，第二行一個正整數(shù)N表示物品個數(shù)，接下來N行列出這N個物品各自的體積。

【輸出文件】

單獨一行，表示箱子最小的剩余空間。

【輸入樣例】

24

6

8

3

12

7

9

7

【輸出樣例】

0

【問題分析】

本題是經(jīng)典的0/1背包問題，并且是0/1背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩余空間最小也就是盡量裝滿背包。于是這個問題便成了：

有一個栽重量為V的背包，有N個物品，盡量多裝物品，使背包盡量的重。

設計一個狀態(tài)opt[i]表示重量i可否構(gòu)成。

狀態(tài)轉(zhuǎn)移方程：opt[j]:=opt[j-w[1]]   {opt[j-w[i]]=true}

最終的解就是v-x（x<=n 且opt[x]=true 且 opt[x+1..n]=false）。

【源代碼1】

program pack;

const

fin='pack.in';

fout='pack.out';

maxv=20010;

maxn=100;

var

opt:array[0..maxv] of boolean;

w:array[0..maxn] of longint;

v,n,x:longint;

procedure init;

var

i:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

read(v);

read(n);

for i:=1 to n do

read(w[i]);

end;

procedure main;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),false);

opt[0]:=true;

for i:=1 to n do

for j:=v downto w[i] do

if opt[j-w[i]] then opt[j] :=true;

x:=v;

while not opt[x] do   dec(x);

end;

procedure print;

begin

writeln(v-x);

close(input);

close(output);

end;

begin

init;

main;

print;

end.

例題6   砝碼稱重 來源：NOIP1996（提高組）   第四題

【問題描述】

設有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），用他們能稱出的重量的種類數(shù)。

【輸入文件】

a1   a2   a3   a4   a5   a6

（表示1g砝碼有a1個，2g砝碼有a2個，…，20g砝碼有a6個，中間有空格）。

【輸出文件】

Total=N

（N表示用這些砝碼能稱出的不同重量的個數(shù)，但不包括一個砝碼也不用的情況）。

【輸入樣例】

1 1 0 0 0 0

【輸出樣例】

TOTAL=3

【問題分析】

把問題稍做一個改動，已知a1+a2+a3+a4+a5+a6個砝碼的重量w[i], w[i]∈{ 1,2,3,5,10,20} 其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數(shù)。

這樣一改就是經(jīng)典的0/1背包問題的簡化版了，求解方法完全和上面說的一樣，這里就不多說了，只是要注意這個題目不是求最大載重量，是統(tǒng)計所有的可稱出的重量的個數(shù)。

【源代碼1】

program P4;

const

maxn=1010;

w:array[1..6] of longint=(1,2,3,5,10,20);

var

opt:array[0..maxn] of boolean;

a:array[1..6] of longint;

procedure init;

var

i:longint;

begin

for i:=1 to 6 do

read(a[i]);

end;

procedure main;

var

i,j,k:longint;

begin

fillchar(opt,sizeof(opt),false);

opt[0]:=true;

for i:=1 to 6 do

for j:=1 to a[i] do

for k:=maxn downto w[i] do

if opt[k-w[i]] then   opt[k]:=true;

end;

procedure print;

var

ans,i:longint;

begin

ans:=0;

for i:=1 to maxn do

if opt[i] then

inc(ans);

writeln(ans);

end;

begin

init;

main;

print;

end.

例題7   積木城堡   來源：vijos P1059

【問題描述】

XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發(fā)現(xiàn)壘城堡的時候，如果下面的積木比上面的積木大，那么城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規(guī)則。

小XC想把自己壘的城堡送給幼兒園里漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們?yōu)榱双@得更漂亮的城堡而引起爭執(zhí)?？墒撬l(fā)現(xiàn)自己在壘城堡的時候并沒有預先考慮到這一點。所以他現(xiàn)在要改造城堡。由于他沒有多余的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最后的城堡都盡可能的高。

任務：

請你幫助小XC編一個程序，根據(jù)他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。

【輸入文件】

第一行是一個整數(shù)N(N<=100)，表示一共有幾座城堡。以下N行每行是一系列非負整數(shù)，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長。用-1結(jié)束。一座城堡中的積木不超過100塊，每塊積木的棱長不超過100。

【輸出文件】

一個整數(shù)，表示最后城堡的最大可能的高度。如果找不到合適的方案，則輸出0。

【輸入樣例】

2

2 1 –1

3 2 1 -1

【輸出樣例】

3

【提交鏈接】

http://www.vijos.cn/

【問題分析】

首先要說明一點，可以挪走任意一個積木，不見得是最上面的。

初看題目有點茫然，但抽象一下就。。。。。。。。。。

其實塔好積木在拿走就相當于當初搭的時候沒選拿走的積木。這樣一轉(zhuǎn)化思維問題就清楚了。把積木可搭建的最大高度看做背包的載重，每塊積木的高度就是物品的重量。也就是用給定的物品裝指定的包，使每個包裝的物品一樣多，且在符合條件的前提下盡量多。

這樣就變成經(jīng)典的背包問題了。

對于每一個城堡求一次，最終找到每一個城堡都可達到的最大高度即可。

【源代碼1】

const

maxhig=7000;

maxn=100;

var

n,top:longint;

opt:array[0..maxn,0..maxhig] of boolean;

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

procedure init;

var

i:longint;

begin

readln(n);

fillchar(opt,sizeof(opt),false);

for i:=1 to n do

opt[i,0]:=true;

end;

function can(m:longint):boolean;

var

i:longint;

begin

can:=true;

for i:=1 to n do

if not opt[i,m] then

exit(false);

end;

procedure main;

var

ii,m,tothig,i,j,ans:longint;

begin

for ii:=1 to n do

begin

top:=0;

read(m);

tothig:=0;

while m>0 do

begin

inc(top);

a[top]:=m;

inc(tothig,m);

read(m);

end;

for i:=1 to top do

for j:=tothig downto 1 do

if (j-a[i]>=0) and (opt[ii,j-a[i]]) then

opt[ii,j]:=true;

end;

ans:=maxhig;

while not opt[1,ans] do

dec(ans);

while not can(ans) do

dec(ans);

writeln(ans);

end;

begin

init;

main;

end.

回顧上面的內(nèi)容充分說明動態(tài)規(guī)劃的本質(zhì)就是遞推。其實按照我的理解（動規(guī)涉及最優(yōu)決策，遞推是單純的總結(jié)）背包問題的簡化版更準確點算是遞推而非動態(tài)規(guī)劃，至于動歸和遞推之間的界線本來就很模糊（至少我這么認為）把它看做什么都可以，沒必要咬文嚼字。

回到0/1背包的原問題上（如果你忘了就去上面看看）。

如果在不知道這個模型的情況下我們怎么做這個題呢？

這就要用到第一節(jié)提到的方法二：三要素法。

題目中明確說明對于一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿（用0表示）或拿（用1表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應該是很輕松的了。

那么階段是什么呢？

顯然，給你一堆東西讓你往包里塞，你當然是一個一個的那來，塞進去。那么階段很明顯就是物品的個數(shù)。

狀態(tài)又是什么呢？

有的人在裝東西是有個習慣（比如說我）就是先把東西分類，然后把同類的東西打個小包，最后在把小包放進去，我們可以按這個思想給物品打一些小包，也就是按照單位為1的遞增的順序準備好多小包，比如載重是6的包，可以為它準備載重是1，2，3，4，5的小包。這樣狀態(tài)就可以想出來了：

設計狀態(tài)opt[i，j]表示裝第i個物品時載重為j的包可以裝到的最大價值。

opt[i-1,j]                     (j-w[i]<0，i>0)

狀態(tài)轉(zhuǎn)移方程：opt[i,j]=

max{opt[i-1,j],opt[i-1,j-w[i]]+v[i]} (j-w[i]>=0,i>0)

(w[i]:第i個物品的重量，v[i]第i個物品的價值)

解釋：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個物品，比不裝獲得的價值大就裝上它。

邊界條件：opt[0,i]=0; (i∈{1..S})

注：

這種二維的狀態(tài)表示應該在下節(jié)講，但是為了方便理解先在這里說了。

上面的方法動態(tài)規(guī)劃三要素都很明顯，實現(xiàn)也很簡單。但是在我初學背包時卻用另外一種一維的狀態(tài)表示法。

用第一節(jié)說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：

怎么放寬約束呢？

把題目中的價值去掉，不考慮價值即最優(yōu)就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？

再一次增加約束：背包只能裝滿。

顯然對于N個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那么裝不滿怎么辦呢？其實裝不滿背包，它總要達到一定的重量（X）。我們可以把這種情況看作是裝滿一個載重為X的小包。

總結(jié)一下上面的思維過程：

放寬約束讓我們找到問題的突破口——和背包問題簡化版一樣，我們可以卻定載重為S的背包是否可以裝滿。

增加約束讓我們找到問題的求解方法——在裝滿背包的方案中選擇最優(yōu)的一個方案。

這樣問題就解決了。

設計一個狀態(tài)opt[j]表示裝滿載重為j的背包可獲得的最大價值。對于第i個物品，只要opt[j-w[i]]可以裝滿且opt[j-w[i]]+v[i]比opt[j]大就裝上這個物品（更新opt[j]）。

怎么使opt[j]既有是否構(gòu)成又有最優(yōu)的概念呢？

opt[j]只表示最優(yōu)，只不過使初始條件+1，判斷opt[j]是否為0，如果opt[j]=0說明j裝不滿。

邊界條件：opt[0]=1;

狀態(tài)轉(zhuǎn)移方程：opt[j]=max{opt[j-w[i]]} (0<i<n,w[i]<=j<=S)

問題解： ans=max{opt[i]}-1          (0<i<=s)

時間復雜度：階段數(shù)O(S)*狀態(tài)數(shù)（O(N)）*轉(zhuǎn)移代價（O(1)）=O（SN）

下面看幾個例題：

例題8   采藥   (medic.pas/c/cpp)   來源：NOIP2005（普及組） 第三題

【問題描述】

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個難題。醫(yī)師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大?！?/span>

如果你是辰辰，你能完成這個任務嗎？

【輸入文件】

輸入文件medic.in的第一行有兩個整數(shù)T（1 <= T <= 1000）和M（1 <= M <= 100），用一個空格隔開，T代表總共能夠用來采藥的時間，M代表山洞里的草藥的數(shù)目。接下來的M行每行包括兩個在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時間和這株草藥的價值。

【輸出文件】

輸出文件medic.out包括一行，這一行只包含一個整數(shù)，表示在規(guī)定的時間內(nèi)，可以采到的草藥的最大總價值。

【輸入樣例】

70 3

71 100

69 1

1 2

【輸出樣例】

3

【數(shù)據(jù)規(guī)?！?/span>

對于30%的數(shù)據(jù)，M <= 10；

對于全部的數(shù)據(jù)，M <= 100。

【問題分析】

這是一道典型的0/1背包問題，把時間看做標準模型中的重量，把規(guī)定的時間看做載重為T的背包，這樣問題和基本模型就一樣了，具體實現(xiàn)這里不多說了。

【源代碼1】 {二維狀態(tài)}

program medic;

const

fin='medic.in';

fout='medic.out';

maxt=1010;

maxn=110;

var

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

w,v:array[0..maxn] of longint;

t,n:longint;

procedure init;

var

i:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

read(t,n);

for i:=1 to n do

read(w[i],v[i]);

close(input);

end;

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

begin

if x>y then max:=x

else max:=y;

end;

procedure main;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

for i:=1 to n do

for j:=1 to t do

if j-w[i]<0 then

opt[i,j]:=opt[i-1,j]

else opt[i,j]:=max(opt[i-1,j],opt[i-1,j-w[i]]+v[i]);

end;

procedure print;

begin

writeln(opt[n,t]);

close(output);

end;

begin

init;

main;

print;

end.

【源代碼2】 {一維狀態(tài)}

program medic;

const

fin='medic.in';

fout='medic.out';

maxt=1010;

maxn=110;

var

opt:array[0..maxt] of longint;

w,v:array[0..maxn] of longint;

ans,t,n:longint;

procedure init;

var

i:longint;

begin

assign(input,fin);

reset(input);

assign(output,fout);

rewrite(output);

readln(t,n);

for i:=1 to n do

read(w[i],v[i]);

close(input);

end;

procedure main;

var

i,j:longint;

begin

fillchar(opt,sizeof(opt),0);

opt[0]:=1;

for i:=1 to n do

for j:=t downto w[i] do

if (opt[j-w[i]]>0) and (opt[j-w[i]]+v[i]>opt[j]) then

opt[j]:=opt[j-w[i]]+v[i];

ans:=-maxlongint;

for i:=1 to t do

if opt[i]>ans then ans:=opt[i];

end;

procedure print;

begin

writeln(ans-1);

close(output);

end;

begin

init;

main;

print;

end.