0

I'm having a hard figuring out what to do with this code, that does not compile correctly. I'm trying to write a DP version for the knapsack problem. I want to keep track of previous solution for the sub-problems, by keeping them in memory, using a matrix called mem. I want to initialize all values to be -1 (i.e. not computed yet), except for the edge conditions, i.e for backpack weight of 0 or 0 items. Therefore, I initialize the matrix at -1 and change its values at edge conditions. But I don't know how to pass the mem array after that to the next part of the code. I tried using in or and but it doesn't work.

Help greatly appreciated!

let knapsack_mem = fun (vps : (int * int) array) (c : int) -> 
let mem = Array.make_matrix (c + 1) ((Array.length vps) + 1) (-1) in
mem.(0) <- Array.make (n + 1) 0; for i = 1 to c do mem.(i).(0) <- 0;

(* HERE : in ? and ? *)

let rec aux vps (i,j) = 
    if mem.(i).(j) >= 0 then mem.(i).(j)
    else 
        if lst vps.(i) <= i then max ((aux vps (i - lst vps.(i), j - 1)) + fst vps.(i)) (aux vps (i, j - 1)) 
        else aux vps (i,j - 1)
in aux vps (c, (Array.length vps) + 1) ;;

1 Answer 1

3

The syntax error you are getting is due to the use of the for loop. The syntax is the following:

for i = 1 to n_jobs () do
    do_next_job ()
done

Since this is a side effect operation don't forget to use a ; after the "done" to continue the body of the function. There are other problems with your code but this should fix the syntax error.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.