CMSC 435  Algorithm Analysis & Design

 

Dynamic Programming

 

Consider the following algorithm:

 

long int fibonacci(int n) {

    if (n == 0)

          return 0;

    if (n == 1)

          return 1;

    return fibonacci(n-1) + fibonacci(n-2);

}

 

This algorithm has the recurrence relation

 

     T(n) = T(n-1) + T(n-2)

 

which we have previously seen yields  T(n) = Q(((1+Ö5)/2)n)

 

A non-recursive fibonacci algorithm:

 

            long int fibon(int n) {

                long int fib;

    if (n == 0)

          return 0;

    if (n == 1)

          return 1;

                int last = 1, prev = 0;

                for (int i = 1; i <= n; i++) {

                      fib = last + prev;

                      prev = last;

                      last = fib;

                }

                return fib;

            }

 

This non-recursive algorithm is clearly linear in n ( T(n) = Q(n)) as the for-loop executes a constant number of statements n times.

 

Why does the recursive algorithm behave so badly?

 

Because it must recompute the same results numerous times.  It is an example of a problem with overlapping sub-problems for which a recursive approach yields disasterous performance.  Algorithms with these characteristics may be described as senile, because the same calculation is made and repeatedly forgotten necessitating the same computation to be performed numerous times.  The performance of these algorithms can be substantially improved, however, the way the performance of the fibonacci algorithm was improved--by keeping a table of previously learned values.

 

Example 2  The Exact-fit knapsack problem

 

Assume we have a knapsack of size K and a collection of n items where the jth item in this set has a size sj.  Is there some subset of these n items that will exactly fill the knapsack?

 

To solve this problem, state the solution in terms of the solution to the problem of filling a knapsack from the set of the first n - 1 items.

 

There is a solution to the knapsack problem of exactly filling a sack of size K with a subset of n items if:

 

1.  A knapsack of size K can be filled from among the first n-1 items.  (just leave the nth

       item out.

2.  A knapsack of size K - sn can be exactly filled by a selection of the first n-1 items. 

     Then this collection plus the nth item will exactly fill a knapsack of size K.

 

If we let P(n, K) be the statement that there exists a subset of the n items that exactly fills a knapsack of size K.  This statement is either true or false.  To determine which, we can formulate a recursive solution:

 

            P(n, K) = P(n-1, K) OR P(n-1, K - sn)

 

The statement written symbolically as P(n, K) is true if either of the other two statements is true.

 

            We know that P(0, k) is false for all n: 0 < k  £ K

            and P(0, 0) = true (the empty set can exactly fit a knapsack of size 0).  {base case} 

 

Therefore we can write a recursive algorithm to solve this question:

 

            bool  P(int S[], int n, int K) {

                  //where S is an array of (integer) sizes of the individual items, n is the number of items in the set,

                  //and K is the size of the knapsack

                  if ((n == 0) && (K > 0))

                        return FALSE;

                  if ((n == 0) && (K == 0))

                        return TRUE;

                  if ((P(S, n-1, K) ||(((K - S[n]) >= 0) && (P(S, n-1, K - S[n]))))

                              return TRUE;

                  else

                        return FALSE;

            }

 

The performance of this algorithm is exponential, as the algorithm suffers from acute senility.  It is clearly a case in which the overlapping subproblems will have to be solved anew repeatedly. 

 

Now consider a dynamic programming approach:

 

There can be as many as nK subproblems that need to be solved in order to determine if a solution to the statement of the exact-fit knapsack problem exists.  Our approach will be to construct a matrix  with (n+1) rows and (K + 1) columns with a cell in the i,jth position of this matrix representing the solution to the problem of a knapsack of size j choosing from among the first i items to be placed in it.  Each cell will have two boolean fields:  and exists field to show if a solution exists to this subproblem, and a belongs field to indicate whether the ith item is part of the solution set.  The first row of our matrix will correspond to n = 0.  The items to put into the knapsack form the empty set.  All of the entries in the first row, therefore, are FALSE for both fields, except the P[0][0] entry for which the exists field is set to TRUE -- there is no exact-fit solution to a knapsack of size > 0 that is left empty, but a knapsack of size 0 is filled with no items in it.

 

ExactFitKnapsack

                       

One proceeds filling in the cell values from left to right and from top to bottom.  To fill the cell marked i, j in the diagram above, one has to examine the contents of the two previously filled cells marked x1 and x2. 

 

If a solution to the cell marked x1 exists, then a knapsack of size j has an exact fit solution from among the previous i -1 items and a solution to the problem of P(S,i,j) also exists (by leaving the ith item out), and

 

                        P[i][j].exists = TRUE              P[i][j].belongs = FALSE

 

If no solution has been found for the cell labeled x1, one next examines the cell labeled x2.  This cell corresponds to a knapsack of size j - S[i] and a subset of the previous i - 1 items.  One first has to determine is such a knapsack exists size     ((j - S[i]) ³ 0), then check P[i-1][K-S[i]].belongs.  If both conditions are true then a solution to the problem of P(S,i,j) exists by adding the ith element with the contents of the previous knapsack.

 

                        P[i][j].exists = TRUE and      P[i][j].belongs = TRUE

 

Putting this together, we can write the dynamic programming algorithm for the exact-fit knapsack problem.

 

            bool  P(int S[], int n, int K) {

                  struct  cell {

                        bool  exists;

                        bool belongs;

                  }

                  cell M[n+1][K+1];

                  //initialize the matrix M

                  for (int i = 0; i <= K; i++)  {

                        M[0][i].exists = FALSE;

                        M[0][i].belongs = FALSE;

                  }

                  M[0][0].exists = TRUE;

                  //now traverse from top to bottom and left to right filling in the value for the i, jth cell as we traverse

                  for (int i = 1; i <= n; i++)

                        for (int j = 0; j <= K; j++)  {

                               M[i][j].exists = M[i] [j].belongs = FALSE;          //default initialization

                               if (M[i-1][j].exists)

                                    M[i][j].exists = TRUE;                                                //solution exists that does not include ith item

                               if (((j - S[i]) >= 0) && M[i-1][j-S[i]].exists) {

                                    M[i][j].exists = TRUE;

                                    M[i][j].belongs = TRUE;

                               }

                        }

                  // filling in table entries now complete

                  return M[n][K].exists;

            }

 

The algorithm for retrieving the solution set proceeds as follows -- {we must redefine the matrix M so that it is not local to a single function}

 

            Start at  i = n, j = K -- the last cell in the table

            while (i != 0 ) //while you have not yet reached the top row

                  while (!M[i][j].belongs)

                        i--;        //move up the table

                  if (i != 0)  add item i, with size S[i] to the solution set.

                  if (j >= S[i])

                        j -= S[i];  //slide over to the left

                        i--;

            }

 

ExactFitKnapsackRetrieval