DP - Red Huang

動態規劃經典教程
引言：本人在做過一些題目後對 DP 有些感想，就寫了這個總結：
第一節動態規劃基本概念
一，動態規劃三要素：階段，狀態，決策。
他們的概念到處都是，我就不多說了，我只說說我對他們的理解：
如果把動態規劃的求解過程看成一個工廠的生產線，階段就是生產某個商品的不同的環節，狀態就是工件當前的形態，決策就是對工件的操作。顯然不同階段是對產品的一個前面各個狀態的小結，有一個個的小結構成了最終的整個生產線。每個狀態間又有關聯（下一個狀態是由上一個狀態做了某個決策後產生的）。
下面舉個例子：
要生產一批雪糕，在這個過程中要分好多環節：購買牛奶，對牛奶提純處理，放入工廠加工，加工後的商品要包裝，包裝後就去銷售……，這樣每個環節就可以看做是一個階段；產品在不同的時候有不同的狀態，剛開始時只是白白的牛奶，進入生產後做成了各種造型，從冷凍庫拿出來後就變成雪糕（由液態變成固態 =_=||）。每個形態就是一個狀態，那從液態變成固態經過了冰凍這一操作，這個操作就是一個決策。
一個狀態經過一個決策變成了另外一個狀態，這個過程就是狀態轉移，用來描述狀態轉移的方程就是狀態轉移方程。
經過這個例子相信大家對動態規劃有所了解了吧。
下面再說說我對動態規劃的另外一個理解：
用圖論知識理解動態規劃：把動態規劃中的狀態抽象成一個點，在有直接關聯的狀態間連一條有向邊，狀態轉移的代價就是邊上的權。這樣就形成了一個有向無環圖 AOE 網（為什麼無環呢？往下看）。對這個圖進行拓撲排序，刪除一個邊後同時出現入度為 0 的狀態在同一階段。這樣對圖求最優路徑就是動態規劃問題的求解。
二，動態規劃的適用範圍
動態規劃用於解決多階段決策最優化問題，但是不是所有的最優化問題都可以用動態規劃解答呢？
一般在題目中出現求最優解的問題就要考慮動態規劃了，但是否可以用還要滿足兩個條件：
最優子結構（最優化原理）
無後效性
最優化原理在下面的最短路徑問題中有詳細的解答；
什麼是無後效性呢？
就是說在狀態 i 求解時用到狀態 j 而狀態 j 就解有用到狀態 k….. 狀態 N。
而求狀態 N 時有用到了狀態 i 這樣求解狀態的過程形成了環就沒法用動態規劃解答了，這也是上面用圖論理解動態規劃中形成的圖無環的原因。
也就是說當前狀態是前面狀態的完美總結，現在與過去無關。。。
當然，有是換一個劃分狀態或階段的方法就滿足無後效性了，這樣的問題仍然可以用動態規劃解。
三，動態規劃解決問題的一般思路。
拿到多階段決策最優化問題後，第一步要判斷這個問題是否可以用動態規劃解決，如果不能就要考慮搜索或貪心了。當確定問題可以用動態規劃後，就要用下面介紹的方法解決問題了：
（1）模型匹配法：
最先考慮的就是這個方法了。挖掘問題的本質，如果發現問題是自己熟悉的某個基本的模型，就直接套用，但要小心其中的一些小的變動，現在考題辦都是基本模型的變形套用時要小心條件，三思而後行。這些基本模型在先面的分類中將一一介紹。
（2）三要素法
仔細分析問題嘗試著確定動態規劃的三要素，不同問題的確定方向不同：
先確定階段的問題：數塔問題，和走路問題（詳見解題報告）
先確定狀態的問題：大多數都是先確定狀態的。
先確定決策的問題：背包問題。（詳見解題報告）
一般都是先從比較明顯的地方入手，至於怎麼知道哪個明顯就是經驗問題了，多做題就會發現。
（3）尋找規律法：
這個方法很簡單，耐心推幾組數據後，看他們的規律，總結規律間的共性，有點貪心的意思。
（4）邊界條件法
找到問題的邊界條件，然後考慮邊界條件與它的鄰接狀態之間的關係。這個方法也很有效。
（5）放寬約束和增加約束
這個思想是在陳啟鋒的論文裡看到的，具體內容就是給問題增加一些條件或刪除一些條件使問題變得清晰。
第二節動態規劃分類討論
這裡用狀態維數對動態規劃進行了分類：
1. 狀態是一維的
1．1 下降 / 非降子序列問題：
問題描述： {挖掘題目的本質，一旦抽象成這樣的描述就可以用這個方法解}
在一個無序的序列 a1,a2,a3,a4…an 裡，找到一個最長的序列滿足：ai<=aj<=ak…<=am, 且 i<j<k…aj>ak…>am, 且 i>j>k…>m.（最長下降子序列）。
問題分析：
如果前 i-1 個數中用到 ak (ak>ai 或 aj<=ai)，opt [j]+1 就是 opt [i] 的值；用方程表示為：{我習慣了這種寫法，但不是狀態轉移方程的標準寫法 }
opt [i]=max (opt [j])+1 (0<=j<i 且 aj<=ai) {最長非降子序列}
opt [i]=max (opt [j])+1 (0<=j<i 且 aj>ai) {最長下降子序列}
實現求解的部分代碼：
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 為最終解}
複雜度：從上面的實現不難看出時間複雜度為 O（N2），空間複雜度 O（N）；_

例題 1 攔截導彈 (missile.pas/c/cpp) 來源：NOIP1999 (提高組) 第一題
【問題描述】
某國為了防禦敵國的導彈襲擊，發展出一種導彈攔截系統。但是這種導彈攔截系統有一個缺陷：雖然它的第一發砲彈能夠到達任意的高度，但是以後每一發砲彈都不能高於前一發的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有一套系統，因此有可能不能攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大於 30000 的正整數），計算這套系統最多能攔截多少導彈，如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。
【輸入文件】missile.in
單獨一行列出導彈依次飛來的高度。
【輸出文件】missile.out
兩行，分別是最多能攔截的導彈數，要攔截所有導彈最少要配備的系統數
【輸入樣例】
389 207 155 300 299 170 158 65
【輸出樣例】
6
2
【問題分析】
有經驗的選手不難看出這是一個求最長非升子序列問題，顯然標準算法是動態規劃。
以導彈依次飛來的順序為階段，設計狀態 opt [i] 表示前 i 個導彈中攔截了導彈 i 可以攔截最多能攔截到的導彈的個數。
狀態轉移方程：
opt[i]=max(opt[j])+1 (h[i]>=h[j],0=<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]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+1>…>TK (1<=i<=K)。
你的任務是，已知所有 N 位同學的身高，計算最少需要幾位同學出列，可以使得剩下的同學排成合唱隊形。
【輸入文件】
輸入文件 chorus.in 的第一行是一個整數 N (2<=N<=100)，表示同學的總數。第一行有 n 個整數，用空格分隔，第 i 個整數 Ti (130<=Ti<=230) 是第 i 位同學的身高 (釐米)。
【輸出文件】
輸出文件 chorus.out 包括一行，這一行只包含一個整數，就是最少需要幾位同學出列。
【樣例輸入】
8
186 186 150 200 160 130 197 220
【樣例輸出】
4
【數據規模】
對於 50% 的數據，保證有 n<=20；
對於全部的數據，保證有 n<=100。
【問題分析】
出列人數最少，也就是說留的人最多，也就是序列最長。
這樣分析就是典型的最長下降子序列問題。只要枚舉每一個人站中間時可以的到的最優解。顯然它就等於，包括他在內向左求最長上升子序列，向右求最長下降子序列。
我們看一下複雜度：
計算最長下降子序列的複雜度是 O（N2），一共求 N 次，總複雜度是 O（N3）。這樣的複雜度對於這個題的數據範圍來說是可以 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[0..maxn] of longint;
n,ans;
procedure init;
var
i;
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;
begin
a[0]:=-maxlongint;
for i:=1 to n do
for j:=i-1 downto 0 do
if (a[j]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]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
【問題描述】
「逢低吸納」是炒股的一條成功秘訣。如果你想成為一個成功的投資者，就要遵守這條秘訣:
"逢低吸納，越低越買"
這句話的意思是：每次你購買股票時的股價一定要比你上次購買時的股價低。按照這個規則購買股票的次數越多越好，看看你最多能按這個規則買幾次。
給定連續的 N 天中每天的股價。你可以在任何一天購買一次股票，但是購買時的股價一定要比你上次購買時的股價低。寫一個程序，求出最多能買幾次股票。
以下面這個表為例，某幾天的股價是:
天數 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 次股票。一種買法如下 (可能有其他的買法):
天數 2 5 6 10
股價 69 68 64 62
【輸入文件】buylow.in
第 1 行: N (1 <= N =a [j],0=<j<i) {a [i] 存第 i 天股價}
最大的 opt [i] 就是最終的解。
第二問呢，稍麻煩一點。
從問題的邊界出發考慮問題，當第一問求得一個最優解 opt [i]=X 時，
在 1 到 N 中如果還有另外一個 opt [j]=x 那麼選取 J 的這個方案肯定是成立的。
是不是統計所有的 opt [j]=x 的個數就是解了呢？
顯然沒那麼簡單，因為選取Ｊ這天的股票構成的方案不見得＝１，看下面一個例子：
５　6 4　3　１ 2
方案一：５４３１
方案二：５４３２
方案三：６４３１
方案四：６４３２
x=4
也就是所雖然 opt [5]=X 和 opt [6]=X 但個數隻有兩個，而實際上應該有四個方案，但在仔細觀察發現，構成 opt [5]=x 的這個方案中 opt [j]=x-1 的方案數有兩個，opt [j]=x-2 的有一個，opt [j]=x-3 的有一個……
顯然這是滿足低歸定義的設計函數 F（i）表示前 I 張中用到第 i 張股票的方案數。
遞推式：
1 (i=0)
F(i)=
Sum (F (j)) (0<=ja [i],opt [j]=opt [i]-1) {sum 代表求和}
答案 = sum (F (j)) {0<ja [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;
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) 來源：《奧賽經典》（提高篇）
【問題描述】
PALMIA 國家被一條河流分成南北兩岸，南北兩岸上各有 N 個村莊。北岸的每一個村莊有一個唯一的朋友在南岸，且他們的朋友村莊彼此不同。
每一對朋友村莊想要一條船來連接他們，他們向政府提出申請以獲得批准。由於河面上常常有霧，政府決定禁止船隻航線相交（如果相交，則很可能導致碰船）。
你的任務是編寫一個程序，幫助政府官員決定批准哪些船隻航線，使得不相交的航線數目最大。
【輸入文件】ships.in
輸入文件由幾組數據組成。每組數據的第一行有 2 個整數 X，Y，中間有一個空格隔開，X 代表 PALMIA 河的長度（10<=X<=6000），Y 代表河的寬度（10<=Y<=100）。第二行包含整數 N，表示分別坐落在南北兩岸上的村莊的數目（1<=N<=5000）。在接下來的 N 行中，每一行有兩個非負整數 C，D，由一個空格隔開，分別表示這一對朋友村莊沿河岸與 PALMIA 河最西邊界的距離（C 代表北岸的村莊，D 代表南岸的村莊），不存在同岸又同位置的村莊。最後一組數據的下面僅有一行，是兩個 0，也被一空格隔開。
【輸出文件】ships.out
對輸入文件的每一組數據，輸出文件應在連續的行中表示出最大可能滿足上述條件的航線的數目。
【輸入樣例】
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
【輸出樣例】
4
【問題分析】
這道題目相對來說思考難度較高，從字面意義上看不出問題的本質來，有點無法下手的感覺。這裡我給大家推薦兩種思考這類問題的方法。
法一：尋找規律法（我前面總結提到的第 3 個方法）
尋找規律自然要推幾組數據，首先當然有從樣例入手；

仔細觀察上圖：紅色航線是合法的，那麼他們滿足什麼規律呢？
C1 C2 C3 C4
北岸紅線的端點： 4 9 15 17
南岸紅線的端點： 2 8 12 17
D1 D2 D3 D4
不難看出無論線的斜率如何，都有這樣的規律：
C1<C2<C3<C4 且 D1<D2<D3<D4
如果我們把輸入數據排升序，問題變抽象為：
在一個序列（D）裡找到最長的序列滿足 DI<DJ<Dk…… 且 i<j<k
這樣的話便是典型的最長非降子序列問題了。。。。
法二：邊界條件法（我前面總結提到的第 4 個方法）
邊界法其實就是把數據往小了縮，顯然 N=1 是答案是 1。N=2 時呢？
考慮這樣一組數據：
N=2
C1 D1
C2 D2
當 C1D2 那麼一定會相交，反之則不會相交。
當 C1 >C2 時，如果 D1<D2 那麼一定會相交，反之則不會相交。
N=3
C1 D1
C2 D2
C3 D3
……
其實不用在推導 N=3 了，有興趣的可以推導去。看 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;
end;
var
x,y,n,ans;
a[0..maxn] of retype;
opt[0..maxn] of longint;
procedure init;
var
i;
begin
readln(n);
for i:=1 to n do
read(a[i].c,a[i].d);
end;
procedure quick(L,r);
var
i,j,x;
y;
begin
i:=L;
j:=r;
x:=a[(i+j) div 2].c;
repeat
while a[i].cx do
dec(j);
if ij;
if j>L then quick(L,j);
if i<r then quick(i,r);
end;
procedure main;
var
i,j;
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].dopt[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+y0) do
begin
init;
main;
read(x,y);
end;
close(input);
close(output);
end.

1.2 背包問題
首先說說背包問題的基本模型：
現有 N 個物品，每個物品的價值為 V，重量為 W。求用一個載重量為 S 的背包裝這些物品，使得所裝物品的總價值最高。
背包問題用貪心和搜索解，當然效果不佳，不過在我的貪心和搜索總結中會說到。顯然標準的解法是動態規劃，我在解決這個問題時習慣設計一維狀態，還可以設計二維的，二維狀態在下面會講，現在只討論用一維狀態實現背包問題。
背包問題的分類：
(1) 小數背包：物品的重量是實數，如油，水等可以取 1.67 升……
(2) 整數背包：0/1 背包：每個物品只能選一次，或不選。不能只選一部分
部分背包：所選物品可以是一部分。
(3) 多重背包：背包不只一個。
小數背包：在貪心總結中會細講。
整數背包：
部分背包：同小數背包。
0/1 背包：這個問題是最經常出現的問題，應該熟練掌握。
我們先看一下 0/1 背包的簡化版：
現有 N 個物品，每個物品重量為 W，這些物品能否使在載重量為 S 的背包裝滿（即重量和正好為 S）？如果不能那能使物品重量和最重達到多少？
針對這一問題我們以物品的個數分階段，設計一個狀態 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 了。
這樣劃分階段，設計狀態，滿足無後效性和麼？
顯然對於每一個階段都是獨立的，物品的順序並不影響求解，因為裝物品的次序不限。而對於 opt [j] 只考慮 opt [j-w [i]] 而不考慮後面的，所以滿足無後效性。
有了上面的分析不難寫出狀態轉移方程：
opt[j]:=opt[j-w[1]] {opt[j-w[i]]=true}
時間複雜度：
階段數 O (S)* 狀態數（O (N)）* 轉移代價（O (1)）=O（SN）
下面看幾個例題：

例題 5 裝箱問題 (pack.pas/c/cpp) 來源：NOIP2001 (普及組) 第四題
【問題描述】
有一個箱子容量為 V（正整數，0＜＝V＜＝20000），同時有 n 個物品（0＜n＜＝30＝，每個物品有一個體積（正整數）。
要求 n 個物品中，任取若干個裝入箱內，使箱子的剩餘空間為最小。
【輸入文件】
第一行一個正整數 V 表示箱子的容量，第二行一個正整數 N 表示物品個數，接下來 N 行列出這 N 個物品各自的體積。
【輸出文件】
單獨一行，表示箱子最小的剩餘空間。
【輸入樣例】
24
6
8
3
12
7
9
7
【輸出樣例】
0
【問題分析】
本題是經典的 0/1 背包問題，並且是 0/1 背包的簡化版，把箱子看做背包，容量看做載重量，體積看做重量，剩餘空間最小也就是儘量裝滿背包。於是這個問題便成了：
有一個載重量為 V 的背包，有 N 個物品，儘量多裝物品，使背包儘量的重。
設計一個狀態 opt [i] 表示重量 i 可否構成。
狀態轉移方程：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[0..maxv] of boolean;
w[0..maxn] of longint;
v,n,x;
procedure init;
var
i;
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;
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），用他們能稱出的重量的種類數。
【輸入文件】
a1 a2 a3 a4 a5 a6
（表示 1g 砝碼有 a1 個，2g 砝碼有 a2 個，…，20g 砝碼有 a6 個，中間有空格）。
【輸出文件】
Total=N
（N 表示用這些砝碼能稱出的不同重量的個數，但不包括一個砝碼也不用的情況）。
【輸入樣例】
1 1 0 0 0 0
【輸出樣例】
TOTAL=3
【問題分析】
把問題稍做一個改動，已知 a1+a2+a3+a4+a5+a6 個砝碼的重量 w [i], w [i]∈{ 1,2,3,5,10,20} 其中砝碼重量可以相等，求用這些砝碼可稱出的不同重量的個數。
這樣一改就是經典的 0/1 背包問題的簡化版了，求解方法完全和上面說的一樣，只是要注意這個題目不是求最大載重量，是統計所有的可稱出的重量的個數。

【源代碼 1】
program P4;
const
maxn=1010;
w[1..6] of longint=(1,2,3,5,10,20);
var
opt[0..maxn] of boolean;
a[1..6] of longint;
procedure init;
var
i;
begin
for i:=1 to 6 do
read(a[i]);
end;
procedure main;
var
i,j,k;
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;
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 還聰明的孩子，他發現壘城堡的時候，如果下面的積木比上面的積木大，那麼城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規則。
小 XC 想把自己壘的城堡送給幼兒園裡漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執。可是他發現自己在壘城堡的時候並沒有預先考慮到這一點。所以他現在要改造城堡。由於他沒有多餘的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最後的城堡都儘可能的高。
任務：
請你幫助小 XC 編一個程序，根據他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。
【輸入文件】
第一行是一個整數 N (N0 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.

回顧上面的內容充分說明動態規劃的本質就是遞推。其實按照我的理解（動規涉及最優決策，遞推是單純的總結）背包問題的簡化版更準確點算是遞推而非動態規劃，至於動歸和遞推之間的界線本來就很模糊（至少我這麼認為）把它看做什麼都可以，沒必要咬文嚼字。
回到 0/1 背包的原問題上（如果你忘了就去上面看看）。
如果在不知道這個模型的情況下我們怎麼做這個題呢？
這就要用到第一節提到的方法二：三要素法。
題目中明確說明對於一個物品要不就拿走要不就放下，其實題目赤裸裸的告訴我們決策就是不拿（用 0 表示）或拿（用 1 表示）。這樣想都不用想就知道了決策，這也是本題的突破口。知道了決策寫個搜索的程序應該是很輕鬆的了。
那麼階段是什麼呢？
顯然，給你一堆東西讓你往包裡塞，你當然是一個一個的那來，塞進去。那麼階段很明顯就是物品的個數。
狀態又是什麼呢？
有的人在裝東西是有個習慣（比如說我）就是先把東西分類，然後把同類的東西打個小包，最後在把小包放進去，我們可以按這個思想給物品打一些小包，也就是按照單位為 1 的遞增的順序準備好多小包，比如載重是 6 的包，可以為它準備載重是 1，2，3，4，5 的小包。這樣狀態就可以想出來了：
設計狀態 opt [i，j] 表示裝第 i 個物品時載重為 j 的包可以裝到的最大價值。
opt[i-1,j] (j-w[i]0)
狀態轉移方程：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})
註：
這種二維的狀態表示應該在下節講，但是為了方便理解先在這裡說了。
上面的方法動態規劃三要素都很明顯，實現也很簡單。但是在我初學背包時卻用另外一種一維的狀態表示法。
用第一節說的思考方法五（放寬約束和增加約束）在重新思考一下這個問題：
怎麼放寬約束呢？
把題目中的價值去掉，不考慮價值即最優就變成背包問題的簡化版了。那簡化版的求解對我們有何啟示呢？
再一次增加約束：背包只能裝滿。
顯然對於 N 個裝滿背包的方案中只要找到一個價值最大的就是問題的解。那麼裝不滿怎麼辦呢？其實裝不滿背包，它總要達到一定的重量（X）。我們可以把這種情況看作是裝滿一個載重為 X 的小包。
總結一下上面的思維過程：
放寬約束讓我們找到問題的突破口 —— 和背包問題簡化版一樣，我們可以卻定載重為 S 的背包是否可以裝滿。
增加約束讓我們找到問題的求解方法 —— 在裝滿背包的方案中選擇最優的一個方案。
這樣問題就解決了。
設計一個狀態 opt [j] 表示裝滿載重為 j 的背包可獲得的最大價值。對於第 i 個物品，只要 opt [j-w [i]] 可以裝滿且 opt [j-w [i]]+v [i] 比 opt [j] 大就裝上這個物品（更新 opt [j]）。
怎麼使 opt [j] 既有是否構成又有最優的概念呢？
opt [j] 只表示最優，只不過使初始條件 + 1，判斷 opt [j] 是否為 0，如果 opt [j]=0 說明 j 裝不滿。
邊界條件：opt [0]=1;
狀態轉移方程：opt [j]=max {opt [j-w [i]]} (0<i<n,w [i]<=j<=S)
問題解： ans=max {opt [i]}-1 (0<i<=s)
時間複雜度：階段數 O (S)* 狀態數（O (N)）* 轉移代價（O (1)）=O（SN）
下面看幾個例題：

例題 8 採藥 (medic.pas/c/cpp) 來源：NOIP2005（普及組）第三題
【問題描述】
辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞裡對他說：「孩子，這個山洞裡有一些不同的草藥，采每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間裡，你可以采到一些草藥。如果你是一個聰明的孩子，你應該可以讓采到的草藥的總價值最大。」
如果你是辰辰，你能完成這個任務嗎？
【輸入文件】
輸入文件 medic.in 的第一行有兩個整數 T（1 <= T <= 1000）和 M（1 <= M <= 100），用一個空格隔開，T 代表總共能夠用來採藥的時間，M 代表山洞裡的草藥的數目。接下來的 M 行每行包括兩個在 1 到 100 之間（包括 1 和 100）的整數，分別表示採摘某株草藥的時間和這株草藥的價值。
【輸出文件】
輸出文件 medic.out 包括一行，這一行只包含一個整數，表示在規定的時間內，可以采到的草藥的最大總價值。
【輸入樣例】
70 3
71 100
69 1
1 2
【輸出樣例】
3
【數據規模】
對於 30% 的數據，M <= 10；
對於全部的數據，M y then max:=x
else max:=y;
end;
procedure main;
var
i,j;
begin
fillchar(opt,sizeof(opt),0);
for i:=1 to n do
for j:=1 to t do
if 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;

例題 9 開心的金明來源：NOIP2006（普及組）第二題
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間他自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過 N 元錢就行」。今天一早金明就開始做預算，但是他想買的東西太多了，肯定會超過媽媽限定的 N 元。於是，他把每件物品規定了一個重要度，分為 5 等：用整數 1~5 表示，第 5 等最重要。他還從因特網上查到了每件物品的價格（都是整數元）。他希望在不超過 N 元（可以等於 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。設第 j 件物品的價格為 v [j]，重要度為 w [j]，共選中了 k 件物品，編號依次為 j1…jk，則所求的總和為：v [j1]*w [j1]+..+v [jk]*w [jk] 請你幫助金明設計一個滿足要求的購物單.
【輸入文件】
輸入的第 1 行，為兩個正整數，用一個空格隔開： N m
（其中 N（<30000）表示總錢數，m (<25) 為希望購買物品的個數。）
從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數據，每行有 2 個非負整數 v p
（其中 v 表示該物品的價格（v≦10000），p 表示該物品的重要度（1~5））
【輸出文件】
輸出只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（=0) 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;
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.

例題 10 金明的預算方案 (budget.pas/c/cpp) 來源：NOIP2006 第二題
【問題描述】
金明今天很開心，家裡購置的新房就要領鑰匙了，新房裡有一間金明自己專用的很寬敞的房間。更讓他高興的是，媽媽昨天對他說：「你的房間需要購買哪些物品，怎麼佈置，你說了算，只要不超過 N 元錢就行」。今天一早，金明就開始做預算了，他把想買的物品分為兩類：主件與附件，附件是從屬於某個主件的，下表就是一些主件與附件的例子：
主件附件
電腦打印機，掃瞄儀
書櫃圖書
書桌檯燈，文具
工作椅無
如果要買歸類為附件的物品，必須先買該附件所屬的主件。每個主件可以有 0 個、1 個或 2 個附件。附件不再有從屬於自己的附件。金明想買的東西很多，肯定會超過媽媽限定的 N 元。於是，他把每件物品規定了一個重要度，分為 5 等：用整數 1~5 表示，第 5 等最重要。他還從因特網上查到了每件物品的價格（都是 10 元的整數倍）。他希望在不超過 N 元（可以等於 N 元）的前提下，使每件物品的價格與重要度的乘積的總和最大。
設第 j 件物品的價格為 v [j]，重要度為 w [j]，共選中了 k 件物品，編號依次為 j1，j2，……，jk，則所求的總和為：
v [j1]*w [j1]+v [j2]*w [j2]+ …+v [jk]*w [jk]。（其中 * 為乘號）
請你幫助金明設計一個滿足要求的購物單。
【輸入文件】
輸入文件 budget.in 的第 1 行，為兩個正整數，用一個空格隔開：
N m （其中 N（<32000）表示總錢數，m（<60）為希望購買物品的個數。）
從第 2 行到第 m+1 行，第 j 行給出了編號為 j-1 的物品的基本數據，每行有 3 個非負整數： v p q
（其中 v 表示該物品的價格（v≦10000），p 表示該物品的重要度（1~5），q 是所屬主件的編號）
【輸出文件】
輸出文件 budget.out 只有一個正整數，為不超過總錢數的物品的價格與重要度乘積的總和的最大值（=0) 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;
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.