Knapsack
August 23, 2011
Our function takes a vector of objects, where each object is itself a three-slot vector of name, value and weight, and a capacity, and returns both the value achieved and a list of the object names included in the solution:
(define (knapsack objs cap) ; objs is vector of #(name value weight)
(let* ((len (vector-length objs))
(vs (make-matrix (+ len 1) (+ cap 1) 0))
(ns (make-matrix (+ len 1) (+ cap 1) #f)))
(define (n i) (vector-ref (vector-ref objs (- i 1)) 0))
(define (v i) (vector-ref (vector-ref objs (- i 1)) 1))
(define (w i) (vector-ref (vector-ref objs (- i 1)) 2))
(define (mv r c) (matrix-ref vs r c))
(define (mn r c) (matrix-ref ns r c))
(define (mv! r c x) (matrix-set! vs r c x))
(define (mn! r c x) (matrix-set! ns r c x))
; (do ((c 0 (+ c 1))) ((< len c)) (mv! 0 c 0))
(do ((r 1 (+ r 1))) ((< len r))
(do ((c 0 (+ c 1))) ((< cap c))
(cond ((and (<= (w r) c)
(< (mv (- r 1) c)
(+ (v r) (mv (- r 1) (- c (w r))))))
(mv! r c (+ (v r) (mv (- r 1) (- c (w r)))))
(mn! r c #t))
(else (mv! r c (mv (- r 1) c)) (mn! r c #f)))))
(let loop ((r len) (k cap) (ks '()))
(cond ((zero? r) (values (mv len cap) ks))
((mn r k) (loop (- r 1) (- k (w r)) (cons (n r) ks)))
(else (loop (- r 1) k ks))))))
The function begins by computing the number of objects and creating matrices to store the accumulating values, vs
, and the object names included in the accumulating solution, ns
. Then follow several define
s that help with readability. The commented-out line is included to remind the reader what is happening, but it’s not necessary because the value was included in the initialization. The main body of the function is the nested do
loops on the rows r
and columns c
of the matrices; the cond
implements the max of the recurrence expression. The final let loop
accumulates the object names included in the solution. Here are some examples:
> (knapsack #(#(a 10 5) #(b 40 4) #(c 30 6) #(d 50 3)) 10)
90
(b d)
> (knapsack #(#(a 4 12) #(b 2 1) #(c 10 4) #(d 2 2) #(e 1 1)) 15)
15
(b c d e)
We used the matrix functions from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/sZVbIi97.
Python 3.
‘items’ is a list of objects that have ‘name’, ‘value’, and ‘weight’ attributes. For testing, I used the Item() namedtuple above.
Example,
What is W? Why do you start with V[0,w] and not, say, V[i,w], which would make more sense since you wrote “1 ≤ i ≤ n”
wi is the weight of the ith object. V[0,w] is the base of the recurrence expression, and hence must be calculated first.
I was asking about the capital W, which is defined nowhere. I guess it’s the maximum weight one can bear… Also, it should be “all objects 1≤i≤n” rather than “all sets of objects 1≤i≤n” shouldn’t it?
Anyway, I have a solution, but it’s too ugly for posting :)
W is the capacity of the knapsack.
(define values
#(2 4 5 1 3))
(define weights
#(3 2 2 3 4))
(define (knapsack w i)
(cond
((or (= w 0)
(= i 0)) 0)
((> (vector-ref weights (sub1 i)) w)
(knapsack w (sub1 i)))
(else
(max (knapsack w (sub1 i))
(+ (vector-ref values (sub1 i))
(knapsack (- w (vector-ref weights (sub1 i)))
(- i 1)))))))
Sorry for poor formating
Why must the objects be sorted by weight? Your examples don’t obey this constraint, and your program doesn’t sort the objects. Anyway, I didn’t bother with the matrix and just used recursion and memoization (like in the Word Breaks problem):
[…] reduces the multiplication of the factors to addition of their logarithms, which means that the knapsack algorithm can be used to find the greatest sum less than the logarithm of the square […]