! Copyright (c) 2012 Anonymous
! See http://factorcode.org/license.txt for BSD license.
-USING: accessors arrays fry io kernel locals make math
-math.order math.parser math.ranges sequences sorting ;
+USING: accessors arrays io kernel make math math.order
+math.parser ranges sequences sorting ;
IN: rosetta-code.knapsack
! http://rosettacode.org/wiki/Knapsack_problem/0-1
! Which items does the tourist carry in his knapsack so that
! their total weight does not exceed 400 dag [4 kg], and their
-! total value is maximised?
+! total value is maximized?
TUPLE: item
name weight value ;
T{ item f "socks" 4 50 }
T{ item f "book" 30 10 }
}
-
+
CONSTANT: limit 400
-
+
: make-table ( -- table )
items length 1 + [ limit 1 + 0 <array> ] replicate ;
-
+
:: iterate ( item-no table -- )
item-no table nth :> prev
item-no 1 + table nth :> curr
item-no items nth :> item
- limit [1,b] [| weight |
+ limit [1..b] [| weight |
weight prev nth
weight item weight>> - dup 0 >=
[ prev nth item value>> + max ]
] each ;
: fill-table ( table -- )
- [ items length iota ] dip
+ [ items length <iota> ] dip
'[ _ iterate ] each ;
:: extract-packed-items ( table -- items )
[
limit :> weight!
- items length iota <reversed> [| item-no |
+ items length <iota> <reversed> [| item-no |
item-no table nth :> prev
item-no 1 + table nth :> curr
weight [ curr nth ] [ prev nth ] bi =