Knapsack

August 23, 2011

We look today at a famous problem known as the knapsack problem. The task is to fill a knapsack that can carry objects of a known total weight—the capacity—with objects of a given set—each object having a given weight and value—in such a way as to maximize the sum of the values of the objects. Since any individual object is subject to a binary decision to either take it or leave it, this variant of the knapsack problem is known as the 0/1 knapsack.

The usual algorithm uses dynamic programming on the recurrence expression V[i,w] = max(V[i−1,w], vi + V[i−1,wwi]), where V[i,w] is the maximum value of a knapsack of capacity w using the first i objects (which must be arranged by increasing weight), vi is the value of the ith object, and wi is the weight of the ith object. The program builds up the V matrix, starting from V[0,w] = 0, for all weights 0 ≤ wW and all sets of objects 1 ≤ in, where n is the number of objects available. The answer is V[n,W].

Your task is to write a function that implements the knapsack algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

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 635 other followers

%d bloggers like this: