DP - Red Huang

動的計畫法の古典的なチュートリアル
序論：私はいくつかの問題を解いた後、DP についての感想を持ち、この要約を書きました：
第 1 節動的計画法の基本概念

動的計画法の三要素：段階、状態、決定。
彼らの概念は至る所にありますので、私は多くを語りませんが、彼らに対する私の理解を述べます：
動的計画法の解決プロセスを工場の生産ラインと見なすと、段階は特定の製品を生産する異なる環節、状態は部品の現在の形態、決定は部品の操作です。明らかに、異なる段階は製品の前の各状態の小結であり、各小結が最終的な全体の生産ラインを構成します。各状態間には関連があります（次の状態は前の状態が特定の決定を行った後に生成されます）。
以下に例を示します：
アイスクリームのバッチを生産するには、多くの環節に分ける必要があります：牛乳を購入し、牛乳を精製処理し、工場に入れて加工し、加工後の商品を包装し、包装後に販売する…… このように、各環節は段階と見なすことができます；製品は異なる時点で異なる状態を持ち、最初はただの白い牛乳であり、生産に入るとさまざまな形状になり、冷凍庫から取り出すとアイスクリームに変わります（液体から固体に変わる）。各形態は一つの状態であり、液体から固体に変わる過程で凍結という操作を経て、この操作は一つの決定です。
一つの状態が一つの決定を経て別の状態に変わるこのプロセスは状態遷移と呼ばれ、状態遷移を記述する方程式は状態遷移方程式です。
この例を通じて、皆さんは動的計画法について理解できたと思います。
次に、動的計画法に対する私の別の理解を述べます：
グラフ理論の知識を用いて動的計画法を理解する：動的計画法の状態を点として抽象化し、直接関連する状態の間に有向辺を引き、状態遷移のコストは辺の重みです。このようにして、有向非循環グラフ AOE ネットワークが形成されます（なぜ非循環なのかは、下を見てください）。このグラフにトポロジカルソートを行い、辺を一つ削除すると同時に入次数が 0 の状態が同じ段階に現れます。このようにして、グラフの最適経路を求めることが動的計画法問題の解決になります。
動的計画法の適用範囲
動的計画法は多段階の決定最適化問題を解決するために使用されますが、すべての最適化問題が動的計画法で解決できるわけではありません。
一般に問題の中で最適解を求めることが出てきた場合は、動的計画法を考慮する必要がありますが、使用できるかどうかは 2 つの条件を満たす必要があります：
最適部分構造（最適化原理）
無後效性
最適化原理は以下の最短経路問題で詳細に解答されています；
無後效性とは何か？
状態 i を解決する際に状態 j を使用し、状態 j が状態 k を使用し、…… 状態 N を使用することを意味します。
状態 N を求める際に状態 i を使用する場合、このような状態の解決プロセスが環を形成するため、動的計画法で解決できなくなります。これが上記のグラフ理論を用いて動的計画法を理解する際に形成されるグラフが非循環である理由です。
つまり、現在の状態は前の状態の完璧な要約であり、現在と過去は無関係です。。。
もちろん、別の方法で状態や段階を分割すれば無後效性を満たすことができ、そのような問題は動的計画法で解決できます。
動的計画法で問題を解決する一般的な考え方。
多段階の決定最適化問題を受け取った後、最初のステップはこの問題が動的計画法で解決できるかどうかを判断することです。解決できない場合は、探索や貪欲法を考慮する必要があります。問題が動的計画法で解決できることが確定したら、以下で紹介する方法で問題を解決する必要があります：
（1）モデルマッチング法：
最初に考慮するのはこの方法です。問題の本質を掘り下げ、問題が自分がよく知っている基本的なモデルのいずれかであることがわかった場合は、直接適用しますが、その中のいくつかの小さな変動には注意が必要です。現在の試験問題は基本モデルの変形を適用する際に条件に注意し、慎重に行動する必要があります。これらの基本モデルは前の分類で一つ一つ紹介されます。
（2）三要素法
問題を注意深く分析し、動的計画法の三要素を特定しようとします。異なる問題の確定方向は異なります：
最初に段階の問題を特定する：数塔問題、歩行問題（詳細は解題報告を参照）
最初に状態の問題を特定する：ほとんどが最初に状態を特定します。
最初に決定の問題を特定する：ナップサック問題。（詳細は解題報告を参照）
一般的には、比較的明らかな場所から始めますが、どの明らかさを知るかは経験の問題であり、多くの問題を解くことで発見します。
（3）規則を探す方法：
この方法は非常に簡単で、数組のデータを辛抱強く推測した後、彼らの規則を見て、規則間の共通性をまとめます。少し貪欲な意味があります。
（4）境界条件法
問題の境界条件を見つけ、次に境界条件とその隣接状態との関係を考えます。この方法も非常に効果的です。
（5）制約を緩和し、制約を追加する
この考え方は陳啟鋒の論文で見たもので、具体的な内容は問題にいくつかの条件を追加したり、いくつかの条件を削除したりして問題を明確にすることです。
第 2 節動的計画法の分類と議論
ここでは状態の次元に基づいて動的計画法を分類しました：
状態は 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 または akai（または 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_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（上級組）第一題
【問題の説明】
ある国は敵国のミサイル攻撃を防ぐために、ミサイル迎撃システムを開発しました。しかし、このミサイル迎撃システムには欠陥があります：最初の弾は任意の高さに到達できますが、その後の各弾は前の弾の高さを超えることができません。ある日、レーダーが敵国のミサイルの襲来をキャッチしました。このシステムはまだ試用段階にあるため、システムは 1 セットしかなく、すべてのミサイルを迎撃できない可能性があります。
ミサイルが飛来する高さを入力し（レーダーが提供する高さデータは 30,000 を超えない正の整数）、このシステムが最大で何発のミサイルを迎撃できるか、すべてのミサイルを迎撃するために最低何セットのミサイル迎撃システムを装備する必要があるかを計算します。
【入力ファイル】missile.in
単独の行に、ミサイルが飛来する高さを列挙します。
【出力ファイル】missile.out
2 行、最大で迎撃できるミサイルの数、すべてのミサイルを迎撃するために最低必要なシステムの数をそれぞれ出力します。
【入力例】
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]) {最長非上昇部分列}
opt [i]=max (opt [j])+1 (0<=j_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）；_

例題 2 合唱隊形 (chorus.pas/c/cpp) 出典：NOIP2004（上級組）第一題
N 人の学生が一列に並び、音楽の先生はその中から (N-K) 人の学生を選び出し、残りの K 人の学生を合唱隊形に並べることを求めています。
合唱隊形とは、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 番目の学生の身長（cm）です。
【出力ファイル】
出力ファイル chorus.out には 1 行が含まれ、最小限の人数が出列する必要があることを示す整数が含まれています。
【サンプル入力】
8
186 186 150 200 160 130 197 220
【サンプル出力】
4
【データ規模】
50％のデータに対して、n<=20 が保証されています；
すべてのデータに対して、n<=100 が保証されています。
【問題の分析】
出列人数が最小であるということは、残る人数が最大であるということです。
このように分析すると、典型的な最長減少部分列問題になります。各人が中央に立っているときに得られる最適解を求めることができます。
明らかに、最長減少（上昇）部分列は中間の人の影響を受けません。
最長減少（上昇）部分列を求めるには、OPT1 を使用して最長上昇部分列を 1 回求め、OPT2 を使用して最長下降部分列を 1 回求めます。これにより、答えは 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 回購入できますが、購入時の株価は前回購入時の株価よりも低くなければなりません。プログラムを書いて、最大で何回株式を購入できるかを求めてください。
以下の表は、ある数日の株価です：
日数 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 [5]=X と opt [6]=X があるが、個数は 2 つしかなく、実際には 4 つの方案があるべきですが、注意深く観察すると、opt [5]=x を構成するこの方案の中で opt [j]=x-1 の方案数が 2 つ、opt [j]=x-2 のものが 1 つ、opt [j]=x-3 のものが 1 つ……
明らかにこれは低い定義を満たす設計関数 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 行には、各行に 2 つの非負整数 C、D が含まれ、空白で区切られ、PALMIA 川の最西端からの距離を示します（C は北岸の村、D は南岸の村を表します）。最後のデータセットの下には、2 つの 0 があり、空白で区切られています。
【出力ファイル】ships.out
入力ファイルの各データセットに対して、出力ファイルは連続した行に、上記の条件を満たす航路の最大数を示します。
【入力例】
30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
0 0
【出力例】
4
【問題の分析】
この問題は比較的考えるのが難しいですが、文字通りの意味から問題の本質を見出すのは難しいです。ここで、私はこのような問題を考えるための 2 つの方法をお勧めします。
方法 1：規則を探す方法（前述の第 3 の方法）
規則を探すには、まずいくつかのデータを推測する必要があります。最初はサンプルから始めます；

上の図を注意深く観察すると、赤い航路は合法であり、彼らは何らかの規則を満たしています。
北岸の赤い線の端点： 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 を満たす最長の列を見つけることです。
この場合、典型的な最長非減少部分列問題になります。。。。
方法 2：境界条件法（前述の第 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 の場合を見れば、
任意の 2 つの航路が Ci<Cj かつ Di<Dj を満たす場合、2 つの航路は交差しません。この場合、すべての航路が交差しないようにするには、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.

例題 5 装箱問題 (pack.pas/c/cpp) 來源：NOIP2001（普及組）第四題
【問題の説明】
ある箱の容量は V（正の整数、0＜＝V＜＝20000）であり、同時に n 個の物品（0＜n＜＝30）があります。
n 個の物品の中から、任意の個数を選んで箱に入れ、箱の残りの空間を最小にすることを求めます。
【入力ファイル】
第一行に正の整数 V が箱の容量を示し、第二行に正の整数 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 ナップサックの元の問題に戻ります（忘れた場合は上を見てください）。
このモデルを知らない場合、どのようにこの問題を解決しますか？
これは、第一節で述べた方法 2：三要素法を使用する必要があります。
問題の中で明確に、各物品については取るか取らないかの決定を行う必要があることが示されています。これは、決定が取らない（0 で表される）または取る（1 で表される）ことを示しています。このように考えると、決定が何であるかは明らかです。
したがって、段階は何ですか？
明らかに、物品をナップサックに詰め込むために、物品を一つずつ持ってくる必要があります。したがって、段階は物品の数であることは明らかです。
状態は何ですか？
物を詰めるときに、ある習慣（例えば私のように）を持っている人がいて、物を分類し、同じ種類の物を小さな袋にまとめ、最後に小さな袋を詰め込むことができます。この考え方に従って、物品を小さな袋に分けることができます。つまり、重さが 6 のナップサックには、重さが 1、2、3、4、5 の小さな袋を用意することができます。このようにして、状態を考え出すことができます：
状態 opt [i,j] を設計して、i 番目の物品を詰め込むときに、重さ j のナップサックが最大の価値を得ることができることを示します。
状態遷移方程式：opt [j]:=opt [j-w [1]] {opt [j-w [i]]=true}
境界条件：opt [0,i]=0; (i∈{1..S})
注：
このような二次元の状態表示は、次のセクションで説明されるべきですが、理解を容易にするためにここで説明しました。
上記の方法は、動的計画法の三要素が非常に明確であり、実装も非常に簡単です。しかし、私がナップサックを初めて学んだときは、別の一次元の状態表示法を使用しました。
第一節で述べた思考方法 5（制約を緩和し、制約を追加する）を再考してみましょう：
制約を緩和する方法は、問題の中の価値を取り除くことです。価値を考慮しない場合、最適はナップサック問題の簡略版になります。
簡略版の解決は、私たちに何を示唆するのでしょうか？
再び制約を追加します：ナップサックは満杯にすることができます。
明らかに、N 個の満杯のナップサックの方案の中で、最も価値の高いものを見つけることが解決策です。
満杯でない場合はどうでしょうか？実際、満杯でないナップサックは、必ず一定の重さ（X）に達する必要があります。このような状況を、重さが X の小さな袋を満たすことと見なすことができます。
上記の思考プロセスをまとめると、制約を緩和することで問題の突破口を見つけることができます。
制約を追加することで、問題の解決方法を見つけることができます。
このようにして、問題が解決されました。
状態 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 [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）
以下にいくつかの例題を見てみましょう：

例題 5 箱詰め問題 (pack.pas/c/cpp) 出典：NOIP2001（普及組）第四題
【問題の説明】
ある箱の容量は V（正の整数、0＜＝V＜＝20000）であり、同時に n 個の物品（0＜n＜＝30）があります。
n 個の物品の中から、任意の個数を選んで箱に入れ、箱の残りの空間を最小にすることを求めます。
【入力ファイル】
第一行に正の整数 V が箱の容量を示し、第二行に正の整数 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）。