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.

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