Paste: Knappsack

USING: accessors arrays fry io kernel locals make math
math.order math.parser math.ranges namespaces sequences sorting ;
IN: rosetta.knappsack

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

: total-weight ( seq -- n )
    [ weight>> ] map sum ;

: total-value ( seq -- n )
    [ value>> ] map sum ;

SYMBOL: best-knappsack
SYMBOL: best-value

: check-knappsack ( sack -- )
    dup total-value dup best-value get >
    [ best-value set best-knappsack set ] [ 2drop ] if ;

: add-to-knappsack ( seq sack -- )
    dup total-weight limit > [
        2drop
    ] [
        over empty?
        [
            check-knappsack drop
        ] [
            [ unclip ] dip [ swap suffix ] [ nip ] 3bi
            [ add-to-knappsack ] 2bi@
        ] if
    ] if ;


: solve-knappsack ( -- items value )
    0 best-value set items { } add-to-knappsack
    best-knappsack get [ name>> ] map best-value get ;

: main ( -- )
    solve-knappsack
    "Total value: " write number>string print
    "Items packed: " print
    natural-sort
    [ "   " write print ] each ;