In this section, we will describe the dynamic-programming solutions of three additional examples. These are given at the links below.

Example 1: The Knapsack Problem

Example 2: The Project-Planning Problem

Example 3: The Production-Planning Problem, Revisited

The discussions at the above links refer to two figures. To view these figures, click on the following titles: Figure DP-6, Figure DP-7.

Finally, we conclude our discussion of dynamic programming with a few comments.

In all of our examples, the recursions proceed from the last stage toward the first stage. This approach is called backward dynamic programming. Clearly, by symmetry, we could also have worked from the first stage toward the last stage; such recursions are called forward dynamic programming. In general, one can adopt either of these two approaches to solve a problem. There is, however, a difference in the "by-products" produced by these two methods: In solving a problem by backward DP, we will obtain as by-products the optimal values from every state in every stage to the end; whereas in solving a problem by forward DP, the corresponding by-products would be the optimal values from the initial state(s) in the first stage to every state in the remaining stages.

In the course of solving a problem by dynamic programming, we are in fact going through a complete evaluation of all possible sequences of decisions. Despite the fact that a significant reduction of redundancy is achieved with the use of recurrence relations, the total amount of required computational effort typically grows very rapidly as a function of problem size. In fact, for large problems, the computational burden can be such that it is virtually impossible to obtain an optimal solution within a reasonable amount of time. This limitation on the use of dynamic programming is commonly referred to as the curse of dimensionality.

For additional realism, it is also possible to formulate dynamic programs where the outcome of an action is random. Such problems are called stochastic dynamic programs. Specific examples can be found in Section 11.4 of the text.

Assignment No. 7

Chapter 11: 11.2-3, 11.2-4, 11.3-2, 11.3-3, and one of 11.3-6 and 11.3-10.

The diagram shown in Exercise 11.2-3 is called a precedence diagram, in that it describes the precedence relationship between different activities in a project. A description of such networks can be found on page 471 of the text.