78 lines
2.2 KiB
Factor
78 lines
2.2 KiB
Factor
USING: accessors arrays fry io kernel locals make math
|
|
math.order math.parser math.ranges sequences sorting ;
|
|
IN: rosetta.knappsack.0-1
|
|
|
|
TUPLE: item
|
|
name weight value ;
|
|
|
|
CONSTANT: items {
|
|
T{ item f "map" 9 150 }
|
|
T{ item f "compass" 13 35 }
|
|
T{ item f "water" 153 200 }
|
|
T{ item f "sandwich" 50 160 }
|
|
T{ item f "glucose" 15 60 }
|
|
T{ item f "tin" 68 45 }
|
|
T{ item f "banana" 27 60 }
|
|
T{ item f "apple" 39 40 }
|
|
T{ item f "cheese" 23 30 }
|
|
T{ item f "beer" 52 10 }
|
|
T{ item f "suntan cream" 11 70 }
|
|
T{ item f "camera" 32 30 }
|
|
T{ item f "t-shirt" 24 15 }
|
|
T{ item f "trousers" 48 10 }
|
|
T{ item f "umbrella" 73 40 }
|
|
T{ item f "waterproof trousers" 42 70 }
|
|
T{ item f "waterproof overclothes" 43 75 }
|
|
T{ item f "note-case" 22 80 }
|
|
T{ item f "sunglasses" 7 20 }
|
|
T{ item f "towel" 18 12 }
|
|
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 |
|
|
weight prev nth
|
|
weight item weight>> - dup 0 >=
|
|
[ prev nth item value>> + max ]
|
|
[ drop ] if
|
|
weight curr set-nth
|
|
] each ;
|
|
|
|
: fill-table ( table -- )
|
|
[ items length iota ] dip
|
|
'[ _ iterate ] each ;
|
|
|
|
:: extract-packed-items ( table -- items )
|
|
[
|
|
limit :> weight!
|
|
items length iota <reversed> [| item-no |
|
|
item-no table nth :> prev
|
|
item-no 1 + table nth :> curr
|
|
weight [ curr nth ] [ prev nth ] bi =
|
|
[
|
|
item-no items nth
|
|
[ name>> , ] [ weight>> weight swap - weight! ] bi
|
|
] unless
|
|
] each
|
|
] { } make ;
|
|
|
|
: solve-knappsack ( -- items value )
|
|
make-table [ fill-table ]
|
|
[ extract-packed-items ] [ last last ] tri ;
|
|
|
|
: main ( -- )
|
|
solve-knappsack
|
|
"Total value: " write number>string print
|
|
"Items packed: " print
|
|
natural-sort
|
|
[ " " write print ] each ;
|