Problem 3: City College is holding a fundraiser at the XYZ corporation. Each emp

Question

Problem 3: City College is holding a fundraiser at the XYZ corporation. Each employee a at XYZ as pledged to contribute nothing. to City College if invited to the fundraiser, otherwise he/she will contribute tree. The XYZ CEO is at the top and the children of each node are its direct subordinates. want to invite an employee and his/her direct supervisor to the party. of donations that City College will receive at the party. The employees at XYZ are organized according to a hyerarchical structure which we can represent as a To avoid fights at the party and make sure that people can talk and drink freely, City College does not Your job is to come up with a guest list that satisfies the above constraints and maximizes the amount

Explanation / Answer

We will use the hierarachical tree say T, to compute the guest list L and maximum output. Array A, whose length is equal to depth of tree which is intially empty will contain summation cx at each depth. So A[i] will contain summation of contribution cx of each node x whose depth is i. Let depth of root node is 1. Another array B we will create, where B[i] contains the maximum contribution that can come from nodes whose depth is >=i if the nodes at depth i is included. Once we obtained array A after Breadth First Search, we can compute array B by dynamic programing by going in reverse index, i.e. from index d to 1 where d is maximum depth.

ALGO

1. Perform breath first search in T and according to depth of node x from root, add the value cx to A[i], where i is the depth of node x. Let d is maximum depth

2. B[d] = A[d]; B[d-1]=A[d-1]; B[d-2]=A[d-2]+A[d];  

3. For i=d-3 to 1:

4. B[i]=A[i]+max(B[i+2],B[i+3]);

5. if B[1]>B[2]:

6. then {maximum=B[1]; i=1; L.ADD[1];}

7. else:  

8 { maximum=B[2]; i=2; L.ADD[2];}

9. While i<=d-2:

10. if B[i]==A[i]+B[i+2]

11. then {L.ADD(i+2); i=i+2;}

12. else {L.ADD(i+3); i=i+3;}

Note that, while computing array B, if I am including the nodes at depth i, then I can not include node at depth i+1, but I have to include either the nodes at depth >=i+2, or I can include nodes at depth >=i+3 but not both. So the equation at line number 4 will give B[i] using dynamic programming. At the end, I am checking either B[1] or B[2] will contain the maximum value. I will include that index in list L. Then I will go till bottom of index d, by checking entry of array B and array A to know, which depth is included in calculating B[i], I will use that depth and go further down till end. Node that List L contain the depth of nodes in tree T to add in guest list and maximum cantains the maximum fund that can be generated.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.