DP for Knapsack Problem

kp.ml

type item = {w:int; p:int}

(* 2004, Kellerer et al., Knapsack Problems, p.23 *)
let dp2 items c =
  let n = Array.length items in
  let z = Array.make (c + 1) 0 in
  for j = 0 to n - 1 do
    let {w=wj; p=pj} = items.(j) in
    for d = c downto wj do
      let o = z.(d - wj) + pj in
      if o > z.(d) then
        z.(d) <- o
    done
  done;
  z.(c)