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,w−wi]), 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 ≤ 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.
Programming Praxis 
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)‘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 :)
(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)))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)))))))
(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):
#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)[…] 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 […]