(* Knapsack algorithm adapted for our game *)
(* A package is given by an id, a location to which it should be delivered *)
(* and a weight *)
type package_id = int
type location = int * int
type weight = int
type package = Package of package_id * location * weight
(* A robot has a current location, a maximum weight it can carry *)
(* and a list of the packages it is currently carrying *)
type weight = int
type robot = Robot of location * weight * package list
(* At every turn, our robot is given a list of packages *)
(* that it can pick from the current location. Adapt the knapsack *)
(* algorithm to decide which packages to pick and drop at each turn *)
module HT = Hashtbl.Make (struct
type t = (package list * weight)
let equal = (=)
let hash = Hashtbl.hash
end)
let rec decide_action robot packages_at_location =
let Robot (robot_location, max_weight, robot_packages) = robot in
let all_packages = robot_packages @ packages_at_location in
let optimal_package_ids = knapsack all_packages max_weight (fun loc -> estimate_cost robot_location loc) in
let packages_to_drop = List.filter (fun (Package(id,_,_)) -> not (List.mem id optimal_package_ids)) robot_packages in
let packages_to_pick = List.filter (fun (Package(id,_,_)) -> List.mem id optimal_package_ids) packages_at_location in
(packages_to_pick, packages_to_drop)
(* Currently use a simple formula; this can be made much more accurate *)
(* if we exploit the map and the obstacles on it *)
and estimate_cost (x1,y1) (x2,y2) = 1. /. (float (abs (x1-x2) + abs(y1-y2)))
and knapsack packages maxweight estimate_cost =
let ht = HT.create 10000 in
let rec kh packages maxweight =
match packages with
[] -> ([],0,0.0)
| Package(id,loc,weight)::rpackages ->
if HT.mem ht (packages,maxweight)
then HT.find ht (packages,maxweight)
else if maxweight >= weight
then
let (s1,w1,c1) = kh rpackages maxweight in
let (sp,wp,cp) = kh rpackages (maxweight - weight) in
let (s2,w2,c2) = (id :: sp, wp + weight, cp +. (estimate_cost loc)) in
let ans =
if c2 > c1
then (s2,w2,c2)
else if c1 = c2
then if w1 < w2 then (s1,w1,c1) else (s2,w2,c2)
else (s1,w1,c1) in
HT.add ht (packages,maxweight) ans;
ans
else kh rpackages maxweight
in let (package_ids,_,_) = kh packages maxweight
in package_ids
(* Testing *)
let rp = [Package(1,(100,200),100)]
let r = Robot ((1,2),120, rp)
let p = [Package(2,(1,2),120)]
let go () = decide_action r p