The best algorithm for inviting people to a party

Question

I am new here, but there is a question in my tutorial. Unfortunately, he has no answers, so I was wondering if anyone could help. The question arises:

You have been given the task of distributing invitations within the company. You only have time to talk with a certain number of people, but you are guaranteed that if you invite someone, they will invite their boss, that person will invite his boss, etc., up to the CEO. You have outlined the entire hierarchy of companies and assigned value to each person, indicating how valuable it would be to invite them. Given this setting, and limit the number of people you can talk to, you want to calculate the optimal set of people for the invitation. An optimal set of people maximizes the total value of all the invitees, directly or indirectly, of your choice.

There will be exactly one person, the CEO, without a boss in the hierarchy. All other people will ultimately answer that person in the command chain, but not necessarily.

You are guaranteed that each person will have no more than one boss, but this boss may have another one in turn. For example, person A may have boss B, whose boss is C, whose boss is D, whose boss is CEO. Thus, the influence of person A will automatically affect B, C, D and CEO.

Different employees may have common tasks in the team chain. You do not get additional value for impacting a person more than once. For example, if A and B both respond directly to the CEO, and you influence both, you will get the value val (A) + val (B) + val (CEO), not val (A) + val (B) + 2val (CEO).

Given a positive integer j, select j people who will ultimately result in the highest total cost.

I know that brute force approach is to just search the list for the maximum value j times, but this is not very useful. I think there is an approach to dynamic programming, but my attempt did not always give the correct answer. Any help would be appreciated!

Answer 1

Let V [e, k] be the maximum value for issuing k invitations e and e to direct and indirect subordinates, ignoring the value of all direct and indirect supervisors e. If employee e has no subordinates, then the base case

V[e, k], k = 0 = 0 V[e, k], k > 0 = val(e). 

If employee e0 has two subordinates, e1 and e2, then recurrence

 V[e0, k], k = 0 = 0 V[e0, k], k > 0 = max over j of val(e0) + V[e1, j] + V[e2, k - j]. 

A naive convolution with more than two employees is too slow, so we have to drill the first pair and then curl up the rest. I omit the details.

Answer 2

Edit: This answer assumes that the values ​​for inviting people are non-negative.

This problem can be solved using the greedy algorithm. Let's first discuss the case where the values ​​are equal, so we are just trying to invite the maximum number of people. The main observation is that in any optimal solution you should always choose the person with the greatest number of direct or indirect bosses. Here is a brief explanation: why person X has the majority of bosses, and you have a choice that does not include person X Consider person Y among your choices, which is shared by most superiors with X Then you can do it better by choosing X instead of Y

So, at the first stage, we can always eagerly choose a person with senior management. Then the problem boils down to the same problem on several smaller trees. For example, suppose we select 3 invitees from the following tree:

  A BC DEFG HIJKLMNO 

Our first choice will be H , which automatically gives us D , B and A Then it remains to choose 2 of the three trees

 IEC JKFG LMNO 

The next best choice is L , etc.

We can do this efficiently because we just need to track the deepest child (not necessarily a straight child) of each node, which we can calculate in advance. Then we need some sort of priority queue data structure to select the best tree to select. If you selected k people from a hierarchy of size n , this should give the O(n + k log n) algorithm.

In order to extend this to the case when the values ​​may be unequal, basically the same idea works, except for the depth, you need to calculate the total cost of all the bosses. For each node X you track the child of Y , which has the most common value along the path between Y and X

Answer 3

Sounds like a graph problem . You can use the idea of ​​connected components to implement this solution.

• The first iteration will cover everyone in the company, where you will determine who is the CEO and who is directly below him.
• Take each of the bosses directly below the CEO as the source set of components.
• Then, for each other person, you will use dfs to link them to the 2nd level boss (this is a dynamic approach).
• You want to do this last part so that if person F is the boss of person E , who, in turn, is the boss of person D , ... up to person A , then you want after dfs to be able to say in O (1) the time that person F is the boss of person A and vice versa.

Remember to keep a counter for each boss, where the score will be the sum of the values ​​of all the people below him and possibly track the number of people.

The best case is that first you find all the people in the chain, otherwise the algorithm should work in O (nk), where k is the maximum chain from bottom to top