L7 wrote:
> Suppose the following tree...
>
> 4
> / \
> 1 20
> / \ / \
> 10 2 2 3
>
> You now have EVEN -> 21, ODD -> 21
> However, if you take only the 10 and 20 nodes you get 30, with minimal
> node selection as a bonus.
The max would actually be !0 + 20 + 2 = 32, but still, what your saying
is valid.
One way to do it maybe like this:
1. Set up the adjacency matrix and 2 stack based data structures
called, 'picked' & 'can't_pick'
2. Start from anywhere (let's say root node).
3. add the node u selected to 'picked'.
4. add all the nodes that are adjacent to the one u picked (i.e. root
in this case) to 'can't_pick'.
5. from the adjacency matrix begin at the node that is not adjacent to
the one u picked (i.e. root in this case).
5a. if node picked in not in the 'picked' or 'can't_pick' list then
repeat from step 3 until u have folowed all the links.
5b. add the path and total to a global variable.
6. back to step 5 until you've gone through all the columns in the
adjacency matrix for the *row* that u began with (i.e. root). You pick
only column entries that are not adjacent to the row in question.
7. Now repeat all the above steps for the next row in the adjacency
matrix.
Illustration: (i've changed one node below (i.e. 5) from L2's example
for clarity)
4
/ \
1 20
/ \ / \
10 5 2 3
Steps as above for start point 20:
1. setup adjacency matrix, 'picked' & 'can't_pick'.
nodes that can be picked from adjacency matrix for node 20 = 1, 10, 5
2. start point is 20
3. picked = 20
4. can't_pick = 4, 2, 3
5. start point is 1, the first node in the adjacency matrix from step 1
for node 20 and 1 is not in the 'picked or 'can't_pick' list.
5a. picked = 20, 1
can't_pick = 4, 2, 3, 10, 5
nodes that can be picked from adjacency matrix for node 1 = 20,
2, 3 (all of these are in the 'picked' or 'can't pick' list)
so the first sum is 20 + 1 = 21.
6. next start point is 10, from step 1 and 10 is not in the 'picked' or
'can't pick'
back to step 5
5a. picked = 20, 10
can't pick = 4, 2, 3, 1
nodes that can be picked from adjacency matrix for node 10 =
4, 5, 2, 3 (4, 2, 3 are in the 'picked' or 'can't pick' list)
can only pick 5, so the second sum is 20 + 10 + 5 = 35
7. next start point is 5, from step 1 and 5 is not in the 'picked' or
'can't pick'
back to step 5
5a. picked = 20, 10, 5
can't pick = 4, 2, 3, 1
nodes that can be picked from adjacency matrix for node 5 =
10, 4, 20, 2, 3 (all of these are in the 'picked' or 'can't pick' list)
so the second sum is 20 + 10 + 5 = 35.
Repeat these steps for all the rows in the adjacency matrix.
Finally you arrive at the max = 35 for nodes 20, 10, 5.
This method might work, although seems a little tedious. I wonder if
there is a more elegant solution for this.
GoCooL
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
