text: Double Knapsack | Dynamic Programming | C ++ 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 ; Driver code ; Input array ; Initializing the array with - 1 ; Number of elements in the array ; Capacity of knapsacks ; Function to be called
code: #include <bits/stdc++.h> NEW_LINE #define maxN  31 NEW_LINE #define maxW  31 NEW_LINE using namespace std ; int dp [ maxN ] [ maxW ] [ maxW ] ; int maxWeight ( int * arr , int n , int w1_r , int w2_r , int i ) { if ( i == n ) return 0 ; if ( dp [ i ] [ w1_r ] [ w2_r ] != -1 ) return dp [ i ] [ w1_r ] [ w2_r ] ; int 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 ] = max ( fill_none , max ( fill_w1 , fill_w2 ) ) ; return dp [ i ] [ w1_r ] [ w2_r ] ; } int main ( ) { int arr [ ] = { 8 , 2 , 3 } ; memset ( dp , -1 , sizeof ( dp ) ) ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int w1 = 10 , w2 = 3 ; cout << maxWeight ( arr , n , w1 , w2 , 0 ) ; return 0 ; }