You are ignoring the possibility that we might want to leave to
adjacent levels for a higher-valued descendant.
I think this should be formulated as a DP problem.
Writing the recursive version:
optimal value of node(at level l) = max of {its value+sum of optimal
values of level l+2 , sum of optimal values of all children at level
l+1}
T(n)=Max{ C_n +Sum_{i=1 to k}(all children at T(n+2)), Sum_{i=1 to k}
T(l+1) for all k children
We start with T(0) :
T(l) : Best solution for level l
C_i= Value contained in node i
Not sure if notation is explicit..
Explaning with the example tree discussed in prev threads..
4(1)
/ \
1(2) 20(3)
/ \ / \
10(4) 5(5) 2(6) 3(7)
P.S : no in brackets denote their ids.
T(1)= Max{4+T(4)+T(5)+T(6)+ T(7), T(2) + T(3)}
T(2) = Max{1, T(4)+T(5)} = Max{1,10+5} = 15
T(3) = Max{20, T(6)+t(7) } = 20
Substituting in T(1), we have
T(1) = Max{4+10+2+2, 20+15 }
T(1) = 35.
A complete solution would have a bottom up approach, storing computed
values of tree nodes. I guess its similar to one of the DP problems
discussed in CLR, for tree organization.
I am not sure if starting from any node is good idea, because we shud
maek use of tree organization to eliminate the number of combinations.
Hope this helps.
~anshu.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
