Maximize the happiness of the groups on the Trip | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MaxHappiness ( int A , int N , vector < string > v ) { string str ; int val [ N ] , wt [ N ] , c = 0 ; for ( int i = 0 ; i < N ; i ++ ) { str = v [ i ] ; c = 0 ; for ( int j = 0 ; str [ j ] ; j ++ ) { if ( str [ j ] == ' c ' ) c += 4 ; else if ( str [ j ] == ' w ' ) c += 3 ; else if ( str [ j ] == ' m ' ) c += 2 ; else c ++ ; } c *= str . length ( ) ; val [ i ] = c ; wt [ i ] = str . length ( ) ; } int k [ N + 1 ] [ A + 1 ] ; for ( int i = 0 ; i <= N ; i ++ ) { for ( int w = 0 ; w <= A ; w ++ ) { if ( i == 0 w == 0 ) k [ i ] [ w ] = 0 ; else if ( wt [ i - 1 ] <= w ) k [ i ] [ w ] = max ( val [ i - 1 ] + k [ i - 1 ] [ w - wt [ i - 1 ] ] , k [ i - 1 ] [ w ] ) ; else k [ i ] [ w ] = k [ i - 1 ] [ w ] ; } } return k [ N ] [ A ] ; } int main ( ) { int A = 5 ; vector < string > v = { " mmo " , " oo " , " cmw " , " cc " , " c " } ; int N = v . size ( ) ; cout << MaxHappiness ( A , N , v ) ; return 0 ; }