0 | C # 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
using System ; 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 bool [ , ] v = new bool [ max_arr_len , C_MAX + 1 ] ; static int findMax ( int i , int r , int [ ] w , int n ) { if ( r < 0 ) return Int32 . MaxValue ; 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 ( ) { int [ ] w = { 3 , 8 , 9 } ; int n = w . Length ; preCompute ( w , n ) ; int [ ] queries = { 11 , 10 , 4 } ; int q = queries . Length ; for ( int i = 0 ; i < q ; i ++ ) Console . WriteLine ( ansQuery ( queries [ i ] ) ) ; } }