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 defines 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.

About these ads

Pages: 1 2

10 Responses to “Knapsack”

  1. Mike said

    Python 3.

    from collections import namedtuple
    from operator import attrgetter
    
    Item = namedtuple('Item','name value weight')
    Node = namedtuple('Node','value items')
    
    def knapsack(items, capacity):
        m = [Node(0,[])] * (capacity + 1)
    
        for item in sorted(items, key=operator.attrgetter('weight')):
            for w in range(capacity, item.weight-1, -1):
    
                prev = m[w - item.weight]
    
                if prev.value + item.value > m[w].value:
                    m[w] = Node(prev.value + item.value, prev.items + [item.name])
    
        return m[-1].value, sorted(m[-1].items)
    
  2. Mike said

    ‘items’ is a list of objects that have ‘name’, ‘value’, and ‘weight’ attributes. For testing, I used the Item() namedtuple above.

    Example,

    from random import randint
    
    items = [Item(c, randint(1,50), randint(1,15)) for c in 'abcdefgh']
    #items = [
    # Item(name='a', value=21, weight=10),
    # Item(name='b', value=31, weight=10),
    # Item(name='c', value=13, weight=1),
    # Item(name='d', value=9, weight=6),
    # Item(name='e', value=2, weight=15),
    # Item(name='f', value=10, weight=2),
    # Item(name='g', value=24, weight=4),
    # Item(name='h', value=15, weight=4)]
    
    knapsack(items, 20)  
    # (83, ['b', 'c', 'g', 'h'])
    
  3. Axio said

    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”

  4. programmingpraxis said

    wi is the weight of the ith object. V[0,w] is the base of the recurrence expression, and hence must be calculated first.

  5. Axio said

    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 :)

  6. Axio said
    (defstruct item value weight name)
    
    (defparameter *my-items*
          (vector
           (make-item :value 21 :weight 10 :name 'a)
           (make-item :value 31 :weight 10 :name 'b)
           (make-item :value 13 :weight 1 :name 'c)
           (make-item :value 9 :weight 6 :name 'd)
           (make-item :value 2 :weight 15 :name 'e)
           (make-item :value 10 :weight 2 :name 'f)
           (make-item :value 24 :weight 4 :name 'g)
           (make-item :value 15 :weight 4 :name 'h)))
    
    (defmacro val (i) `(item-value (aref items (1- ,i))))
    (defmacro wei (i) `(item-weight (aref items (1- ,i))))
    (defmacro nam (i) `(item-name (aref items (1- ,i))))
    
    (defun ks (items max-weight)
      (let ((items (sort items #'< :key #'item-value))
            (mat (make-array (list (1+ (array-dimension items 0))
                                   (1+ max-weight))
                             :initial-element '(0))))
        (loop for i from 1 upto (array-dimension items 0)
           do (loop for w from max-weight downto 0
                 do (let ((pred (aref mat (1- i) w)))
                      (setf (aref mat i w)
                            (if (or (< (- w (wei i)) 0) ;; to heavy
                                    (> (car pred) ;; no gain
                                       (+ (val i)
                                          (car (aref mat (1- i) (- w (wei i)))))))
                                pred
                                (cons (+ (val i)
                                         (car (aref mat (1- i) (- w (wei i)))))
                                      (cons (nam i)
                                            (cdr (aref mat (1- i) (- w (wei i)))))))))))
        (format t "~a~%" mat)
        (aref mat (array-dimension items 0) max-weight)))
    
  7. programmingpraxis said

    W is the capacity of the knapsack.

  8. ohwow said


    (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)))))))

  9. ohwow said
    (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

  10. 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):

    #lang racket
    (require rackunit)
    
    (struct obj (value weight))
    
    (define (max-value objs max-weight)
      (if (null? objs)
          0
          (match-let (((list-rest (struct obj (value weight)) rest) objs))
            (if (> weight max-weight)
                (max-value rest max-weight)
                (max (+ value (max-value rest (- max-weight weight)))
                     (max-value rest max-weight))))))
    
    (define (memoize f)
      (let ((dict (make-hash)))
        (λ args (dict-ref! dict args (λ () (apply f args))))))
    
    (set! max-value (memoize max-value))
    
    (check-equal? (max-value (list (obj 2 2)) 2) 2)
    (check-equal? (max-value (list (obj 2 2)) 1) 0)
    (check-equal? (max-value (list (obj 2 2) (obj 1 1) (obj 3 3)) 6) 6)
    (check-equal? (max-value (list (obj 2 2) (obj 1 1) (obj 3 3)) 5) 5)
    (check-equal? (max-value (list (obj 10 5) (obj 40 4) (obj 30 6) (obj 50 3)) 10) 90)
    (check-equal? (max-value (list (obj 4 12) (obj 2 1) (obj 10 4) (obj 2 2) (obj 1 1)) 15) 15)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: