Double Knapsack | Dynamic Programming | 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 ; Driver code ; Input array ; 3D array to store states of DP ; Number of elements in the array ; Capacity of knapsacks ; Function to be called
def maxWeight ( arr , n , w1_r , w2_r , i ) : NEW_LINE INDENT if i == n : NEW_LINE INDENT return 0 NEW_LINE DEDENT if dp [ i ] [ w1_r ] [ w2_r ] != - 1 : NEW_LINE INDENT return dp [ i ] [ w1_r ] [ w2_r ] NEW_LINE DEDENT fill_w1 , fill_w2 , fill_none = 0 , 0 , 0 NEW_LINE if w1_r >= arr [ i ] : NEW_LINE INDENT fill_w1 = arr [ i ] + maxWeight ( arr , n , w1_r - arr [ i ] , w2_r , i + 1 ) NEW_LINE DEDENT if w2_r >= arr [ i ] : NEW_LINE INDENT fill_w2 = arr [ i ] + maxWeight ( arr , n , w1_r , w2_r - arr [ i ] , i + 1 ) NEW_LINE DEDENT fill_none = maxWeight ( arr , n , w1_r , w2_r , i + 1 ) NEW_LINE dp [ i ] [ w1_r ] [ w2_r ] = max ( fill_none , max ( fill_w1 , fill_w2 ) ) NEW_LINE return dp [ i ] [ w1_r ] [ w2_r ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 8 , 2 , 3 ] NEW_LINE maxN , maxW = 31 , 31 NEW_LINE dp = [ [ [ - 1 ] * maxW ] * maxW ] * maxN NEW_LINE n = len ( arr ) NEW_LINE w1 , w2 = 10 , 3 NEW_LINE print ( maxWeight ( arr , n , w1 , w2 , 0 ) ) NEW_LINE DEDENT