Solution using 0 1 knapsack
int k [ N + 1 ] [ A + 1 ] ; for ( int i = 0 ; i <= N ; i ++ ) { for ( int w = 0 ; w <= A ; w ++ ) { if ( i == 0 w == 0 ) k [ i ] [ w ] = 0 ; else if ( wt [ i - 1 ] <= w ) k [ i ] [ w ] = max ( val [ i - 1 ] + k [ i - 1 ] [ w - wt [ i - 1 ] ] , k [ i - 1 ] [ w ] ) ; else k [ i ] [ w ] = k [ i - 1 ] [ w ] ; } } return k [ N ] [ A ] ; }