動的計画法（プログラム例）

      1. 資源配分問題（0-1 ナップザック問題）ー投資先（品物）毎のデータを出力したい場合ー
      2. 資源配分問題（0-1 ナップザック問題）ー投資先（品物）毎のデータを必要としない場合ー
      3. 0-1 ナップザック問題 ー品物毎のデータを出力したい場合ー
      4. 0-1 ナップザック問題 ー品物毎のデータを必要としない場合ー
      5. グラフにおける最短距離問題 ー経路を出力したい場合ー
      6. グラフにおける最短距離問題 ー経路を出力する必要が無い場合ー

　　動的計画法は，システムを複数の状態で表現し，初期状態から目標状態まで遷移させていき，その過程を通して最大値（最小値）を求めようとするものです．上図に示すように，ステップ (k+1) の状態 j におけるコストは，ステップ k の各状態におけるコスト（ステップ k に至るまでのコストの和）に，その状態からステップ (k+1) の状態 j に遷移（全ての状態から遷移できるとは限らない）するためにかかるコストを加えたものの内最小（最大）のものになります．これを，初期状態から目標状態まで繰り返せば解が得られます．ステップ (k+1) におけるコストは，ステップ k のコストだけで決まるため，最小（最大）を求めることだけが目的であれば，前後する 2 つのステップにおける状態だけを記憶しておけば良いことになります．

１．資源配分問題（0-1 ナップザック問題）ー投資先（品物）毎のデータを出力したい場合ー

　　資源配分問題は，n_toshi 種類の投資先に，max_t 単位の資金を配分し（資金は単位でしか配分できない），利益を最大にしようとするものです．このプログラム例では，以下に示すように（コメント部分は除く），n_toshi，及び，max_t の値と，各投資先に 1 から max_t 単位の資金を投資した場合に得られる利益を入力すれば結果を得ることができます． 
n_toshi max_t
p1,1 p1,2 ･･･ p1,max_t   // 1 番目の投資先によって得られる利益
p2,1 p2,2 ･･･ p2,max_t   // 2 番目の投資先によって得られる利益
　　・・・
pn_toshi,1 pn_toshi,2 ･･･ pn_toshi,max_t
　　資源配分問題においては，投資資金が状態になります（ 0 の場合も含めるため，状態数は (max_t+1) 個）．プログラムの table[i][j] には，ステップ (i+1) において j 単位の資金を投資した場合の利益が記憶されます．また，各投資先に対する投資額も知りたい場合には，table[i-1][k] から table[i][j] に遷移するする際，どの状態（ k の値）から遷移する際に table[i][j] が最大になるかを記憶しておく必要があります．これを行うのが，変数 prev です．

　　0-1 ナップザック問題も，データを適切に記述すれば，同じプログラムで解くことが可能です．0-1 ナップザック問題では，n_toshi 種類の品物からいくつか選んでナップザックに入れるものとナップザックに入れるとします．各品物を入れることによって，その品物固有の効用が得られます．ただし，ナップザックに入れることができる最大重量は max_t であり，この条件のもとで効用が最大になるように入れる品物を選ぶことになります．例えば，品物の数が 4，最大重量が 6 の場合，以下に示すような入力データになります（コメント部分は除く）．なお，0-1 ナップザック問題においては，ナップザック内に入っている品物の重量が状態になります． 
4 6
2 0 0 0 0 0   // 1 番目の品物の重さは 1 で，その効用は 2
0 0 5 0 0 0   // 2 番目の品物の重さは 3 で，その効用は 5
0 0 4 0 0 0   // 3 番目の品物の重さは 3 で，その効用は 4
0 0 3 0 0 0   // 4 番目の品物の重さは 3 で，その効用は 3

結果
データ

２．資源配分問題（0-1 ナップザック問題）ー投資先（品物）毎のデータを必要としない場合ー

　　資源配分問題（0-1 ナップザック問題）において，最大利益（最大効用）だけを知りたい場合には，table[i-1][k] から table[i][j] に遷移するする際，どの状態（ k の値）から遷移する際に table[i][j] が最大になるかを記憶する必要がありませんので，変数 prev は不必要です．また，前後 2 つのステップにおける状態だけを記憶しておけば良いので，変数 rieki の配列サイズを小さくすることができます．


結果
データ

３．0-1 ナップザック問題 ー品物毎のデータを出力したい場合ー

　　0-1 ナップザック問題を資源配分問題に対するプログラムで解く場合，上の例で示したように，入力データとして余分な 0 を記述する必要があります．しかし，一般的には，以下に示すように，品物の数 N，ナップザックに入れることができる最大重量 W，及び，各品物の重さ wi と その効用 vi を入力するだけで十分です（コメント部分は除く）． 
N W
w1 v1   // 1 番目の品物の重さとそれを入れた場合の効用
w2 v2   // 2 番目の品物の重さとそれを入れた場合の効用
　　・・・
wN vN

結果
データ

４．0-1 ナップザック問題 ー品物毎のデータを必要としない場合ー

　　資源配分問題と同様，最大効用だけを知りたい場合には，プログラムはより簡単になります．


結果
データ

５．グラフにおける最短距離問題 ー経路を出力したい場合ー

　　ここでは，グラフにおける最短経路問題を扱います．初期ノードから目標ノードに至る最短経路を求める問題です．最短経路問題において，状態はノードとなりますので，状態の数はノードの数となります．例えば，上図に示すグラフにおいては，状態の数は 7 となり，ノード 0 から ノード 6 に至る最短経路を求めることになります．また，上図における枝上に記述された数字はノード間の距離を示しており，最短経路は赤で示した経路になります．このプログラムに対しては，以下に示すようなデータを入力します（コメント部分は除く）． 
N M   // ノードの数，接続データの数（接続データが無いノード間は移動できない）
ni nj rij   // ノード ni と ノード nj 間の距離は rij
　　・・・
例えば，上に示した図に対する入力データは以下のようになります． 
7 10
0 1 2
0 2 5
1 2 4
1 3 6
1 4 10
2 3 2
3 5 1
4 5 3
4 6 5
5 6 9

結果
データ

６．グラフにおける最短距離問題 ー経路を出力する必要が無い場合ー

　　上のプログラムでは最短経路も出力されますが，このプログラムでは，最短経路長だけが出力されます．


結果
データ