Double Knapsack | Dynamic Programming | Javascript implementation of the above approach ; 3D array to store states of DP ; w1_r represents remaining capacity of 1 st knapsack w2_r represents remaining capacity of 2 nd knapsack i represents index of the array arr we are working on ; Base case ; Variables to store the result of three parts of recurrence relation ; Store the state in the 3D array ; Input array ; Number of elements in the array ; Capacity of knapsacks ; Function to be called
var maxN = 31 var maxW = 31 var dp = Array ( maxN ) ; for ( var i = 0 ; i < maxN ; i ++ ) { dp [ i ] = Array ( maxW ) ; for ( var j = 0 ; j < maxW ; j ++ ) { dp [ i ] [ j ] = Array ( maxW ) . fill ( - 1 ) ; } } function maxWeight ( arr , n , w1_r , w2_r , i ) { if ( i == n ) return 0 ; if ( dp [ i ] [ w1_r ] [ w2_r ] != - 1 ) return dp [ i ] [ w1_r ] [ w2_r ] ; var fill_w1 = 0 , fill_w2 = 0 , fill_none = 0 ; if ( w1_r >= arr [ i ] ) fill_w1 = arr [ i ] + maxWeight ( arr , n , w1_r - arr [ i ] , w2_r , i + 1 ) ; if ( w2_r >= arr [ i ] ) fill_w2 = arr [ i ] + maxWeight ( arr , n , w1_r , w2_r - arr [ i ] , i + 1 ) ; fill_none = maxWeight ( arr , n , w1_r , w2_r , i + 1 ) ; dp [ i ] [ w1_r ] [ w2_r ] = Math . max ( fill_none , Math . max ( fill_w1 , fill_w2 ) ) ; return dp [ i ] [ w1_r ] [ w2_r ] ; } var arr = [ 8 , 2 , 3 ] ; var n = arr . length ; var w1 = 10 , w2 = 3 ; document . write ( maxWeight ( arr , n , w1 , w2 , 0 ) ) ;