Knapsack with large Weights | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define V_SUM_MAX  1000 NEW_LINE #define N_MAX  100 NEW_LINE #define W_MAX  10000000 NEW_LINE int dp [ V_SUM_MAX + 1 ] [ N_MAX ] ; bool v [ V_SUM_MAX + 1 ] [ N_MAX ] ; 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 ] = 1 ; dp [ r ] [ i ] = min ( solveDp ( r , i + 1 , w , val , n ) , w [ i ] + solveDp ( r - val [ i ] , i + 1 , w , val , n ) ) ; return dp [ r ] [ i ] ; } 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 ; } int main ( ) { int w [ ] = { 3 , 4 , 5 } ; int val [ ] = { 30 , 50 , 60 } ; int n = sizeof ( w ) / sizeof ( int ) ; int C = 8 ; cout << maxWeight ( w , val , n , C ) ; return 0 ; }