Лучший алгоритм для приглашения людей на вечеринку

Пусть V[e, k] будет максимальным значением выдачи k приглашений e и его прямым и косвенным подчиненным, игнорируя значение всех прямых и косвенных начальников 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].

Простая свертка с более чем двумя сотрудниками слишком медленная, поэтому мы должны свернуть первую пару, а затем свернуть остальные. Я опущу подробности.

Изменить: этот ответ предполагает, что все значения для приглашения людей неотрицательны.

Эту задачу можно решить с помощью жадного алгоритма. Давайте сначала обсудим случай, когда все значения равны, поэтому мы просто пытаемся пригласить максимальное количество людей. Ключевое наблюдение заключается в том, что в любом оптимальном решении вы всегда должны выбирать человека с наибольшим количеством прямых или косвенных начальников. Вот краткое объяснение того, почему: предположим, что у человека X больше начальников, и у вас есть выборки, не включающие человека X. Рассмотрите человека Y среди ваших выборов, у которого больше всего начальников с X. Затем вы можете добиться большего успеха, выбрав X вместо Y.

Итак, на первом этапе мы всегда можем жадно выбрать человека с наибольшим превосходством. Затем задача сводится к той же задаче на нескольких деревьях меньшего размера. Например, предположим, что мы выбираем 3 приглашенных из следующего дерева:

       A
   B       C
 D   E   F   G
H I J K L M N O

Наш первый выбор будет H, что автоматически дает нам D, B и A. Затем остается выбрать 2 из трех деревьев

I   E      C
   J K   F   G
        L M N O

Следующий лучший выбор — L и так далее.

Мы можем сделать это эффективно, потому что нам просто нужно отслеживать самого глубокого потомка (не обязательно прямого потомка) каждого узла, который мы можем вычислить заранее. Затем нам нужна какая-то структура данных очереди приоритетов, чтобы выбрать лучшее дерево для выбора. Если вы выбираете k людей из иерархии размером n, это должно дать алгоритм O(n + k log n).

Чтобы распространить это на случай, когда значения могут быть неравными, в основном работает та же самая идея, за исключением того, что вместо глубины вам нужно вычислить общую стоимость всех вышестоящих. Для каждого узла X вы отслеживаете дочерний узел Y, который имеет наибольшее общее значение на пути между Y и X.

Похоже на проблему с графиком. Вы можете использовать идею связанных компонентов, чтобы реализовать решение этой проблемы.

• Первая итерация охватит всех в компании, где вы определите, кто является генеральным директором, а кто находится непосредственно под ним.
• В качестве начального набора компонентов возьмите каждого из начальников непосредственно ниже генерального директора.
• Затем для каждого другого человека вы будете использовать dfs, чтобы связать их с боссом 2-го уровня (это динамический подход).
• Вы хотите сделать эту последнюю часть таким образом, что если person F является боссом person E, который, в свою очередь, является боссом person D, ... вплоть до person A, то вы хотите, чтобы после dfs можно было сказать через O(1) раз этот человек F становится начальником человека A и наоборот.

Не забудьте вести подсчет для каждого босса, где подсчет будет представлять собой сумму значений всех людей ниже него, и, при желании, отслеживать количество людей.

Оптимальным случаем будет то, что вы сначала найдете всех людей ниже в цепочке, в противном случае алгоритм должен работать за O (nk), где k — максимальная цепочка снизу вверх.