Mini-project: A simple variant of the knapsack problem

Ali Baba is in a hurry. He just jumped down from his faithful Irish camel, O’Caml, opened the door of the thieves’ den, and now he wishes to fill his Yale-NUS knapsack with a share of the treasure and then go back to his family with the loot before the thieves come back. Since his knapsack can only hold that much weight, he is looking for the most expensive items he can find that fit into his bag. Conveniently (as luck has it, the thieves also use Irish camels), each item in the den is tagged with its weight and its worth, and the whole treasure is represented as a list of triples:

type name = string;;

type weight = int;;

type worth = int;;

type triple = name * weight * worth;;

type treasure = triple list;;

Ali Baba promptly realizes that he needs to compute the most pricey subset of the treasure that is light enough to fit into his bag.

Fortunately, he knows how to compute the powerset of a set when this set is represented as a list of elements (see the section about Computing the powerset of a set, revisited in the lecture notes of Week 09), which is the case here:

let exp2 n =
  let () = assert (n >= 0) in
  let rec visit i a =
    if i = 0
    then a
    else visit (pred i) (2 * a)
  in visit n 1;;

let make_a_subset xs n =
  let rec visit xs i =
    match xs with
    | [] ->
       []
    | x :: xs' ->
       if i mod 2 = 0
       then visit xs' (i / 2)
       else x :: (visit xs' (i / 2))
  in visit xs n;;

let powerset xs =
  List.init (exp2 (List.length xs)) (make_a_subset xs);;

Given an element of the powerset of the treasure, i.e., a list of triples, he can assess their total weight and total worth as follows:

let assess_subset given_triples =
  let rec loop triples total_weight total_worth =
    match triples with
    | [] ->
       (total_weight, total_worth, given_triples)
    | (name, weight, worth) :: triples' ->
       loop triples' (total_weight + weight) (total_worth + worth)
  in loop given_triples 0 0;;

Thus equipped, he can assess the powerset of the treasure:

let assess_powerset given_tripless =
  List.map assess_subset given_tripless;;

Now all that he needs to do is to filter out the subsets that are too heavy:

let filter_out p given_vs =
  let rec visit vs =
    match vs with
    | [] ->
       []
    | v :: vs' ->
       if p v
       then visit vs'
       else v :: visit vs'
  in visit given_vs;;

let minimize_the_weight given_weight assessed_subsets =
  filter_out
    (fun (weight, worth, triples) ->
      weight > given_weight)
    assessed_subsets;;

And given candidate subsets that are light enough, all he needs to do is to select the most pricey ones:

type comparison = Lt | Eq | Gt;;

let compare v1 v2 =
  if v1 < v2 then Lt else if v1 = v2 then Eq else Gt;;

let maximize_the_worth given_candidate_subsets =
  let rec visit candidate_subsets =
    match candidate_subsets with
    | [] ->
       (0, [])
    | candidate_subset :: candidate_subsets' ->
       let (weight, worth, triples) = candidate_subset
       and (current_worth, current_candidate_subsets) = visit candidate_subsets'
       in match compare worth current_worth with
          | Lt ->
             (current_worth, current_candidate_subsets)
          | Eq ->
             (current_worth, candidate_subset :: current_candidate_subsets)
          | Gt ->
             (worth, candidate_subset :: [])
  in visit given_candidate_subsets;;

The solution is therefore:

let minimax_v0 given_weight given_triples =
  maximize_the_worth
    (minimize_the_weight
       given_weight
       (assess_powerset
          (powerset given_triples)));;

Namely:

1. compute the powerset of the set of given triples;
2. assess the weight and the worth of each subset of this powerset;
3. filter out all the subsets that are too heavy;
4. select among the remaining subsets the ones that are the most pricey.

And indeed, for example, if the treasure consists of

• one diamond of weight 10 and of worth 100,
• two rubies of weight 7 and of worth 70, and
• one piece of jade of weight 3 and of worth 30,

Ali Baba’s program yields the right answer depending on the capacity of his knapsack:

# minimax_v0 10 [("diamond", 10, 100); ("ruby1", 7, 70); ("ruby2", 7, 70); ("jade", 3, 30)];;
- : int * (int * int * (string * int * int) list) list = (100, [(10, 100, [("diamond", 10, 100)]);
                                                                (10, 100, [("ruby1", 7, 70); ("jade", 3, 30)]);
                                                                (10, 100, [("ruby2", 7, 70); ("jade", 3, 30)])])
# minimax_v0 8 [("diamond", 10, 100); ("ruby1", 7, 70); ("ruby2", 7, 70); ("jade", 3, 30)];;
- : int * (int * int * (string * int * int) list) list = (70, [(7, 70, [("ruby1", 7, 70)]);
                                                               (7, 70, [("ruby2", 7, 70)])])
# minimax_v0 5 [("diamond", 10, 100); ("ruby1", 7, 70); ("ruby2", 7, 70); ("jade", 3, 30)];;
- : int * (int * int * (string * int * int) list) list = (30, [(3, 30, [("jade", 3, 30)])])
# minimax_v0 2 [("diamond", 10, 100); ("ruby1", 7, 70); ("ruby2", 7, 70); ("jade", 3, 30)];;
- : int * (int * int * (string * int * int) list) list = (0, [(0, 0, [])])
#

Analysis:

• if the knapsack can hold a weight of 10, then Ali Baba has 3 choices: the diamond or either ruby and the piece of jade;
• if the knapsack can hold a weight of 8, then Ali Baba has 2 choices: either the first or the second ruby;
• if the knapsack can hold a weight of 5, then Ali Baba has 1 choice: the piece of jade; and
• if the knapsack can hold a weight of 2, then Ali Baba has also 1 choice, which is to leave with his bag empty.

This solution is however inefficient because it requires him to compute the powerset of the treasure, which is an exponential computation, and the thieves are galloping back full tilt on their Irish camels (but no pressure).

This is where, as a consultant, you jump in. With Emacs speed, i.e., very, very fast, you refactor Ali Baba’s solution:

let minimize_assessed_powerset_v0 given_weight given_triples =
  minimize_the_weight
    given_weight
    (assess_powerset
       (powerset given_triples));;

let minimax_v0_alt given_weight given_triples =
  maximize_the_worth
    (minimize_assessed_powerset_v0 given_weight given_triples);;

And then you simplify this solution:

let minimize_assessed_powerset_v1 given_weight given_triples =
  ... (* to be implemented *)

let minimax_v1 given_weight given_triples =
  maximize_the_worth
    (minimize_assessed_powerset_v1 given_weight given_triples);;

Your insight is that there is no need to list all the subsets of the given set and then assess them and then filter out the subsets that are too heavy: one only needs to list the subsets that are light enough.

Not just that but all the functions above can be made tail-recursive with an accumulator, so that the Irish camel’s hump does not overflow during evaluation (looping regurgitation?). The resource file already contains all these tail-recursive implementations as well as a copious collection of unit tests, so you are also expected to implement a tail-recursive version of minimize_assessed_powerset_v1:

let tr_minimize_assessed_powerset_v1 given_weight given_triples =
  ... (* to be implemented *)

let tr_minimax_v1 given_weight given_triples =
  tr_maximize_the_worth
    (tr_minimize_assessed_powerset_v1 given_weight given_triples);;

Resources

• The OCaml code for the present mini-project (latest version: 15 Oct 2022).

Acknowledgment

To Gregory Teo for suggesting this mini-project in the spring of 2020.

Version

Created [15 Oct 2022]