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 ] ; }