## 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*], *v _{i}* +

*V*[

*i*−1,

*w*−

*w*]), where

_{i}*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),

*v*is the value of the

_{i}*i*th object, and

*w*is the weight of the

_{i}*i*th object. The program builds up the

*V*matrix, starting from

*V*[0,

*w*] = 0, for all weights 0 ≤

*w*≤

*W*and all sets of objects 1 ≤

*i*≤

*n*, 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

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”

wis the weight of the_{i}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):