(* Write the recursive solution; memoize it *)
type id = string
type cost = int
type weight = int
type items = (id * cost * weight) list
(* Naive recursive *)
let rec knapsack_rec items maxweight =
match items with
[] -> ([],0,0)
| (id,cost,weight)::items ->
if maxweight >= weight (* we have a choice to pick or not the current item *)
then (* compute solutions in both cases *)
let (s1,w1,c1) = knapsack_rec items maxweight in (* choice where we didn't pick it *)
let (sp,wp,cp) = knapsack_rec items (maxweight - weight) in (* choice where we do pick it *)
let (s2,w2,c2) = (id :: sp, wp + weight, cp + cost) in
if c2 > c1 then (s2,w2,c2) else (s1,w1,c1)
else (* cannot pick the current item *)
knapsack_rec items maxweight
let items1 = [("I1", 60, 10); ("I2", 100, 20); ("I3", 120, 30)]
let rec make_items n = if n = 0 then []
else ("X",20,20) :: (make_items (n-1))
let items2 = items1 @ (make_items 1000)
(* Memoized *)
module HT = Hashtbl.Make (struct
type t = (items * weight)
let equal = (=)
let hash = Hashtbl.hash
end)
let knapsack_mem items maxweight =
let ht = HT.create 10000 in
let rec kh items maxweight =
if HT.mem ht (items,maxweight)
then HT.find ht (items,maxweight)
else match items with
[] -> ([],0,0)
| (id,cost,weight)::ritems ->
if maxweight >= weight (* we have a choice to pick or not the current item *)
then (* compute solutions in both cases *)
let (s1,w1,c1) = kh ritems maxweight in (* choice where we didn't pick it *)
let (sp,wp,cp) = kh ritems (maxweight - weight) in (* choice where we do pick it *)
let (s2,w2,c2) = (id :: sp, wp + weight, cp + cost) in
let ans = if c2 > c1 then (s2,w2,c2) else (s1,w1,c1) in
HT.add ht (items,maxweight) ans;
ans
else (* cannot pick the current item *)
kh ritems maxweight
in kh items maxweight