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 ; Input array ; number of knapsacks and capacity ; Performing required pre - computation ; finding the required answer
let v = [ ] ; let dp = [ ] ; let exp_c = [ ] ; function FindMax ( i , r , w , n , c , 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 ( let j = 0 ; j < k ; j ++ ) { let 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 ] ; } function PreCompute ( n , c , k ) { for ( let i = 0 ; i < k ; i ++ ) { exp_c . push ( 0 ) ; } exp_c [ 0 ] = 1 ; for ( let i = 1 ; i < k ; i ++ ) { exp_c [ i ] = ( exp_c [ i - 1 ] * ( c + 1 ) ) ; } for ( let i = 0 ; i < n ; i ++ ) { dp . push ( [ ] ) ; } for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < ( exp_c [ k - 1 ] * ( c + 1 ) ) ; j ++ ) { dp [ i ] [ 0 ] ; } } for ( let i = 0 ; i < n ; i ++ ) { v . push ( [ ( exp_c [ k - 1 ] * ( c + 1 ) ) ] ) ; } for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < v [ i ] . length ; j ++ ) { v [ i ] [ j ] = false ; } } let R = 0 ; for ( let i = 0 ; i < k ; i ++ ) { R += exp_c [ i ] * c ; } return R ; } let w = [ 3 , 8 , 9 ] ; let k = 1 , c = 11 ; let n = w . length ; let r = PreCompute ( n , c , k ) ; document . write ( FindMax ( 0 , r , w , n , c , k ) ) ;