Best Algorithm to Invite People to Party

Question

I'm new here, but have question found in my text book. Unfortunately it has no answers so I was wondering if someone could please help. The question is:

You are given the task of spreading invitations within a company. You only have the time to talk to a certain amount of people, but you are guaranteed that if you invite somebody, they will invite their boss, that person will invite their boss, and so on, all the way up to the CEO. You have mapped out the entire company hierarchy, and assigned a value to each person, indicating how valuable it would be to invite them. Given this setup and a limit on the number of people you can speak with, you want to compute the optimal set of people to invite. An optimal set of people will maximize the total value of all persons invited, directly or indirectly, by your selection.

There will be exactly one person, the CEO, with no boss in the hierarchy. All other people will eventually answer to this person on the command chain, but not necessarily directly.

You are guaranteed that each person will have at most one boss, but that boss may have another in turn. For example, person A may have a boss B, whose boss is C, whose boss is D, whose boss is the CEO. Thus influencing person A will automatically influence B, C, D, and the CEO.

Different employees may have bosses in common in the command chain. You DO NOT obtain additional value for influencing a person more than once. For example, if A and B both answer directly to the CEO, and you influence both, you will receive a value of val(A)+val(B)+val(CEO), not val(A)+val(B)+2val(CEO).

Given a positive integer j, select the j people that will ultimately result in the greatest overall value.

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

Answer 1

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

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

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

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

The naive convolution with more than two employees is too slow, so we have to convolve the first pair and then convolve in the rest. I'm going to omit the details.