A tourist wants to make a good trip at the weekend with his friends.

They will go to the mountains to see the wonders of nature.   So he needs some items during the trip.   Food, clothing, etc.   He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening.

He creates a list of what he wants to bring for the trip, but the total weight of all items is too much.   He adds a value to each item.   The value represents how important the thing for the tourist.

The list contains which items are the wanted things for the trip, what is the weight and value of an item, and how many units does he have from each items.



This is the list:


 Table of potential knapsack items


 item 
 weight (dag) (each) 
 value (each) 
 piece(s)


 map 
 9 
 150 
 1


 compass 
 13 
 35 
 1


 water 
 153 
 200 
 2


 sandwich 
 50 
 60 
 2


 glucose 
 15 
 60 
 2


 tin 
 68 
 45 
 3


 banana 
 27 
 60 
 3


 apple 
 39 
 40 
 3


 cheese 
 23 
 30 
 1


 beer 
 52 
 10 
 3


 suntan cream 
 11 
 70 
 1


 camera 
 32 
 30 
 1


 T-shirt 
 24 
 15 
 2


 trousers 
 48 
 10 
 2


 umbrella 
 73 
 40 
 1


 waterproof trousers 
 42 
 70 
 1


 waterproof overclothes 
 43 
 75 
 1


 note-case 
 22 
 80 
 1


 sunglasses 
 7 
 20 
 1


 towel 
 18 
 12 
 2


 socks 
 4 
 50 
 1


 book 
 30 
 10 
 2


 knapsack 
 ≤400 dag 
 ? 
 ?



The tourist can choose to take any combination of items from the list, and some number of each item is available   (see the column   piece(s)   in the list above).

He may not cut the items, so he can only take whole units of any item.



Task

Show which items does the tourist carry in his knapsack so that their total weight does not exceed 4 kg, and their total value is maximized.



Related tasks

   Knapsack problem/Unbounded
   Knapsack problem/Continuous
   Knapsack problem/0-1


 
#lang racket
(require net/url html xml xml/path)
 
(struct item (name mass value count) #:transparent)
 
;this section is to convert the web page on the problem into the data for the problem
;i don't got time to manually type tables, nevermind that this took longer
(define (group-n n l)
  (let group-n ([l l] [acc '()])
    (if (null? l)
        (reverse acc)
        (let-values ([(takes drops) (split-at l n)])
          (group-n drops (cons takes acc))))))
(define (atom? x) (not (or (pair? x) (null? x))))
;modified from little schemer...finds nested list where regular member would've returned non-#f
(define (member* x t)
  (cond [(null? t) #f]
        [(atom? (car t)) (or (and (equal? (car t) x) t)
                             (member* x (cdr t)))]
        [else (or (member* x (car t))
                  (member* x (cdr t)))]))
(define (addr->xexpr f) (compose xml->xexpr f read-html-as-xml get-pure-port string->url))
(define (read-page) ((addr->xexpr cadr) "http://rosettacode.org/wiki/Knapsack_problem/Bounded"))
(define (get-xml-table xe) (member* 'table xe))
(define (xml-table->item-list xe-table)
  ;all html table datas
  (let* ([strs (se-path*/list '(td) xe-table)]
         ;4 columns per row
         [rows (group-n 4 strs)]
         ;the last two rows belong to the knapsack entry which we don't want
         [rows (take rows (- (length rows) 2))])
    (for/list ([r rows])
      (let ([r (map string-trim r)])
        ;convert the weight, value, and pieces columns to numbers and structify it
        (apply item (car r) (map string->number (cdr r)))))))
;top-level function to take a string representing a URL and gives the table I didn't want to type
(define addr->item-list (compose xml-table->item-list get-xml-table read-page))
 
;stores best solution
(struct solution (value choices) #:transparent)
 
;finds best solution in a list of solutions
(define (best sol-list)
  (let best ([l (cdr sol-list)] [bst (car sol-list)])
    (match l
      ['() bst]
      [(cons s l) (if (> (solution-value s) (solution-value bst))
                      (best l s)
                      (best l bst))])))
 
;stores the choices leading to best solution...item name and # of that item taken
(struct choice (name count) #:transparent)
 
;algorithm is derived from Haskell's array-based example
;returns vector of solutions for every natural number capacity up to the input max
(define (solution-vector capacity)
  ;find best value and items that gave it, trying all items
  ;first we set up a vector for the best solution found for every capacity
  ;the best solution found at the beginning has 0 value with no items
  (for/fold ([solutions (make-vector (add1 capacity) (solution 0 '()))])
            ([i (addr->item-list)])
    ;the new solutions aren't accumulated until after processing all the way through a particular
    ;capacity, lest capacity c allow capacity c+1 to reuse an item that had been exhausted, i.e.
    ;we have to move on to the next item before we save ANY solutions found for that item, so they
    ;must be saved "in parallel" by overwriting the entire vector at once
    (for/vector ([target-cap (range 0 (add1 capacity))])
      (match-let ([(item name mass value count) i])
        ;find best solution for item out of every number that can be taken of that item
        ;we'll call an "item and count of item" a choice
        (best (for/list ([n (range 0 (add1 count))])
                ;ensure mass of this choice is not greater than target capacity
                (let ([mass-choice (* n mass)])
                  (if (> mass-choice target-cap)
                      (solution 0 '())
                      ;subtract from target capacity the amount taken up by this choice
                      ;use it to get the best solution for THAT capacity
                      (let ([remaining-cap-solution (vector-ref solutions (- target-cap mass-choice))])
                        ;the new solution found adds the value of this choice to the above value and
                        ;adds the choice itself to the list of choices
                        (solution (+ (* n value) (solution-value remaining-cap-solution))
                                  (cons (choice name n) (solution-choices remaining-cap-solution))))))))))))
 
;top level function to convert solution vector into single best answer
(define (knapsack capacity)
  ;the best solution is not necessarily the one that uses max capacity,
  ;e.g. if max is 5 and you have items of mass 4 and 5, and the 4 is worth more
  (match-let ([(solution value choices) (best (vector->list (solution-vector capacity)))])
    (solution value (filter (compose positive? choice-count) choices))))
 