Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

C/C++

C++ Hash Table Memoization: Simplifying Dynamic Programming


A Weightier Example

More Insights

White Papers

More >>

Reports

More >>

Webcasts

More >>

Demonstrating the value of a technique with a problem like Fibonacci numbers can be less than convincing -- it's pretty easy to devise reasonable solutions to the problems in an ad hoc manner.

For a more substantial example, I've slightly revised a problem from Thomas Cormen et al.'s Introduction to Algorithms (Cambridge: MIT Press, 2001):

"

Before leaving Microsoft to work full-time on philanthropic ventures, Bill Gates has one problem left to solve: his employees are overweight. After a company health fair with a mandatory weigh-in, Bill had HR prepare a standard org chart which includes the number of extra pounds each employee is carrying around.

Bill decides the best approach to the problem is to create a regular exercise class for his overweight employees. But with a twist -- he decides that he doesn't want any employee to be in a class with his or her direct superior, so as to avoid any hint at coercion.

Your task is to take that org chart, plus Bill's no-supervisor constraint, and invite as many employees as you can, maximizing the total excess weight in the class."

A sample version of the org chart is in Figure 2. Keep in mind that this sample is fairly small, but Bill's chart will normally have almost 80,000 employees.

Figure 2: The Excess Weight Org Chart

The employee names are not too imaginative, but you can see that employee a is carrying 1 extra pound, employee b 2, and so on.

Because of the constraints on the problem, we know we can't invite all employees. We need to decide who to invite, but still obey the rule that no employees are there with their supervisors.

This problem is very amenable to a conventional recursive solution. To determine the maximum weight that can be achieved at a given node, we can use something like the pseudocode shown here:

GET-MAX-WEIGHT( node ) 
  if node.number_of_children is 0 
    return node.weight; 
  weight1 = 0; 
  for i = 1 to node.number_of_children 
    weight1 = weight1 + GET-MAX-WEIGHT( node.child[ i ] ); 
  weight2 = node.weight; 
  for i = 1 to node.number_of_children 
   for j = 1 to node.child[ i ].number_of_children 
    weight2 = weight2 + GET-MAX-WEIGHT( node.child[ i ].child[ j ] ) 
return max( weight1, weight2 ) 

The logic is straightforward. At each node we calculate two possible values for the maximum weight. The first value, weight1, defines the maximum weight if the node does not attend. Since the node is not attending, the weight will consist of the sum of all that node's immediate children.

The second value, weight2, is used to calculate the maximum value of the node when the node does attend. Since the node is attending, none of its immediate children can attend, which means the total weight will be the sum of the node's weight, plus the max of all of its children's children.

You can immediately see that this algorithm shares a characteristic with the Fibonacci algorithm. When evaluating a node, we make recursive calls at two different depths in the calling tree, and this results in overlapping subproblem evaluation. For example, when implementing this pseudo codeon the organizational chart in Figure 2, the list of nodes passed in to GET-MAX-WEIGHT will be:

Table 1: The Excess Weight Org Chart

You'll note that there are 17 nodes, but because of duplicates, we call GET-MAX-WEIGHT 31 times, leading to much extra work. And that level of work gets into the seriously excessive levels when faced with the entire Microsoft 80,000 person organizational chart.

So naturally, Dynamic Programming comes to the rescue. It turns out that this particular problem fits into the category well. We have overlapping subproblems, we have optimal substructure, so we can employ DP. u


Related Reading






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.