Maximum items that can be filled in K Knapsacks of given Capacity | package whatever do not write package name here ; 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
import java . io . * ; import java . util . * ; class GFG { static ArrayList < ArrayList < Boolean > > v = new ArrayList < ArrayList < Boolean > > ( ) ; static ArrayList < ArrayList < Integer > > dp = new ArrayList < ArrayList < Integer > > ( ) ; static ArrayList < Integer > exp_c = new ArrayList < Integer > ( ) ; static int FindMax ( int i , int r , int w [ ] , int n , int c , int k ) { if ( i >= n ) { return 0 ; } if ( v . get ( i ) . get ( r ) ) { return dp . get ( i ) . get ( r ) ; } v . get ( i ) . set ( r , true ) ; dp . get ( i ) . set ( r , FindMax ( i + 1 , r , w , n , c , k ) ) ; for ( int j = 0 ; j < k ; j ++ ) { int x = ( r / exp_c . get ( j ) ) % ( c + 1 ) ; if ( x - w [ i ] >= 0 ) { dp . get ( i ) . set ( r , Math . max ( dp . get ( i ) . get ( r ) , w [ i ] + FindMax ( i + 1 , r - w [ i ] * exp_c . get ( j ) , w , n , c , k ) ) ) ; } } return dp . get ( i ) . get ( r ) ; } static int PreCompute ( int n , int c , int k ) { for ( int i = 0 ; i < k ; i ++ ) { exp_c . add ( 0 ) ; } exp_c . set ( 0 , 1 ) ; for ( int i = 1 ; i < k ; i ++ ) { exp_c . set ( i , ( exp_c . get ( i - 1 ) * ( c + 1 ) ) ) ; } for ( int i = 0 ; i < n ; i ++ ) { dp . add ( new ArrayList < Integer > ( ) ) ; } for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < ( exp_c . get ( k - 1 ) * ( c + 1 ) ) ; j ++ ) { dp . get ( i ) . add ( 0 ) ; } } for ( int i = 0 ; i < n ; i ++ ) { v . add ( new ArrayList < Boolean > ( Arrays . asList ( new Boolean [ ( exp_c . get ( k - 1 ) * ( c + 1 ) ) ] ) ) ) ; } for ( int i = 0 ; i < n ; i ++ ) { Collections . fill ( v . get ( i ) , Boolean . FALSE ) ; } int R = 0 ; for ( int i = 0 ; i < k ; i ++ ) { R += exp_c . get ( i ) * c ; } return R ; } public static void main ( String [ ] args ) { int w [ ] = { 3 , 8 , 9 } ; int k = 1 , c = 11 ; int n = w . length ; int r = PreCompute ( n , c , k ) ; System . out . println ( FindMax ( 0 , r , w , n , c , k ) ) ; } }