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
#include <bits/stdc++.h> NEW_LINE #define C_MAX  30 NEW_LINE #define max_arr_len  10 NEW_LINE using namespace std ; int dp [ max_arr_len ] [ C_MAX + 1 ] ; bool v [ max_arr_len ] [ C_MAX + 1 ] ; int findMax ( int i , int r , int w [ ] , int n ) { if ( r < 0 ) return INT_MIN ; if ( i == n ) return 0 ; if ( v [ i ] [ r ] ) return dp [ i ] [ r ] ; v [ i ] [ r ] = 1 ; dp [ i ] [ r ] = max ( w [ i ] + findMax ( i + 1 , r - w [ i ] , w , n ) , findMax ( i + 1 , r , w , n ) ) ; return dp [ i ] [ r ] ; } void preCompute ( int w [ ] , int n ) { for ( int i = C_MAX ; i >= 0 ; i -- ) findMax ( 0 , i , w , n ) ; } int ansQuery ( int w ) { return dp [ 0 ] [ w ] ; } int main ( ) { int w [ ] = { 3 , 8 , 9 } ; int n = sizeof ( w ) / sizeof ( int ) ; preCompute ( w , n ) ; int queries [ ] = { 11 , 10 , 4 } ; int q = sizeof ( queries ) / sizeof ( queries [ 0 ] ) ; for ( int i = 0 ; i < q ; i ++ ) cout << ansQuery ( queries [ i ] ) << endl ; return 0 ; }