Maximum items that can be filled in K Knapsacks of given Capacity | 2 - d array to store states of DP ; 2 - d array to store if a state has been solved ; Vector to store power of variable ' C ' . ; function to compute the states ; Base case ; Checking if a state has been solved ; Setting a state as solved ; Recurrence relation ; Returning the solved state ; Function to initialize global variables and find the initial value of 'R ; Resizing the variables ; Variable to store the initial value of R ; Input array ; number of knapsacks and capacity ; Performing required pre - computation ; finding the required answer
x = 100 NEW_LINE dp = [ [ 0 for i in range ( x ) ] for i in range ( x ) ] NEW_LINE v = [ [ 0 for i in range ( x ) ] for i in range ( x ) ] NEW_LINE exp_c = [ ] NEW_LINE def FindMax ( i , r , w , n , c , k ) : NEW_LINE INDENT if ( i >= n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( v [ i ] [ r ] ) : NEW_LINE INDENT return dp [ i ] [ r ] NEW_LINE DEDENT v [ i ] [ r ] = 1 NEW_LINE dp [ i ] [ r ] = FindMax ( i + 1 , r , w , n , c , k ) NEW_LINE for j in range ( k ) : NEW_LINE INDENT x = ( r // exp_c [ j ] ) % ( c + 1 ) NEW_LINE if ( x - w [ i ] >= 0 ) : NEW_LINE INDENT dp [ i ] [ r ] = max ( dp [ i ] [ r ] , w [ i ] + FindMax ( i + 1 , r - w [ i ] * exp_c [ j ] , w , n , c , k ) ) NEW_LINE DEDENT DEDENT return dp [ i ] [ r ] NEW_LINE DEDENT ' NEW_LINE def PreCompute ( n , c , k ) : NEW_LINE INDENT exp_c . append ( 1 ) NEW_LINE for i in range ( 1 , k ) : NEW_LINE INDENT exp_c [ i ] = ( exp_c [ i - 1 ] * ( c + 1 ) ) NEW_LINE DEDENT R = 0 NEW_LINE for i in range ( k ) : NEW_LINE INDENT R += exp_c [ i ] * c NEW_LINE DEDENT return R NEW_LINE DEDENT w = [ 3 , 8 , 9 ] NEW_LINE k = 1 NEW_LINE c = 11 NEW_LINE n = len ( w ) NEW_LINE r = PreCompute ( n , c , k ) NEW_LINE print ( FindMax ( 0 , r , w , n , c , k ) ) NEW_LINE