Maximize the happiness of the groups on the Trip | Python3 implementation of the approach ; Function to return the maximized happiness ; Two arrays similar to 0 1 knapsack problem ; To store the happiness of the current group ; Current person is a child ; Woman ; Man ; Old person ; Group 's happiness is the sum of happiness  of the people in the group multiplied by  the number of people ; Solution using 0 1 knapsack ; Driver code ; Number of seats ; Groups
import numpy as np NEW_LINE def MaxHappiness ( A , N , v ) : NEW_LINE INDENT val = [ 0 ] * N ; wt = [ 0 ] * N ; c = 0 ; NEW_LINE for i in range ( N ) : NEW_LINE INDENT string = v [ i ] ; NEW_LINE c = 0 ; NEW_LINE for j in range ( len ( string ) ) : NEW_LINE INDENT if ( string [ j ] == ' c ' ) : NEW_LINE INDENT c += 4 ; NEW_LINE DEDENT elif ( string [ j ] == ' w ' ) : NEW_LINE INDENT c += 3 ; NEW_LINE DEDENT elif ( string [ j ] == ' m ' ) : NEW_LINE INDENT c += 2 ; NEW_LINE DEDENT else : NEW_LINE INDENT c += 1 ; NEW_LINE DEDENT DEDENT c *= len ( string ) ; NEW_LINE val [ i ] = c ; NEW_LINE wt [ i ] = len ( string ) ; NEW_LINE DEDENT k = np . zeros ( ( N + 1 , A + 1 ) ) NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT for w in range ( A + 1 ) : NEW_LINE INDENT if ( i == 0 or w == 0 ) : NEW_LINE INDENT k [ i ] [ w ] = 0 ; NEW_LINE DEDENT elif ( wt [ i - 1 ] <= w ) : NEW_LINE INDENT k [ i ] [ w ] = max ( val [ i - 1 ] + k [ i - 1 ] [ w - wt [ i - 1 ] ] , k [ i - 1 ] [ w ] ) ; NEW_LINE DEDENT else : NEW_LINE INDENT k [ i ] [ w ] = k [ i - 1 ] [ w ] ; NEW_LINE DEDENT DEDENT DEDENT return k [ N ] [ A ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = 5 ; NEW_LINE v = [ " mmo " , " oo " , " cmw " , " cc " , " c " ] ; NEW_LINE N = len ( v ) ; NEW_LINE print ( MaxHappiness ( A , N , v ) ) ; NEW_LINE DEDENT