4
$\begingroup$

Recently, I came across this problem in my textbook. Any hints on how to solve this using dynamic programming?

"Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the supervisor relation forms a tree rooted at the president. The personnel office has ranked each employee with a conviviality rating, which is a real number. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend. Professor Stewart is given the tree that describes the structure of the corporation, using the left-child, right-sibling representation. Each node of the tree holds, in addition to the pointers, the name of an employee and that employee’s conviviality ranking. Describe an algorithm to make up a guest list that maximizes the sum of the conviviality ratings of the guests."

  • 4
    This question may be more suitable on http://stackoverflow.com.2010-09-28
  • 5
    This is not in anyway programming related.2010-09-28
  • 2
    Or you can try to ask this at [theoretical computer science SE](http://cstheory.stackexchange.com/)2010-09-28
  • 3
    Given that you ask "Any hints on how to solve this using dynamic programming?", how can this not be programming-related?2010-09-28
  • 0
    I'm with KennyTM and Isaac. This is clearly programming-related, or at the least belongs in theoretical computer science.2010-09-28
  • 1
    This is clearly programming related. btw, this will be off-topic on cstheory.stackexchange.com as that site is for research level CS Theory questions. Stackoverflow is more suitable, IMO. btw, is this homework? What have you done so far?2010-09-28
  • 6
    According to http://en.wikipedia.org/wiki/Dynamic_programming dynamic programming is *not* a subset of computer programming.2010-09-29
  • 2
    Dynamic programming is like linear programming, not like computer programming. The quote in my next comment (from http://home.ubalt.edu/ntsbarsh/opre640a/partviii.htm) is about linear programming, but it also applies to dynamic programming. (Ran out of characters.)2010-10-28
  • 1
    "It is important for the reader to appreciate, at the outset, that the "programming" in Linear Programming is of a different flavor than the "programming" in Computer Programming. In the former case, it means to plan and organize as in "Get with the program!", it programs you by its solution. While in the latter case, it means to write codes for performing calculations. Training in one kind of programming has very little direct relevance to the other. In fact, the term "linear programming" was coined before the word "programming" became closely associated with computer software."2010-10-28

1 Answers 1

4

I'll give you a hint without referring to the representation of the graph:

Given a tree structure of a corporation, you can either have the root (president) attend the party or not. Say the root has n children. If the root is not in the party, you can have a party which is the "sum" of n different parties, each representing the subtree at each of the n children (this is the recursive step). If the root is in the party, then you again have the sum of n different parties, but this time each "subparty" cannot have its root included (this is another recursive step).

You can reformat this recursion into a dynamic programming solution, or solve it recursively with memoization.