;; The Knapsack Problem ;; Suppose you've got twelve pounds (def budget 12) ;; And there's a thing that costs a pound, but is worth 20. ;; And another thing that costs 3, but is worth 30 ;; And another thing that costs 3, but is worth 21 ;; And a thing that costs 6 but is worth 40 (def things (map (fn[[c v]] {:cost c :value v}) [[1 20][3 30][3 21][6 40]])) (defn price [things] (reduce + (map :cost things))) (defn evaluate [things] (reduce + (map :value things))) (evaluate things) ;> 111 (price things) ;> 13 ;; So there's 111's worth of things going for 13, but you can't buy everything. ;; What do you buy? (defn value [sortedthings] (evaluate (let [order sortedthings baskets (reductions conj '() order)] (last (takewhile #(<= (price %) budget) baskets))))) ;; Well, if you're a cynic (value (sortby :cost things)) ;> 71 ;; Then you come away with 71's worth ;; And if you're an idealist (value (reverse (sortby :value things))) ;> 91 ;; Then you do way better with 91 ;; A more cunning approach is to take things in order of their price/value ratio (value (reverse (sortby (fn [{:keys[value cost]}] (/ value cost)) things))) ;> 71 ;; Sadly that does worse than the approach that only pays attention to the value. ;; So it seems that out of the three naturalseeming 'greedy algorithms', the best solution is 91 ;; Yet another approach is to exhaustively search the space of possibilities: (defn subsets [things] (if (empty? things) '(()) (let [srt (subsets (rest things))] (concat (map #(cons (first things) %) srt) srt)))) (reverse (sortby second (for [i (subsets things)] [(price i) (evaluate i)]))) ;> ([13 111] [12 91] [10 90] [10 81] [7 71] [9 70] [9 61] [7 60] [6 51] [4 50] [4 41] [6 40] [3 30] [3 21] [1 20] [0 0]) ;; Which tells us that the best combination is unaffordable, so we ;; have to settle for the second best, which is paying 12 to get 91, ;; which the idealist has been trying to tell us all along. ;; But the idealistic approach is unlikely to work in the general case. ;; Consider a thing which is worth a lot, but horribly expensive, and ;; lots of other things which are worth a fair bit and dirt cheap. ;; Personally my money would have been on the 'buy things in order of ;; price/value ratio' approach, but we above that that fails in at ;; least one easy case. ;; So it appears that if we are faced with a problem like this, ( and ;; there are many such problems ), then we are doomed. ;; Exhaustive search is not feasible once you've got more than a very ;; few items, and yet the various greedy algorithms above get the ;; wrong answers. ;; And yet if you write down a knapsack problem like this, you will ;; not find it appallingly difficult to pick the best arrangement. ;; There is a certain tradition at this point of exclaiming 'The HUMAN ;; BRAIN is performing a COMPUTATION INFEASIBLE for a CLASSICAL ;; COMPUTER', and then going on to derive your favourite philosophical ;; position on the nature of consciousness, which will miraculously ;; turn out to be whatever it was you thought before you contemplated ;; the problem in question. ;; But wait ...
Blog Archive

▼
2013
(52)

▼
September
(12)
 Efficiency and Progress III : How Close Can We Get...
 Efficiency and Progress II : Behold, C
 Efficiency and Progress : My God, Clojure is Slow!
 How on earth do you program without *recursion*?
 Algorithms II
 Putting it all together : Using UnionFind in Krus...
 Implementing a Data Structure : UnionFind version II
 Implementing a Data Structure: UnionFind
 Kruskal's Algorithm for Minimal Spanning Trees
 The Knapsack Problem : Another Classic Puzzle from...
 Optimal Scheduling : A Classic Puzzle from Compute...
 SVG Graphics in a Clojure Web Application

▼
September
(12)
Search This Blog
Wednesday, September 18, 2013
The Knapsack Problem : Another Classic Puzzle from Computer Science
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment