0 | Java implementation of the approach ; To store states of DP ; To check if a state has been solved ; Function to compute the states ; Base case ; Check if a state has been solved ; Setting a state as solved ; Returning the solved state ; Function to pre - compute the states dp [ 0 ] [ 0 ] , dp [ 0 ] [ 1 ] , . . , dp [ 0 ] [ C_MAX ] ; Function to answer a query in O ( 1 ) ; Driver code ; Performing required pre - computation ; Perform queries
class GFG { static int C_MAX = 30 ; static int max_arr_len = 10 ; static int dp [ ] [ ] = new int [ max_arr_len ] [ C_MAX + 1 ] ; static boolean v [ ] [ ] = new boolean [ max_arr_len ] [ C_MAX + 1 ] ; static int findMax ( int i , int r , int w [ ] , int n ) { if ( r < 0 ) return Integer . MIN_VALUE ; if ( i == n ) return 0 ; if ( v [ i ] [ r ] ) return dp [ i ] [ r ] ; v [ i ] [ r ] = true ; dp [ i ] [ r ] = Math . max ( w [ i ] + findMax ( i + 1 , r - w [ i ] , w , n ) , findMax ( i + 1 , r , w , n ) ) ; return dp [ i ] [ r ] ; } static void preCompute ( int w [ ] , int n ) { for ( int i = C_MAX ; i >= 0 ; i -- ) findMax ( 0 , i , w , n ) ; } static int ansQuery ( int w ) { return dp [ 0 ] [ w ] ; } public static void main ( String [ ] args ) { int w [ ] = new int [ ] { 3 , 8 , 9 } ; int n = w . length ; preCompute ( w , n ) ; int queries [ ] = new int [ ] { 11 , 10 , 4 } ; int q = queries . length ; for ( int i = 0 ; i < q ; i ++ ) System . out . println ( ansQuery ( queries [ i ] ) ) ; } }