UniLecs #118_1. Сумма на дереве

UniLecs

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

Входные данные: edges - список ребер, которым задано дерево; каждое ребро определятся двумя вершинами: (i, j).

value - упорядоченный массив значений в вершинах, где value(i) - значение вершины i (i от 1 до N; 1 <= N <= 10^4).

Вывод: максимальную сумму значений вершин в подмножестве.

Пример:

Edges = [ (1, 2), (1, 3), (2, 4) ]

Value = [ 1, 1, 0, 1] (Пояснение: 1я вершина - значение 1; 2я вершина - 1; 3я вершина - 0; 4я вершина - 1)

Answer = 2

Реализация:

@PeYceBall, F#: 1 балл

https://gist.github.com/PeYceBall/cf5ea95ff347fadb57c5c58b53d482ae

Test:

https://repl.it/repls/NumbWarpedOs

2. @akolosov364, JS: 1 балл

Идея в том что вначале группируются все возможные пары элементов, в виде ВЕРШИНА: {Предок1, Предок2, ...} и наоборот, если ребра заданы наоборот. После этого составляются все возможные комбинации вершин. При добавлении вершины, нужно учесть что, вершины, которые лежат с ней на 1 ребре нельзя использовать в дальнейшем. Если нарушается условие, то проверяется следущая комбинация.

https://gist.github.com/KolosovAO/9ef43d17d70de823a803794ab96e3176

Test:

https://repl.it/repls/BeigeTediousNormalform

3. @kirillmotrichkin, Python: 1 балл

Динамическое программирование: возьмём вершину и решим задачу отдельно при условии, что она добавлена в подмножество, и отдельно, что нет. И выберем вариант, где сумма получилась максимальной. Так как от любой вершины будут начинаться несколько поддеревьев, то будем решать задачи для каждого поддерева

https://gist.github.com/superkiria/befecdd591c88d6a6ad779b48156f304

Test:

https://repl.it/repls/HarshCapitalBots

4. @tvolf, PHP: 1 балл

Для решения задачи используем метод динамического программирования. Рассмотрим поддерево с корнем в вершине v. В этом случае возможны 2 ситуации вычисления максимальной суммы: когда мы включаем значение вершины v в итоговое множество и когда мы ее не используем. В первом случае максимальная сумма вершин равна сумме веса самой вершины v и суммы максимальных сумм всех поддеревьев с вершинами, не включающими детей вершины v. Во втором случае максимальная сумма вершин поддерева будет равна сумме максимальных сумм поддеревьев для каждого ребенка вершины v. При этом выбираем максимальное значение из 2-ух: когда ребенок входит в множество выбранных вершин и когда он не входит в это множество.