let knapsack values weights cap =
  let n = Array.length values in
  let dp = Array.make (cap + 1) 0 in
  for i = 0 to n - 1 do
    let v = values.(i) and w = weights.(i) in
    for c = cap downto w do
      let take = dp.(c - w) + v in
      if take > dp.(c) then dp.(c) <- take
    done
  done;
  dp.(cap)

;;

let v = [|6; 10; 12; 15; 20|] in
let w = [|1; 2; 3; 4; 5|] in
knapsack v w 8
