A company is planning a party for its employees. A fun rating is assigned to eve

Question

A company is planning a party for its employees. A fun rating is assigned to every employee. The employees are organized into a strict hierarchy, i.e. a tree rooted the president. There is one restriction, though, on the guest list to the party: an employee and his/her immediate supervisor (parent in the tree) cannot both attend the party. You wish to prepare a guest list for the party that maximizes the sum of fun ratings of the guests. Show that greedily choosing guests according to fun rating, will not work. Then, formulate a dynamic programming solution

Can someone suggest me how to proceed with this ? I couldn't get the question properly. Is the fun rate of the president higher than that of his descendants ?

Explanation / Answer

The greedy algorithm is as follows:

So you need to come up with an employee hierarchy where this algorithm doesn't produce the best solution. There's a hint in the mouse-over box below:

It's enough to have three employees if you choose the right hierarchy and fun ratings.

Then, you need to design a dynamic programming algorithm that always produces the correct solution. If you need more help with that, you'll need to ask a more specific question.

There's nothing in the question that says the president has the highest fun rating.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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