Solution using 0 1 knapsack
int [ ] [ ] k = new int [ 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 ] = Math . 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 ] ; }