Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order).
A subgroup Z of V called an Isolated if it doesn't include two nodes that are adjacent (means that for all v in Z, his parent and his childs are not in Z).
A subgroup weight defined as the sum of the numbers of the included nodes in it.
Find an algorithm that finds an Isolated subgroup with the maximum weight.
I've tried to solve this question by set the root as the first node in the subgroup, then skip on his children and get the grandchild nodes.. something like that, but I don't find any greedy algorithm which can always take the nodes with the maximum number in it.
I thought about to sort the tree in a way that the left child of a node is minimum and the right child is maximum, but what if a node have more than 2 childs?
Best Answer
Hint: Write a dynamic programming algorithm that solves the problem for a subtree in two cases, either where you take the root node or you don't. You should be able to come up with a recursive relationship between these cases for a parent node at the top of a tree and children nodes at the tops of their trees. Basically, either you take the root node at the parent and then you do not take the root node at any child, or you do not take the root node at the parent and then you take the root node at at least one child (but not necessarily all of them). Then dynamic programming solves the problem quickly.