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.
Pages: 1 2
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)