DP - Red Huang

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

動的計画法の 3 つの要素：段階、状態、決定。
彼らの概念は至る所にありますので、私は多くを語りませんが、彼らに対する私の理解を述べます：
動的計画法の解決プロセスを工場の生産ラインと見なすと、段階は特定の商品を生産するさまざまな環節、状態は工件の現在の形態、決定は工件の操作です。明らかに、異なる段階は製品の前の各状態の小結であり、各小結が最終的な全体の生産ラインを構成します。各状態間には関連性があります（次の状態は前の状態が特定の決定を行った後に生成されます）。
以下に例を挙げます：
アイスクリームのバッチを生産するには、多くの環節に分かれます：牛乳を購入し、牛乳を精製処理し、工場で加工し、加工後の商品を包装し、包装後に販売します…… このように、各環節は段階と見なすことができます；製品は異なる時点で異なる状態を持ち、最初はただの白い牛乳ですが、生産に入るとさまざまな形状に加工され、冷凍庫から取り出すとアイスクリームになります（液体から固体に変わる）。各形態は一つの状態であり、液体から固体に変わる過程は凍結という操作を経ており、この操作が決定です。
ある状態がある決定を経て別の状態に変わる過程は状態遷移と呼ばれ、状態遷移を記述する方程式が状態遷移方程式です。
この例を通じて、皆さんは動的計画法について理解が深まったと思います。
次に、動的計画法に対する私の別の理解を述べます：
グラフ理論の知識を用いて動的計画法を理解する：動的計画法の状態を点として抽象化し、直接関連する状態間に有向辺を引き、状態遷移のコストは辺の重みです。このようにして、有向非巡回グラフ 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 題
【問題の説明】
ある国は敵国のミサイル攻撃を防ぐために、ミサイル迎撃システムを開発しました。しかし、このミサイル迎撃システムには欠陥があります：最初の弾丸は任意の高さに到達できますが、その後の各弾丸は前の弾丸の高さを超えることができません。ある日、レーダーが敵国のミサイルの襲来をキャッチしました。このシステムはまだ試用段階にあるため、システムは 1 セットしかなく、すべてのミサイルを迎撃できない可能性があります。
ミサイルが次々と飛来する高さを入力し（レーダーが提供する高さデータは 30000 を超えない正の整数です）、このシステムが最大で何発のミサイルを迎撃できるか、すべてのミサイルを迎撃するために必要なシステムの最小数を計算します。
【入力ファイル】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]) 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._

例題 2 合唱隊形 (chorus.pas/c/cpp) 出典：NOIP2004（向上組）第 1 題
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 が保証されます。
【問題分析】
出列人の数が最小であるということは、残る人数が最大であるということです。
このように分析すると、典型的な最長減少部分列問題になります。各人が中央に立つときに得られる最適解を求めることが明らかです。
複雑度：
最長減少部分列の計算の複雑度は 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 回購入できますが、購入時の株価は前回の購入時の株価よりも低くなければなりません。プログラムを作成して、最大で何回株を購入できるかを求めてください。
以下の表は、ある数日の株価です：
日数 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）を示します。
再帰式：
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 の方法）
規則を探すには、いくつかのデータセットを推進する必要があります。最初にサンプルから始めるのが良いでしょう；

上の図を注意深く観察してください：赤い航路は合法であり、彼らは何らかの規則を満たしています。
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 を満たす最長の列を見つけることができます。
この場合、典型的な最長非減少部分列問題になります。。。。
方法 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（普及組）第 4 題
【問題の説明】
ある箱の容量は 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 ナップサックの簡略版です。箱をナップサックと見なし、容量を載荷重量、体積を重量、残りの空間を最小化することは、ナップサックをできるだけ満たすことになります。
状態 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（向上組）第 4 題
【問題の説明】
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 は、積木を使って美しい城を作るのが大好きです。城は立方体の積木で作られ、城の各層は 1 つの積木です。小 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 を使用して取る）。このように考えると、決定がわかり、問題の突破口が見つかります。
したがって、段階は何ですか？
明らかに、物を持って行くときは、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})
注：
このような二次元の状態表示は次のセクションで説明しますが、理解を助けるためにここで説明しました。
上記の方法は、動的計画法の三要素が明らかで、実装も非常に簡単です。しかし、私がナップサックを初めて学んだときは、別の一次元の状態表示法を使用しました。
第一節で述べた考え方 5（制約を緩和し、制約を追加する）を使用して、この問題を再考します：
制約を緩和するにはどうすればよいですか？
問題文の価値を取り除き、価値を考慮しない場合、最適はナップサック問題の簡略版になります。簡略版の解決は私たちに何を示唆するのでしょうか？
再度制約を追加します：ナップサックを満たすことができる。
明らかに、ナップサックを満たす方案の中で、最大の価値を持つものを見つけることが問題の解決策です。では、満たさない場合はどうでしょうか？実際、満たさないナップサックは、必ず一定の重さ（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 [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（普及組）第 4 題
【問題の説明】
ある箱の容量は 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 ナップサックの簡略版です。箱をナップサックと見なし、容量を載荷重量、体積を重量、残りの空間を最小化することは、ナップサックをできるだけ満たすことになります。
状態 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）。