邀请人参加聚会的最佳算法

Question

我是新来的,但在我的教科书中有问题.不幸的是它没有答案所以我想知道是否有人可以请求帮助.问题是:

您的任务是在公司内传播邀请.你只有时间与一定数量的人交谈,但你保证,如果你邀请某人,他们会邀请他们的老板,那个人会邀请他们的老板,等等,一直到CEO.您已绘制出整个公司层次结构,并为每个人分配了一个值,表明邀请他们的价值.鉴于此设置以及您可以与之交谈的人数限制,您需要计算要邀请的最佳人员集.一组最佳人选将通过您的选择直接或间接地最大化所有受邀人员的总价值.

将会有一个人,即CEO,在层次结构中没有老板.所有其他人最终都会在命令链上回答这个人,但不一定直接.

保证每个人最多只有一个老板,但老板可能会轮流拥有另一个老板.例如,A人可能有老板B,老板是C,老板是D,老板是CEO.因此,影响人A将自动影响B,C,D和CEO.

不同的员工可能在命令链中有共同的老板.您不会为不止一次影响某人获得额外的价值.例如,如果A和B都直接回答CEO,并且您对两者都有影响,那么您将收到val(A)+ val(B)+ val(CEO)的值,而不是val(A)+ val(B) + 2val(CEO).

给定正整数j,选择最终会产生最大整体价值的j人.

我知道蛮力方法只是在列表中搜索最大值j次,但这不是很有帮助.我认为有一种动态的编程方法,但我的尝试并不总能提供正确的答案.任何帮助,将不胜感激!

Answer 1

设V [e,k]是向e和e的直接和间接下属发出k个邀请的最大值,忽略e的所有直接和间接监督者的价值.如果员工e没有下属,那么基本案例就是

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

如果员工e0有两个下属,e1和e2,则重复出现

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

与超过两名员工的天真卷积太慢,所以我们必须卷入第一对然后在其余部分卷积.我要省略细节.