0 | Javascript 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
var C_MAX = 30 var max_arr_len = 10 var dp = Array . from ( Array ( max_arr_len ) , ( ) => Array ( C_MAX + 1 ) ) ; var v = Array . from ( Array ( max_arr_len ) , ( ) => Array ( C_MAX + 1 ) ) ; function findMax ( i , r , w , n ) { if ( r < 0 ) return - 1000000000 ; if ( i == n ) return 0 ; if ( v [ i ] [ r ] ) return dp [ i ] [ r ] ; v [ i ] [ r ] = 1 ; 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 ] ; } function preCompute ( w , n ) { for ( var i = C_MAX ; i >= 0 ; i -- ) findMax ( 0 , i , w , n ) ; } function ansQuery ( w ) { return dp [ 0 ] [ w ] ; } var w = [ 3 , 8 , 9 ] ; var n = w . length ; preCompute ( w , n ) ; var queries = [ 11 , 10 , 4 ] ; var q = queries . length ; for ( var i = 0 ; i < q ; i ++ ) document . write ( ansQuery ( queries [ i ] ) + " " ) ;