Lecture 9/25/97 1 handout: assn 3 o dynamic programming - knapsack o memoizing Dynamic Programming ------------------- Talk about an algorithmic technique: called "dynamic programming", also related to technique called "memoizing" I'll talk about too. -- often treated as "advanced" technique, but it's one of my favorite techniques so I want to talk about it now. DP is a method for dealing with problems where you have to make a sequence of decisions, and the idea is to set up the problem so you can build up partial solutions in a systematic way to get your final solution. (The name DP is a little funny: not especially dynamic, or really have much to do with programming in current sense of word.) An example: Knapsack Problem Imagine you have a homework assignment with different parts A,B,C,D,E,F,G. Each part has a "value" (in points) and a "time" (in hours) to do. EG: A B C D E F G value: 7 9 5 12 14 6 12 time: 3 4 2 6 7 3 5 You have: 15 hours. Which parts should you do? What's the best total value possible? (Assume no partial credit on parts) (A: 34 -- ABFG) This is called the "knapsack problem". Think of like this: have a knapsack of some total size. Items of different values and sizes. Want to pack in as much value as can fit. In computing-related applications, this can come up when you want to schedule tasks that each have different priorities. Q: how can we figure out the maximum value to get for our fixed time or size amount? Will call these parts "items". Items A,B,C,D.. - each with value,time. SIMPLE APPROACH: How about trying all subsets of items, and for each one seeing if it's legal, and then just taking the maximum value over all legal ones. What is the running time for this? Answer: O(2^n) This is exponential. Scales very badly with n. To do better, we'll use DP. DYNAMIC PROGRAMMING ------------------- IDEA: 1. For every #hours 0,1,...,15, (our maxiumum) will figure out the max value for that amount of time, not just for 15. I.e., figure our MORE, but this will actually make our life EASIER. 2. Do in "steps". Step 1 suppose only had item A, step 2 had items A and B, step 3 had A,B,C. General idea: figure out result for step i based on previous results. Here's how we can apply these ideas. Make a big 2-D array "varr" (for "value-array"). Idea use varr[i][t] to hold maximum value we can get if we're willing to spend t hours, using only items 1,.., i. [These are the subproblems] varr: t (time) # hours 0 1 2 3 4 5 6 7 8 9 15 +------------------------------------------------------ step:0| 0........... |------------------------------------------------------ 1| 0 0 0 7 7 7 7 7 7 7 ..........7 A only (7-3) |------------------------------------------------------ 2| 0 0 0 7 9 9 9 16 16 .............16 A and B (9-4) |------------------------------------------------------ 3| 0 0 5 7 9 12 14 16 16 21..........21 A, B, C (5-2) |------------------------------------------------------ 4| 0 0 5 7 9 12 14 16 17 21 (12-6) Varr has size at least (number of steps) x (max time + 1) Just for simplicity, say we have a "step 0" where use 0 items, so step number equals the number of items we're using. #steps = #items+1. Start: step 0, all 0s. can't get any points without doing any problems. Step 1: only considering problem A. Can't do anything for 0,1,2 hours, but for 3 or more hours, can get 7 points, so fill in 7s. What about Step 2: here can use A or B. What does this look like? Step 3: Use A or B or C. Now, what does this look like? The big question: what's the general rule? How do we figure out the next row? varr[i][t] = MAX( varr[i-1][t], <-- i.e. don't use item/problem i varr[i-1][t - time[i]] + value[i]) <-- i.e. do use it. where say we have loaded times and values into arrays TIME and VALUE. Can easily turn this into C code. Say have big enough 2-D array varr, and arrays TIME and VALUE. (say use 1,2,...,num_items). Say have function "max" defined, just do: for(t=0; t <=max_time; ++t) varr[0][t] = 0; for(i=1; i <= num_items; ++i) { for(t=0; t < time[i]; ++t) varr[i][t] = varr[i-1][t]; for(t=time[i]; t <= max_time; ++t) { varr[i][t] = MAX( varr[i-1][t], varr[i-1][t - time[i]] + value[i]); } } How do you read off max value? --> varr[num_items][max_time] harder: how can you then find which problems you were supposed to do? A: See whether varr[i][t] equals first case or second. If first, then you shouldn't include the ith problem, otherwise you should. If tie, then it doesn't matter. EG: let's do step 4..... problems A,B,C,D. Say had 9 hours: which should do? Don't do D, do C, do B, do A. 8 hours: Do D,C, not B or A. What is running time in terms of N = number of items, and M = max time (i.e., M = size-of-knapsack)? Answer: Theta(n^2). -------------------------- Order notation review Say T(n) is running time on problem of size n. To review: T(n) = O( n^2 ) means: as n gets large, T(n) is AT MOST proportional to n^2. some c>0 so that T(n) <= c*n^2 = Omega(n^2) means:as n gets large, T(n) is AT LEAST proportional to n^2. some c>0 so that T(n) >= c*n^2 = THETA(n^2) means: as n gets large, T(n) IS proportional to n^2. some c1,c2 > 0 so that c1*n^2 < T(n) < c2*n^2. Examples: 2n^3 + 2n + 1 is O(n^3)? O(n^2)? O(2^n)? Omega(n^3)? -------------------------- General idea: find a way to break problem down into "steps" or "levels". Actual problem at "step" or "level" N. Want to be able to calculate result at level i based on results at previous levels. This DP approach is very similar to a method of speeding up recursion called "memoizing". Use simpler example than these: "fib". Here's a way to do fib that's like above: array fib[N]: step i, compute fib[i] based on previous fibs. start: fib[0] = fib[1] = 1; for(current=2; current <= N; ++current) fib[current] = fib[current-1] + fib[current-2]; --> linear time. Can contrast with the "slow recursive program" fib(int n) { if (n <= 1) return 1; else return fib(n-1) + fib(n-2); } --> exponential time -- reason: recomputes a lot of things many times. --> E.g., look at fib(4) tree. One way to do recursively, but improve time is to store results in array, and only call recursively if haven't done it yet. say have array fibarr[] initialized to all zeros. fib(int n) { if (n <= 1) return 1; if (fibarr[n] != 0) return fibarr[n]; else fibarr[n] = fib(n-1) + fib(n-2); return fibarr[n]; } In a sense, like a "top-down" version of dynamic programming. -- Can Do knapsack too. Instead of doing first level, then second, etc., can start at end, and do recursion, but store results so have same running time. Sometimes, this "recursion with memos" is easier to do than the DP "bottom up" approach. Later on, we'll see an example of this when we build a game-playing program.