Sample input above: Let us say CEO of your company is planning a company party.

Question

Sample input above:

Let us say CEO of your company is planning a company party. Company's hierarchical structure is specified in tree structure, the root node being CEO. The personnel office has ranked each employee with a conviviality rating (i.e. how much (s)he can have fun? J), which is a real number. In order to make the party fun for all attendees, CEO does not want both an employee and his/her immediate boss to attend. Determine an algorithm to make up the guest list. The goal is to maximize the sum of the conviviality ratings of the guests.

Your immediate goal is to find the optimal solution for this instance, then try to get an idea for the general algorithm.

Explanation / Answer

Algorithm

PseudoCode

pair<int,int> maximumWeight(node *x)

/* first value in pair is if node is not contained, second value is if node is in set. */

{

if(x==NULL) return pair<int,int>(0,0);

pair<int,int> lft = maximumWeight(x->left);

pair<int,int> rgt = maximumWeight(x->right);

int fir = max(lft.first,lft.second)+max(rgt.first,rgt.second);

int sec = x->val+lft.first+rgt.first;

return pair<int,int>(fir,sec);

}

Use this function to iterate over the complete binary tree, passing root of the tree as arguement.

Logic

there are two values returned by the function.

First value is the maximum weight of the tree rooted at the node if node is not present in the required set.

Similarly, second value is the maximum value if node is present in the set.

To calculate these value for current nodes values of child nodes are calculated by calling the function recursively.

As for every node function is called only once,Efficiency of the code is O(n).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.