Maximum sum of values of N items in 0 | Function to find the maximum value ; base condition ; K elements already reduced to half of their weight ; Dont include item ; If weight of the item is less than or equal to the remaining weight then include the item ; Return the maximum of both cases ; If the weight reduction to half is possible ; Skip the item ; Include item with full weight if weight of the item is less than the remaining weight ; Include item with half weight if half weight of the item is less than the remaining weight ; Return the maximum of all 3 cases ; Driver Code
def maximum ( value , weight , weight1 , flag , K , index , val_len ) : NEW_LINE INDENT if ( index >= val_len ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( flag == K ) : NEW_LINE INDENT skip = maximum ( value , weight , weight1 , flag , K , index + 1 , val_len ) NEW_LINE full = 0 NEW_LINE if ( weight [ index ] <= weight1 ) : NEW_LINE INDENT full = value [ index ] + maximum ( value , weight , weight1 - weight [ index ] , flag , K , index + 1 , val_len ) NEW_LINE DEDENT return max ( full , skip ) NEW_LINE DEDENT else : NEW_LINE INDENT skip = maximum ( value , weight , weight1 , flag , K , index + 1 , val_len ) NEW_LINE full = 0 NEW_LINE half = 0 NEW_LINE if ( weight [ index ] <= weight1 ) : NEW_LINE INDENT full = value [ index ] + maximum ( value , weight , weight1 - weight [ index ] , flag , K , index + 1 , val_len ) NEW_LINE DEDENT if ( weight [ index ] / 2 <= weight1 ) : NEW_LINE INDENT half = value [ index ] + maximum ( value , weight , weight1 - weight [ index ] / 2 , flag , K , index + 1 , val_len ) NEW_LINE DEDENT return max ( full , max ( skip , half ) ) NEW_LINE DEDENT DEDENT value = [ 17 , 20 , 10 , 15 ] NEW_LINE weight = [ 4 , 2 , 7 , 5 ] NEW_LINE K = 1 NEW_LINE W = 4 NEW_LINE val_len = len ( value ) NEW_LINE print ( maximum ( value , weight , W , 0 , K , 0 , val_len ) ) NEW_LINE