A Weightier Example
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
