Mini-project about 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 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 monetary value, and the whole treasure is represented as a list of triples:

type name = string;;

type weight = int;;

type monetary_value = int;;

type triple = name * weight * monetary_value;;

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 without repetition (see the Solution for Exercise 15 in the lecture notes of Week 08), which is the case here:

let powerset given_vs =
  let rec outer_visit vs =
    match vs with
    | [] ->
       [[]]
    | v :: vs' ->
       let outer_ih = outer_visit vs'
       in let rec inner_visit wss =
            match wss with
            | [] ->
               outer_ih
            | ws :: wss' ->
               let inner_ih = inner_visit wss'
               in (v :: ws) :: inner_ih
          in inner_visit outer_ih
  in outer_visit given_vs;;

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

let assess_subset given_triples =
  let rec loop triples total_weight total_monetary_value =
    match triples with
    | [] ->
       (total_weight, total_monetary_value, given_triples)
    | (name, weight, monetary_value) :: triples' ->
       loop triples' (total_weight + weight) (total_monetary_value + monetary_value)
  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, monetary_value, 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_monetary_value given_candidate_subsets =
  let rec visit candidate_subsets =
    match candidate_subsets with
    | [] ->
       (0, [])
    | candidate_subset :: candidate_subsets' ->
       let (weight, monetary_value, triples) = candidate_subset
       and (current_monetary_value, current_candidate_subsets) = visit candidate_subsets'
       in match compare monetary_value current_monetary_value with
          | Lt ->
             (current_monetary_value, current_candidate_subsets)
          | Eq ->
             (current_monetary_value, candidate_subset :: current_candidate_subsets)
          | Gt ->
             (monetary_value, candidate_subset :: [])
  in visit given_candidate_subsets;;

The solution is therefore:

let minimax_v0 given_weight given_triples =
  maximize_the_monetary_value
    (minimize_the_weight
       given_weight
       (List.map
          assess_subset
          (powerset given_triples)));;

Namely:

1. compute the powerset of the set of given triples;
2. assess the weight and the monetary value 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 monetary value 100,
• two rubies of weight 7 and of monetary value 70, and
• one piece of jade of weight 3 and of monetary value 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
    (List.map
       assess_subset
       (powerset given_triples));;

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

And then you simplify this solution:

let minimize_assessed_powerset_v1 given_weight given_triples =
  ...

let minimax_v1 given_weight given_triples =
  maximize_the_monetary_value
    (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.

Resources

• The OCaml code for the present mini-project (latest version: 04 Apr 2020).

Acknowledgment

To Gregory Teo for suggesting this mini-project.

Version

Added a description of Ali Baba’s solution [06 Apr 2020]

Added the pointer to the Solution for Exercise 15 in the lecture notes of Week 08 [05 Apr 2020]

Fixed a typo in the narrative, thanks to Shardul Saptoka’s eagle eye [05 Apr 2020]

Created [04 Apr 2020]