<s> def knapsack ( p , v , cmax ) : <EOL> """<STR_LIT>""" <EOL> n = len ( p ) <EOL> Opt = [ [ <NUM_LIT:0> ] * ( cmax + <NUM_LIT:1> ) for _ in range ( n + <NUM_LIT:1> ) ] <EOL> Sel = [ [ False ] * ( cmax + <NUM_LIT:1> ) for _ in range ( n + <NUM_LIT:1> ) ] <EOL> for cap in range ( p [ <NUM_LIT:0> ] , cmax + <NUM_LIT:1> ) : <EOL> Opt [ <NUM_LIT:0> ] [ cap ] = v [ <NUM_LIT:0> ] <EOL> Sel [ <NUM_LIT:0> ] [ cap ] = True <EOL> for i in range ( <NUM_LIT:1> , n ) : <EOL> for cap in range ( cmax + <NUM_LIT:1> ) : <EOL> if cap >= p [ i ] and Opt [ i - <NUM_LIT:1> ] [ cap - p [ i ] ] + v [ i ] > Opt [ i - <NUM_LIT:1> ] [ cap ] : <EOL> Opt [ i ] [ cap ] = Opt [ i - <NUM_LIT:1> ] [ cap - p [ i ] ] + v [ i ] <EOL> Sel [ i ] [ cap ] = True <EOL> else : <EOL> Opt [ i ] [ cap ] = Opt [ i - <NUM_LIT:1> ] [ cap ] <EOL> Sel [ i ] [ cap ] = False <EOL> cap = cmax <EOL> sol = [ ] <EOL> for i in range ( n - <NUM_LIT:1> , - <NUM_LIT:1> , - <NUM_LIT:1> ) : <EOL> if Sel [ i ] [ cap ] : <EOL> sol . append ( i ) <EOL> cap -= p [ i ] <EOL> return ( Opt [ n - <NUM_LIT:1> ] [ cmax ] , sol ) <EOL> def knapsack2 ( p , v , cmax ) : <EOL> """<STR_LIT>""" <EOL> n = len ( p ) <EOL> pgv = [ [ <NUM_LIT:0> ] * ( cmax + <NUM_LIT:1> ) for _ in range ( n ) ] <EOL> for c in range ( cmax + <NUM_LIT:1> ) : <EOL> pgv [ <NUM_LIT:0> ] [ c ] = v [ <NUM_LIT:0> ] if c >= p [ <NUM_LIT:0> ] else <NUM_LIT:0> <EOL> pred = { } <EOL> for i in range ( <NUM_LIT:1> , n ) : <EOL> for c in range ( cmax + <NUM_LIT:1> ) : <EOL> pgv [ i ] [ c ] = pgv [ i - <NUM_LIT:1> ] [ c ] <EOL> pred [ ( i , c ) ] = ( i - <NUM_LIT:1> , c ) <EOL> if c >= p [ i ] and pgv [ i - <NUM_LIT:1> ] [ c - p [ i ] ] + v [ i ] > pgv [ i ] [ c ] : <EOL> pgv [ i ] [ c ] = pgv [ i - <NUM_LIT:1> ] [ c - p [ i ] ] + v [ i ] <EOL> pred [ ( i , c ) ] = ( i - <NUM_LIT:1> , c - p [ i ] ) <EOL> cursor = ( n - <NUM_LIT:1> , cmax ) <EOL> chosen = [ ] <EOL> while cursor in pred : <EOL> if pred [ cursor ] [ <NUM_LIT:1> ] < cursor [ <NUM_LIT:1> ] : <EOL> chosen . append ( cursor [ <NUM_LIT:0> ] ) <EOL> cursor = pred [ cursor ] <EOL> if cursor [ <NUM_LIT:1> ] > <NUM_LIT:0> : <EOL> chosen . append ( cursor [ <NUM_LIT:0> ] ) <EOL> return pgv [ n - <NUM_LIT:1> ] [ cmax ] , chosen </s>
