<s> def read_data ( data ) : <EOL> weights = [ ] <EOL> values = [ ] <EOL> for d in data : <EOL> weights . append ( int ( d . split ( ) [ <NUM_LIT:1> ] ) ) <EOL> values . append ( int ( d . split ( ) [ <NUM_LIT:0> ] ) ) <EOL> return ( weights , values ) <EOL> def knapsack_rep ( weights , values , W ) : <EOL> """<STR_LIT>""" <EOL> k = [ <NUM_LIT:0> ] * ( W + <NUM_LIT:1> ) <EOL> for w in range ( <NUM_LIT:1> , W + <NUM_LIT:1> ) : <EOL> k [ w ] = max ( [ k [ w - i ] + values [ i ] if weights [ i ] <= w else <NUM_LIT:0> for i in range ( len ( weights ) ) ] ) <EOL> return k [ - <NUM_LIT:1> ] <EOL> def knapsack ( weights , values , W ) : <EOL> """<STR_LIT>""" <EOL> optimal_vals = [ <NUM_LIT:0> ] * ( W + <NUM_LIT:1> ) <EOL> for j in range ( <NUM_LIT:0> , len ( weights ) ) : <EOL> for w in range ( W , weights [ j ] - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> if optimal_vals [ w - weights [ j ] ] + values [ j ] > optimal_vals [ w ] : <EOL> optimal_vals [ w ] = optimal_vals [ w - weights [ j ] ] + values [ j ] <EOL> return optimal_vals [ - <NUM_LIT:1> ] <EOL> with open ( "<STR_LIT>" ) as f : <EOL> ( weights , values ) = read_data ( f ) </s>
