競技プログラミングのためのF#入門
1 2 3 |
|
典型的な動的計画法で処理する問題です. 重さを添字w
にした配列を作り, 各w
ごとに価値を格納します. あとはこれをひたすらに計算して書き換えます.
配列を書き換え続ける処理は積み上げ系の処理で, 特にfold
で次のように実現できます.
1 2 3 |
|
書き換える配列でW+1
個作るのは重さw
をそのまま解釈できるようにするためです.
次にfold
処理の関数を考えます. 動的計画法を考えるとき配列はよくdp
(dynamic programming)で表します. ここでもその慣習を踏襲します. このdp[w]
は重さw
まで荷物を積んだときの価値を表します. ひたすらな書き換えは次のように実現します.
1 2 |
|
fold
の内部ではIa
の各要素(w,v)
で更新します. 入力のArray.create (W+1) 0L
と揃えた添字の配列を[|0..W|]
とします. この配列の値を重さ(に関する添字)とみなしてw0
とします. もしw0
がw
より小さい場合, dp[w0]
に重さw
のモノを積めないためdp.[w0]
で素通りします. 逆にw<=w0
のときは価値が大きい方で置き換えます.