Knapsack with large Weights | Java implementation of the approach ; To store the states of DP ; Function to solve the recurrence relation ; Base cases ; Marking state as solved ; Recurrence relation ; Function to return the maximum weight ; Iterating through all possible values to find the the largest value that can be represented by the given weights ; Driver code
class GFG { static final int V_SUM_MAX = 1000 ; static final int N_MAX = 100 ; static final int W_MAX = 10000000 ; static int dp [ ] [ ] = new int [ V_SUM_MAX + 1 ] [ N_MAX ] ; static boolean v [ ] [ ] = new boolean [ V_SUM_MAX + 1 ] [ N_MAX ] ; static int solveDp ( int r , int i , int w [ ] , int val [ ] , int n ) { if ( r <= 0 ) return 0 ; if ( i == n ) return W_MAX ; if ( v [ r ] [ i ] ) return dp [ r ] [ i ] ; v [ r ] [ i ] = true ; dp [ r ] [ i ] = Math . min ( solveDp ( r , i + 1 , w , val , n ) , w [ i ] + solveDp ( r - val [ i ] , i + 1 , w , val , n ) ) ; return dp [ r ] [ i ] ; } static int maxWeight ( int w [ ] , int val [ ] , int n , int c ) { for ( int i = V_SUM_MAX ; i >= 0 ; i -- ) { if ( solveDp ( i , 0 , w , val , n ) <= c ) { return i ; } } return 0 ; } public static void main ( String [ ] args ) { int w [ ] = { 3 , 4 , 5 } ; int val [ ] = { 30 , 50 , 60 } ; int n = w . length ; int C = 8 ; System . out . println ( maxWeight ( w , val , n , C ) ) ; } }