Knapsack with large Weights | Python3 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
V_SUM_MAX = 1000 NEW_LINE N_MAX = 100 NEW_LINE W_MAX = 10000000 NEW_LINE dp = [ [ 0 for i in range ( N_MAX ) ] for i in range ( V_SUM_MAX + 1 ) ] NEW_LINE v = [ [ 0 for i in range ( N_MAX ) ] for i in range ( V_SUM_MAX + 1 ) ] NEW_LINE def solveDp ( r , i , w , val , n ) : NEW_LINE INDENT if ( r <= 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( i == n ) : NEW_LINE INDENT return W_MAX NEW_LINE DEDENT if ( v [ r ] [ i ] ) : NEW_LINE INDENT return dp [ r ] [ i ] NEW_LINE DEDENT v [ r ] [ i ] = 1 NEW_LINE dp [ r ] [ i ] = min ( solveDp ( r , i + 1 , w , val , n ) , w [ i ] + solveDp ( r - val [ i ] , i + 1 , w , val , n ) ) NEW_LINE return dp [ r ] [ i ] NEW_LINE DEDENT def maxWeight ( w , val , n , c ) : NEW_LINE INDENT for i in range ( V_SUM_MAX , - 1 , - 1 ) : NEW_LINE INDENT if ( solveDp ( i , 0 , w , val , n ) <= c ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT return 0 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT w = [ 3 , 4 , 5 ] NEW_LINE val = [ 30 , 50 , 60 ] NEW_LINE n = len ( w ) NEW_LINE C = 8 NEW_LINE print ( maxWeight ( w , val , n , C ) ) NEW_LINE DEDENT