Dynamic Programming
Dynamic programming is a problem solving paradigm most often used to solve problems which require some measure of maximization or minimization.
Divide-and-Conquer is a paradigm that recursively solves problems whose solution can be found in terms of smaller instances of itself. With Divide-and-Conquer, it is inevitable that some sub-problem is solved more than once (in fact, many times). The purpose of dynamic programming is to eliminate this duplication.
The Divide-and-Conquer paradigm is a top-down technique. We start with the problem we wish to solve and express its solution in terms of smaller instances of the same problem. For example, when computing XY we determine if Y is even or odd then we rewrite the original problem in terms of smaller exponentiations. On the other hand, Dynamic Programming is a bottom-up method, we start from simple solutions of similar problems and build to the solution of the problem we trying to solve. We save the results in a table.
Example: Computing Binomial Coefficients
Divide-and-Conquer
C(n-1,k-1) + C(n-1,k), 0 < k < n
C(n,k) =
1, when k=0 or k=n
Compute Binomial Coeficient - C(n,k)
Enter n: 9
Enter k: 4
n/k 0 1 2 3 4
------
0| 1 0 0 0 0
1| 1 1 0 0 0
2| 1 2 1 0 0
3| 1 3 3 1 0
4| 1 4 6 4 1
5| 1 5 10 10 5
6| 1 6 15 20 15
7| 1 7 21 35 35
8| 1 8 28 56 70
9| 1 9 36 84 126
Dynamic Programming
C(9,4) = 126
<Clock: 0.0 seconds>
Divide and Conquer
C(9,4) = 126
<Clock: 0.0 seconds>
Compute Binomial Coeficient - C(n,k)
Enter n: 35
Enter k: 18
Dynamic Programming
C(35,18) = 4537567650
<Clock: 0.0 seconds>
Divide and Conquer
C(35,18) = 4537567650
<Clock: 83.61 seconds>
The execution tree for C(5,2) is shown below:
Dynamic Programming problems typically satisfy the following characteristics:
1. The problem can be divided into separate steps.
2. The cost value increases steadily as we go through the steps.
3. The cost value at any step depends only on the cost value of the steps encountered so far plus the cost of the current step.
4. Principle of Optimality (POO):
If the solution after n steps is optimal then that portion of the solution up through step i, i£n is also optimal.
Example: Knapsack Problem
Given a knapsack with capacity c (integer) and n objects where w[i] and v[i] denote the weight (integer) and value of object i. Problem: Maximize the value of the items placed in the knapsack such that the sum of the weights of the items placed in the knapsack £ capacity c.
Brute-force:
for every subset of n items{
if the subset fits in the knapsack, record its value
}
Select the subset that fits with the largest value
Enter number of items: 5
Enter the capacity of knapsack: 12
Enter weight of item 1: 3
Enter value of item 1: 4
Enter weight of item 2: 6
Enter value of item 2: 5
Enter weight of item 3: 1
Enter value of item 3: 2
Enter weight of item 4: 7
Enter value of item 4: 6
Enter weight of item 5: 8
Enter value of item 5: 5
i: 1 2 3 4 5
wgt: 3 6 1 7 8
val: 4 5 2 6 5
Subset Value Weight
{1} 4 3
{2} 5 6
{3} 2 1
{4} 6 7
{5} 5 8
{1,2} 9 9
{1,3} 6 4
{1,4} 10 10
{1,5} 9 11
{2,3} 7 7
{3,4} 8 8
{3,5} 7 9
{1,2,3} 11 10
{1,3,4} 12 11
{1,3,5} 11 12 Q(2n) runtime!
for each item i{
consider knapsacks of every capacity j £ c{
if the ith item fits in the knapsack of capacity j the remaining
capacity is j – w[i]. To fill the remaining capacity, POO says to
consider the value of the optimum packing of items 1 through i-1
for a knapsack of capacity j – w[i] (already computed, call
it x). If x + v[i] > the value of the optimum packing of items 1
through i-1 for a knapsack of capacity j (already computed, call
it y), update the value of the optimum packing of items 1 through
i for a knapsack of capacity j to be x + v[i]; otherwise, set the
value of the optimum packing of items 1 through i for a knapsack
of capacity j to y.
}
}
i\cap 0 1 2 3 4 5 6 7 8 9 10 11 12=c
------
0| 0 0 0 0 0 0 0 0 0 0 0 0 0
1| 0 0 0 4 4 4 4 4 4 4 4 4 4
2| 0 0 0 4 4 4 5 5 5 9 9 9 9
3| 0 2 2 4 6 6 6 7 7 9 11 11 11
4| 0 2 2 4 6 6 6 7 8 9 11 12 12
5| 0 2 2 4 6 6 6 7 8 9 11 12 12
Packed 4 3 1
Total weight = 11; Value = 12
for(int i=1; i<=n; i++)
for(int j=1; j<=c; j++){
f[i][j] = f[i-1][j];
if(j - w[i] >= 0){
p = f[i-1][j-w[i]] + v[i]; //p = x + v[i]
if(p > f[i-1][j]) //if(p > y) …
f[i][j] = p; //Q(nc) runtime!
}
}
Example: Chained Matrix Product
Determine the most efficient way to perform A A ... A
1 2 n
Let A be a p-by-q matrix and B be a q-by-r matrix then A*B is a p-by-r matrix
q
__
\
A*B[i,j] = / A[i,k] B[k,j] where 1<=i<=p and 1<=j<=r
--
k=1
Complexity of A*B - since A*B has p*r entries and each of these entries takes q to compute. The complexity is Theta(p*q*r).
------
Compute the number of multiplications required to compute A*B*C
------
Since matrix multiplication is associative A*B*C = A*(B*C) = (A*B)*C.
Let A be a p-by-q matrix and B be a q-by-r matrix and C be an r-by-s matrix.
mult[(A*B)*C] = pqr + prs
mult[A*(B*C)] = qrs + pqs
Let p=5, q=4, r=6, and s=2 then
mult[(A*B)*C] = pqr + prs = 5(4)(6) + 5(6)(2) = 120 + 60 = 180
mult[A*(B*C)] = qrs + pqs = 4(6)(2) + 5(4)(2) = 48 + 40 = 88
This result says we should be concerned about which parenthesization we used.
------
Let A have dimension p -by- p where 1<=i<=n.
i i-1 i
Dynamic Programming
======
For each pair 1<=i<=j<=n determine the multiplication sequence
A = A * A * ... * A that minimizes the number of
i..j i i+1 j
multiplications.
Note A is a p -by- p
i..j i-1 j
Problem: minimize the number of multiplications for A
1..n
Example: Chained Matrix Product
Enter number of matrices: 4
Enter dimension 1: 5
Enter dimension 2: 4
Enter dimension 3: 6
Enter dimension 4: 2
Enter dimension 5: 7
A1 is an 5x4 matrix
A2 is an 4x6 matrix
A3 is an 6x2 matrix
A4 is an 2x7 matrix
m[1][2] = min{120}
m[2][3] = min{48}
m[3][4] = min{84}
m[1][3] = min{88, 180}
m[2][4] = min{252, 104}
m[1][4] = min{244, 414, 158}
Matrix m:
1 2 3 4
------
1| 0 120 88 158
2| 0 0 48 104
3| 0 0 0 84
4| 0 0 0 0
Matrix s:
1 2 3 4
------
1| 0 1 1 3
2| 0 0 2 3
3| 0 0 0 3
4| 0 0 0 0
Optimal Product = ((A1*(A2*A3))*A4)