CS 383, Algorithms
Dynamic Programming


Dynamic Programming

A powerful design technique Objective is to avoid redundant processing of subproblems

Example: n choose k

Useful for many problems involving independent events, like counting equipment failures over time Question: what is the number of different k-member teams that can be formed among n potential players?

Straightforward recursive solution:

Based on the following recurrence relation for (n,k) = "n choose k": (n,k) = (n-1, k-1) + (n-1, k) we can write the following recursive algorithm to compute (n,k): nChooseK(n, k) { if (k = 0 or k = n) return 1 else return nChooseK(n-1, k-1) + nChooseK(n-1, k) }

Running time for the straight recursive version

We drew the recursion tree in class Depth of tree is n (not uniformly, just the longest branches) Branching factor is 2 Size could be the order 2^n - very slow! (we can do a more precise analysis as in HW1, and determine that the size is indeed exponential in n, but with a base slightly less than 2)

Source of the inefficiency of the straight recursive solution

Problem is that there are many repeated invocations of nChooseK For example, in order to compute nChooseK(5,3), we recurse as follows: nChooseK(4,2) nChooseK(4,3) nChooseK(3,1) nChooseK(3,2) nChooseK(3,2) nChooseK(3,3) Already at this level, the invocation nChooseK(3,2) occurs twice The redundancy gets worse as you get deeper into the recursion tree We're not being smart about the order in which the invocations are carried out

The dynamic programming approach

Draw the (n,k) plane The value of nChooseK(n,k) depends on the values of nChooseK at points within a limited (cone-shaped in this case) "domain of dependence" Compute the values within the domain of dependence in a smart order Initialize the values along the boundaries: nChooseK(i, 0) = 1 for all i between 0 and n nChooseK(j, j) = 1 for all j between 0 and n Scan the domain of dependence along paths such that any necessary quantities will be available before they are needed: for i=1 to n for j=1 to k-(n-i) nChooseK(i,j) = nCK(i-1,j-1) + nCK(i-1,j)

Exercise

Compute nChooseK(5,3) following the above dynamic programming approach

Running time of the dynamic programming solution

Initialization takes time Theta(n) Updating takes time Theta(n^2) Total time is Theta(n^2) Much, much better than 2^n !

Summary so far: Dynamic Programming

A powerful design technique Improves on divide and conquer by avoiding redundant processing of subproblems that may occur in a direct divide and conquer approach We studied the computation of n choose k as an example

Basic steps required for a Dynamic Programming solution

Cast the task as optimization of some specific objective function over a hierarchy of subproblems of increasing size Write down a recurrence relation for the optimized objective function Determine the domain of dependence of each point Determine the initial conditions at the boundary of the domain Scan the domain in a smart order so that necessary quantities will be available when they are needed to update the objective values

Making change

Recall the task of "making change", that is, breaking down a given quantity as a sum of "tokens" of predetermined "denominations" We cast this as an optimization task One seeks a solution (bag of tokens with a certain total value) that is minimal relative to the given objective function (number of tokens) We saw that a greedy approach doesn't always produce optimal solutions I'll illustrate how to use dynamic programming for this task

Expressing the objective function

The objective function is the function to be optimized For making change, we wish to minimize the total number of tokens Choosing the right variables helps a lot Order the denominations from smallest to largest Choose i = highest denomination to be used (i=1,2,3,...) j = amount to be decomposed in terms of token values c(i,j) = minimum number of tokens needed for total amount j if only token types 1..i are used

Towards a recurrence relation for making change

For dynamic programming to work, one needs a recurrence relation for the optimized objective function Now analyze what the optimal way to make change is if denominations 1...i are allowed ( as opposed to just 1...i-1): Case 1. You don't use any tokens ("coins") of the largest denomination: then the optimal number of tokens is just c(i-1,j) Case 2. You do use tokens of the largest denomination d(i): then the optimal number of tokens is 1 + c(i,j-d(i)) *notice that the right-hand side allows d(i) to be used again* The minimum number of tokens is the best you can do across both cases The recurrence relation is therefore: c(i,j) = min( c(i-1,j), 1 + c(i,j-d(i)) )

Dynamic programming solution

Draw diagram of (i,j) plane Boundary cases are c[i,0] = 0 for i>=1 c[i,<0] = infinity for i>=1 c[0,j] = infinity for j>=1 Domain of dependence for (i,j) is contained in rectangle Scan by rows, from left to right

Pseudocode

coins(N) { for i = 1 to n=# of denominations { c[i,0] = 0 for j = -1 downto d[n] { c[i,j] = infinity } } for j = 1 to N=target quantity { c[0,j] = infinity } for i = 1 to n { for j = 1 to N { c[i,j] = min( c[i-1,j], 1 + c[i,j-d[i]] ) } } }

Recovering the optimal token bag for a given quantity

Given target c[n, q], construct the optimal token bag as follows: Run coins algorithm to fill in table Compare c[n,q] with c[n-1,q]; if they're the same, then no n-tokens should be used, and one should restart at c[n-1,q]; otherwise, put one n-token in the bag and recur on c[n,q-d[n]] Continue as above until c[0,0] is reached

Analysis

Running time is O(number of cells examined) = O(n*N)

Knapsack problem ("0/1 version")

Given: n objects, where object i has weight wi and value vi (both positive), and a knapsack with a weight capacity W Objective: select some of the objects to fill the knapsack so as to maximize the total value, without violating the weight constraint

Greediness fails for the 0/1 knapsack problem

Two possible greedy heuristics: * maximize value without regard for weight: pack most valuable objects first * maximize value per unit weight pack objects in decreasing order of value/weight ratio

Examples

W=100; v1=100, w1=80 (v1/w1=1.25) v2=90, w2=50 (v2/w2=1.80) v3=80, w3=50 (v3/w3=1.60) Here, greedy by value chooses object 1 and stops; total value=100 Greedy by value/weight chooses objects 2, 3; total value=170 (optimal) W=100; v1=100, w1=80 (v1/w1=1.25) v2=130, w2=65 (v2/w2=2.0) v3=80, w3=50 (v3/w3=1.60) v4=90, w4=50 (v4/w4=1.80) Here, greedy by value chooses object 2 and stops; total value=130 Greedy by value/weight chooses object 2 also; total value=130 Optimal solution is to chopose objects 3, 4; total value=170

Side remark: greedy by value/weight actually works for the "fractional" version of the knapsack problem

If you can split objects into pieces without loss of value, then it's best to pack in decreasing order of value/weight

Dynamic programming approach to the 0/1 knapsack problem

As usual, first cast as an optimization problem: Let xi=1 if object i is packed, xi=0 otherwise Maximize sum of xi*vi subject to the constraint that sum of xi*wi <= W Next, write a recurrence relation for the objective function: Let V(I, W) = maximum total value for weight limit W, using only objects indexed by I or less Then since object I is either in the optimal packing or not, and since there is only one copy of object I (unlike making change): V(I, W) = max( V(I-1, W), vI + V(I-1, W-wI) ) Boundary values: V(1,W) = 0 if w1 > W; V(1,W) = v1 if w1 <= W V(I,0) = 0; V(I,<0) = -infinity

Example

We'll discuss the following example in class (W=100) weight limit: 0 10 20 30 40 50 60 70 80 90 100 v1=100, w1=80 0 0 0 0 0 0 0 0 100 100 100 v2=130, w2=60 0 0 0 0 0 0 130 130 130 130 130 v3=80, w3=50 0 0 0 0 0 80 130 130 130 130 130 v4=90, w4=50 0 0 0 0 0 90 130 130 130 130 170