More examples.

More Dynamic Programming Examples

Let us begin with the most easily stated integer programming problem, the knapsack problem. Recall that we have n items which have weights w_i and values v_i and wish to select the highest valued collection which does not exceed a weight limit b. Thus we let x_i be the amount of item i we include and

Breaking this down into subproblems follows easily. We load a portion of the knapsack with some of the items. For all values of k £ n and y £ b this is defined as:

So, for values of k between 1 and n and values of y from 1 to b, F_k(y) gives us a partial loaded knapsack. We note that the principle of optimality does indeed apply since an optimum load consists of several optimum subloads.

The next step is to determine the relationship between the F_k(y) values. This is not too difficult to do. Suppose we wish to have y pounds of items 1 through k. Either item k is in the load or not. If not, then the load is the same as the load involving items 1 through k-1, or F_k-1(y). Otherwise we subtract the weight of item k from y and look at that optimum load. This means that

F_k(y) = maximum[ F_k-1(y), F_k(y - w_k)+v_k]

All we need to do now is make a chart of all the F_k(y) values and fill in the chart. Consider the four items whose weights and values are provided in table 1 below.

Table 1 - A Knapsack Problem

From these weights and values let us compute all of the F_k(y) values for this problem. There are no one pound loads so all F_k(1) = 0. The only way to load up two pounds is to use item 1. At y = 3 pounds we begin to have choices since item three is available. When y can be 5, we can use combinations of all the weights to form an optimum load. Table 2 reveals that the optimum seven-pound load is worth 55.

Table 2 - F_k(y) for a Knapsack Problem

Time and space bounds for computing the dynamic programming solution to the knapsack problem are interesting. Since all we need do is fill in a table, we need O(nb) time and space. This sounds pretty good! In fact, this seems to show that the knapsack problem can be solved in quadratic time and space. This is very interesting indeed since no other NP-complete problem is that easy to do. But we have been fooled since the problem size depends on the space taken to write the weights and values, not the weight bound. Thus the problem size is O(nlogb) which makes O(nb) exponential as we suspected. Problems of this type are called pseudopolynomial time problems.

Let us turn now to the closed city tour problem. We have n cities and a matrix A of costs incurred while traveling between them. Thus a_ij is the cost of traveling from city i to city j. For any set of cities S (not including city 1), we let C(S, k) be the minimum cost for traveling from city 1 to city k, going through all of the cities in S once. That is, a tour completely through S beginning with city 1 and ending in city k.

For sets containing one city, this cost is easy to compute. In fact, for all k,

C({k}, k) = a_1k.

For larger sets of cities, we note that some city (say city i) had to precede city k. Thus to go from city 1 through S to city k, we can go from city 1 to city i through the set S - {i} and then go directly to city k. To get the best tour, we simply take the minimum over all cities in S. This is represented by the formula:

which is the recursive relationship between closed tour subproblems.

Again we note that the principle of optimality does apply since any subtour of an optimum tour is itself optimum. So, to solve the traveling salesman problem, we begin with small tours and keep computing subproblems until we find our optimum tour.

Analysis of the traveling salesman problem indicates that there are (n-1)! possible tours. This is in the neighborhood of O(2^nlogn). We did achieve a savings in time since we can do the computations mentioned above in O(n²2ⁿ) steps, but unfortunately we need about O(n2ⁿ) space for storing our table.