Children And Chocolates

The basic idea is to find the number of connected components in the graph. We need to find the total sum of chocolates present in a connected component with their number of children to get the number of children present in the connected component with their total sum of chocolates present. We then need to find the maximum number of children whose sum of chocolates is smaller than equal to ‘C’.
 

Here is the algorithm :
 

1. Create a graph (say, ‘GRAPH’) using the ‘FRIENDS’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
2. Push the edges in the ‘GRAPH’.
3. Create an array (say, ‘VISITED’) which will be used to mark all the visited vertices and initialize it with ‘FALSE’ for every vertex present in the ‘GRAPH’.
4. Create a variable (say, ‘RES’) to store the count of maximum children.
5. Call the ‘DFS’ function, DFS(‘GRAPH’, ‘U’, ‘VISITED’, ‘CHOCOLATES’) for every unvisited vertex to count for the number of connected components. where ‘U’ is an unvisited vertex and store its result in a variable (say, ‘TEMP’).
   1. Store ‘TEMP’ and number of children in that connected component in arrays (say ‘COUNT’ and ‘CHILDREN’ respectively).
   2. Call the HELPER(‘C’, ‘COUNT’, ‘CHILDREN’) to find the maximum number of children whose sum of chocolates is smaller than ‘C’.
6. Finally, return the value returned by the HELPER function.

DFS(‘GRAPH’, ‘U’, ‘VISITED’, ‘CHOCOLATES’)

1. Mark ‘U’ as visited in the ‘VISITED’ array.
2. Iterate over all the adjacent vertices of the ‘U’ (say, iterator ‘V’).
   • If ‘VISITED[GRAPH[U][V]]’ is equal to ‘FALSE’
     • Update ‘VISITED[GRAPH[U][V]]’ as 1.
     • Call DFS on all adjacent vertices of ‘U’ while adding the chocolates of each friend.

HELPER function finds the maximum number of children that can get chocolates from the shop. For each value of ‘CHILDREN’, we have two options: whether to include the current value or not. So, we can obtain the maximum count by:

1. Maximum count obtained by ‘N’ - 1 childrens, and ‘C’ chocolates (exclude ‘Nth’ children)
2. Value of ‘Nth’ child plus the maximum value obtained by ‘N’ - 1 childrens and ‘C’ minus the chocolate required by a current number of childrens. ( include ‘Nth’ child)
    

HELPER(‘C’, ‘COUNT’, ‘CHILDREN’, ‘S’)  (where ‘N’ is the size of the ‘COUNT’ array).

1. Base case
   • If ‘C’ or ‘S’  is equal to 0, return 0.
2. Check if ‘COUNT[S - 1] is greater than ‘C’
   • Call the HELPER function by not including the current children.
3. Else
   • Call the HELPER function two times by including the current children and not including the current children and return the maximum value.

The approach is similar to the previous approach. In this approach, we will use an array (say, ‘DP’) to store the recursive calls. 

How do we know we are calling the same function more than once?

Let ‘N’ be 3 and ‘C’ be 2.

We call HELPER function on values (3, 2)

(3, 2) if we include current value then it calls helper function on values (2, 1) ->(1, 1), (1, 0) and so on.

(3, 2) if we exclude current value then it calls helper function on values (2, 2) -> (1, 2), (1, 1)  and so on.

As we can see (1, 1) is called twice. For large values of ‘N’ and ‘C’ there can be many repeated recursive calls. To avoid that we can use memoization to store recursive calls.

Here is the algorithm :
 

HELPER(‘C’, ‘COUNT’, ‘CHILDREN’, ‘S’, ‘DP’)  (where ‘N’ is the size of the ‘COUNT’ array, ‘DP’ is the array used for memoization initialized with -1, and ‘S’ is the current index).
 

1. Base case
   • If ‘S’ is equal to 0 or ‘C’ is equal to 0, return 0.
2. Check if ‘DP[S - 1][C]’ is not equal to -1
   • Return ‘DP[S - 1][C]’.
3. Check if ‘COUNT[S - 1] is greater than ‘C’
   • Call the HELPER function by not including the current children and store its value in the ‘DP’ array.
4. Else
   • Call the HELPER function two times by including the current children and not including the current children and return the maximum value and store the value in the ‘DP’ array.

The approach is similar to the previous approach. In this approach, we will use the bottom-up approach to find the count of children for all possible numbers of chocolates from 1 to ‘W’. ‘DP[i]’ denotes the maximum number of children having ‘i’ number of chocolates. 
 

Here is the algorithm :

HELPER(‘C’, ‘COUNT’, ‘CHILDREN’, ‘S’)  (where ‘N’ is the size of the ‘COUNT’ array).
 

1. Create an array (say, ‘DP’) of size ‘C’ initialized with 0.
2. Run a loop from 1 to ‘S’ (say, iterator ‘i’)
   • Run a loop from 1 to ‘W’ (say, iterator ‘j’)
     • Check if ‘COUNT[i - 1] is smaller than equal to ‘W’
       • Update ‘DP[j]’ with value maximum of ‘DP[j]’ and ‘CHILDREN[i - 1]’ plus ‘DP[j - COUNT[i - 1]]’.
3. Finally, return ‘DP[C]’.