Knapsack with large Weights | Javascript 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
var V_SUM_MAX = 1000 var N_MAX = 100 var W_MAX = 10000000 var dp = Array . from ( Array ( V_SUM_MAX + 1 ) , ( ) => Array ( N_MAX ) ) ; var v = Array . from ( Array ( V_SUM_MAX + 1 ) , ( ) => Array ( N_MAX ) ) ; function solveDp ( r , i , w , val , n ) { if ( r <= 0 ) return 0 ; if ( i == n ) return W_MAX ; if ( v [ r ] [ i ] ) return dp [ r ] [ i ] ; v [ r ] [ i ] = 1 ; 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 ] ; } function maxWeight ( w , val , n , c ) { for ( var i = V_SUM_MAX ; i >= 0 ; i -- ) { if ( solveDp ( i , 0 , w , val , n ) <= c ) { return i ; } } return 0 ; } var w = [ 3 , 4 , 5 ] ; var val = [ 30 , 50 , 60 ] ; var n = w . length ; var C = 8 ; document . write ( maxWeight ( w , val , n , C ) ) ;