Maximum items that can be filled in K Knapsacks of given Capacity |  ; 2 - d array to store if a state has been solved ; 2 - d array to store states of DP ; 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 ; Driver code ; Input array ; number of knapsacks and capacity ; Performing required pre - computation ; finding the required answer
using System ; using System . Collections . Generic ; class GFG { static List < List < bool > > v = new List < List < bool > > ( ) ; static List < List < int > > dp = new List < List < int > > ( ) ; static List < int > exp_c = new List < int > ( ) ; static int FindMax ( int i , int r , int [ ] w , int n , int c , int k ) { if ( i >= n ) { return 0 ; } if ( v [ i ] [ r ] ) { return dp [ i ] [ r ] ; } v [ i ] [ r ] = true ; dp [ i ] [ r ] = FindMax ( i + 1 , r , w , n , c , k ) ; for ( int j = 0 ; j < k ; j ++ ) { int x = ( r / exp_c [ j ] ) % ( c + 1 ) ; if ( x - w [ i ] >= 0 ) { dp [ i ] [ r ] = Math . Max ( dp [ i ] [ r ] , w [ i ] + FindMax ( i + 1 , r - w [ i ] * exp_c [ j ] , w , n , c , k ) ) ; } } return dp [ i ] [ r ] ; } static int PreCompute ( int n , int c , int k ) { for ( int i = 0 ; i < k ; i ++ ) { exp_c . Add ( 0 ) ; } exp_c [ 0 ] = 1 ; for ( int i = 1 ; i < k ; i ++ ) { exp_c [ i ] = ( exp_c [ i - 1 ] * ( c + 1 ) ) ; } for ( int i = 0 ; i < n ; i ++ ) { dp . Add ( new List < int > ( ) ) ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < ( exp_c [ k - 1 ] * ( c + 1 ) ) ; j ++ ) { dp [ i ] . Add ( 0 ) ; } } for ( int i = 0 ; i < n ; i ++ ) { v . Add ( new List < bool > ( ) ) ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < ( exp_c [ k - 1 ] * ( c + 1 ) ) ; j ++ ) { v [ i ] . Add ( false ) ; } } int R = 0 ; for ( int i = 0 ; i < k ; i ++ ) { R += exp_c [ i ] * c ; } return R ; } static public void Main ( ) { int [ ] w = { 3 , 8 , 9 } ; int k = 1 , c = 11 ; int n = w . Length ; int r = PreCompute ( n , c , k ) ; Console . WriteLine ( FindMax ( 0 , r , w , n , c , k ) ) ; } }