A19 - Knapsack 1¶

• created: 2022-12-30 fri
• ご意見・ご要望はissue・プルリク用のGitHubまで
• 競技プログラミングのためのF#入門
• GitHub上の対応ディレクトリ
• 公式ページ
• 要点: アルゴリズム

入出力¶

1
2
3

let N,W = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Ia = Array.init N (fun _ -> stdin.ReadLine().Split() |> fun x -> int x.[0],int64 x.[1])
solve Ia |> stdout.WriteLine

方針¶

典型的な動的計画法で処理する問題です. 重さを添字wにした配列を作り, 各wごとに価値を格納します. あとはこれをひたすらに計算して書き換えます.

解説¶

配列を書き換え続ける処理は積み上げ系の処理で, 特にfoldで次のように実現できます.

1
2
3

  (Array.create (W+1) 0L, Ia)
  ||> Array.fold (動的計画法の処理)
  |> Array.last

書き換える配列でW+1個作るのは重さwをそのまま解釈できるようにするためです.

次にfold処理の関数を考えます. 動的計画法を考えるとき配列はよくdp(dynamic programming)で表します. ここでもその慣習を踏襲します. このdp[w]は重さwまで荷物を積んだときの価値を表します. ひたすらな書き換えは次のように実現します.

1
2

  ||> Array.fold (fun dp (w,v) ->
    [|0..W|] |> Array.map (fun w0 -> if w0<w then dp.[w0] else max (dp.[w0-w]+v) dp.[w0]))

foldの内部ではIaの各要素(w,v)で更新します. 入力のArray.create (W+1) 0Lと揃えた添字の配列を[|0..W|]とします. この配列の値を重さ(に関する添字)とみなしてw0とします. もしw0がwより小さい場合, dp[w0]に重さwのモノを積めないためdp.[w0]で素通りします. 逆にw<=w0のときは価値が大きい方で置き換えます.