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
using System ; class GFG { static readonly int V_SUM_MAX = 1000 ; static readonly int N_MAX = 100 ; static readonly int W_MAX = 10000000 ; static int [ , ] dp = new int [ V_SUM_MAX + 1 , N_MAX ] ; static bool [ , ] v = new bool [ V_SUM_MAX + 1 , N_MAX ] ; static 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 ] = true ; 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 ] ; } static 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 ; } public static void Main ( String [ ] args ) { int [ ] w = { 3 , 4 , 5 } ; int [ ] val = { 30 , 50 , 60 } ; int n = w . Length ; int C = 8 ; Console . WriteLine ( maxWeight ( w , val , n , C ) ) ; } }