reset("0","0","1000","780","Dynamic Programming") # conf.lec \macro(S1,S) \macro(S1b,S) \macro(T1,T) \macro(T1b,T) B2s.hide() S! Dynamic programming is an algorithm design strategy especially - useful for solving - Optimization Problems. S! B2- Optimization Problem: "Find an object x satisfying certain - constraints and such that Cost(x) is minimum over all x satisfying the - constraints." S! Here are some examples. S! B2:: Example 1: Tailor's layout problem. Given a set of - geometric shapes and a seminfinite roll of cloth of some given width - W, place them onto the roll without overlap such that the length L - that must be cut out of the roll to accomodate them should be minimized. B2:: x = layout, Cost(x) = length L that must be cut from the roll. B2:: Example 2: Travelling salesman problem. Given a weighted - graph in which each edge - represents the time required to travel from vertex i to vertex j, find - a permutation of the vertices such that if you travel in the graph - according to the permutation, and return to the vertex you started - with, the total distance covered is minimized. B2:: x = permutation. Cost(x) = Length of entire path indicated by x. S! We next define some commonly used terms. S! B2:: Feasible solutions: All x satisfying the constraints. B2: Optimal solutions: That x satisfying the constraints and - having minimum Cost(x) S! Sometimes Optimization problems will be stated with a function - Benefit(x) which is to be maximized. We could of course define -
    Cost(x) = - Benefit(x)
and use our method here. S:: Our next example, which we will study in detail requires us to maximize benefit. S! B! Knapsack problem: Given a set of n items having values V[1,...,n] and weights W[1,...,n] respectively, and a knapsack having capacity C, find a subset of items whose total weight is at most C and whose total value is maximum over all possible subsets. B:: x = subset of {1,...,n}. Benefit(x) = value of items in x. S! At first glance you might think this problem is easy. "Simply select items in increasing order of value"... B2!

Algorithm attempt 1:
  1. Sort items in non-increasing order of value. Renumber in this order.
  2. S = {}, w=0
  3. for i=1 to n
    \sp if w + W[i] \le C then w = w+ W[i], S = {i} U S.
    end
  4. Return S
S! S! Here is an instance for which this doesnt work. B2- Instance: (10, [10,9,8], [10,5,5]) S! Here capacity C=10, item values V=[10,9,8] and item weights W=[10,5,5]. S:: The algorithm will return the subset S={1} of value 10, while the subset {2,3} has value 17 also achieved without exceeding capacity. S! Another idea might be to sort in non-increasing order of V[i]/W[i]. You should be able to construct examples for which doesnt work either. S! It is a good idea to think of such strategies, however it should be kept in mind that ultimately it is necessary to prove that the strategy will indeed give us the right answer, and not miss out some good solution. S:: So our first goal ought to be: B2:: Goal 1: Correctness Ensure that we report the solution which is the best among all feasible solutions. S! If we actually generate every feasible solution and pick the best, our algorithm will be very slow, though correct. S:: This is because there could be far too many feasible solutions. S! For example, if C is very large, then most subsets could be included in the knapsack. S:: Even if we assume that all subsets with 3n/4 items can be included, there still are essentially 2n such subsets. S:: We would like to spend much less time. So there is another goal too. B2: Goal 2: Speed Algorithm should run fast. We should not ACTUALLY construct all feasible solutions. S! It might seem intriguing how we can devise rule out feasible solutions without actually constructing them. S! Here is the outline of the lecture. B2!

Outline
  • Recursive algrorithm for searching: This will ACTUALLY examine every feasible solution.
  • Improvements: key dynamic programming idea: This will have the effect of examining every feasible solution, but with much less work.
  • Equivalent Non-recursive algorithm
S! \scene(Outline) S! We define a commonly used term first B2! Search space: set of all the feasible solutions. S! Clearly our goal is to find the best solution in the search space. S:: A natural way to organize this search is to partition the search space into subspaces, find the best solution in each subspace, and then take the best of those. B2:: Approach: partition the search space into subspaces, find the best solution in each subspace, and then take the best of those. S:: Our hope is to device a recursive algorithm: presumably we recurse on the subspaces. S! We now try this approach for our knapsack problem. B:: S = space of feasible solutions to instance (C,V[1..n],W[1..n]). S! Perhaps the simplest way to partition this space is as follows. B:: \S1 : Set of those elements of S in which item 1 is present.
\S1b : Set of those elements of S in which item 1 is absent. S! Clearly, if we search both these spaces, take the best of the solution found in each, we will have found the best solution overall. S! Is there some property of \S1 and \S1b that can be help in searching them? S! Let us consider \S1b first. Clearly, every element in \S1b must satisfy the following. B2:: \claim Let x be any element in \S1b. Then x is a subset of items 2,...,n having total weight at most C. B2: \proof Item 1 is not allowed by the definition of \S1b. Since x also belongs to S, it must have total weight at most C. S! So the first observation is: B2:: Every element in \S1b must be a feasible solution to a knapsack instance (C,V[2..n],W[2..n]) S! But the converse is also true. B2: Every feasible solution to the instance (C,V[2..n],W[2..n]) must belong to \S1b. S! The proof is obvious. B2:: \S1b is exactly the set of solutions to instance (C,V[2..n],W[2..n]) S! Thus the highest value element in \S1b must be an optimal solution of the instance (C,V[2..n],W[2..n]) B:: Max value element in \S1b =
\sp optimal solution of (C,V[2..n],W[2..n]). S! Thus \S1b can be searched using recursion. S! Something similar happens for \S1. B: Max value element in \S1 =
\sp {1} U optimal solution to (C-W[1],V[2..n],W[2..n]). S! We will prove this, but note first that this implies that \S1 can also be searched using recursion. B2:: Let \T1 = set of solutions to instance (C-W[1],V[2..n],W[2..n]). B2: For every x \in \S1 let f(x) denote the set y obtained after removing item 1 from x. B2:: \claim For any x \in \S1, y=f(x) \in \T1. B2: \proof By definition of \S1, x must contain item 1. The rest of the items y=f(x) in x must certainly be a subset of 2..n. Since x also belongs to S, its total weight must be at most C. Of this, item 1 has weight W[1]. Hence the rest of the items, i.e. those in set y must contribute at most C - W[1]. Thus y must be feasible for (C-W[1],V[2..n],W[2..n]), and hence must be in \T1. S! The converse is again true. B2: \claim For y \in \T1, x = f-1(y) \in \S1. S! Here f-1(y) is the set obtained by adding item 1 to y. S! The proof is straightforward. S! Thus we have a 1-1 correspondence. B2: f defines a 1-1 correspondence from \S1 to \T1 S! Further x, f(x) only differ in item 1. Thus.. B2:: Total value of x = V[1] + total value of y=f(x) S! So, to maximize the value of x, it suffices to maximize the value of y and add element 1 to it. S:: Thus we have proved- B.H(maxsblue,yellow) B.U(maxsblue) S! So in summary we can write: B:: Optimal solution to (C,V[1..n],W[1..n]) = B: Most valuable( Optimal solution to (C,V[2..n],W[2..n]),
\sp \sp {1} U Optimal solution to (C-W[1],V[2..n],W[2..n])). S! We are almost ready to write down the algorithm, but we need a slight generalization. S! How would this change if we were trying to find a solution to the instance (c,V[i..n],W[i..n])? S:: It should be clear that the equation for this case would be: B:: Optimal solution to (c,V[i..n],W[i..n]) =
Most valuable( Optimal solution to (c,V[i+1..n],W[i+1..n]),
\sp \sp {i} U Optimal solution to (c-W[i],V[i+1..n],W[i+1..n])). S:: We are now ready to write an algorithm. B2! KS(c,i) : will return the subset of maximum value for the instance (c,V[i..n],W[i..n]). The arrays V, W and their length n are global. The initial call is KS(C,1). \scene(Algorithm) B2:: The subset will be represented suitably, say as a linked list. B2:: KS(c,i){ S! First the base case. B2: if i > n then return {} S! We next compute.. B.H(opt1,yellow) B2:: best1 = KS(c,i+1) S! As per the definition of KS, B2.H(KSdef,red) S- KS(c,i+1) will indeed return the solution for the instance (c,V[i+1..n],W[i+1..n]). B2.U(KSdef) B.U(opt1) S! We next compute.. B.H(opt2,green) S! In this, the instance is properly defined only if c - W[i] \ge 0. Else, the corresponding subspace \S1 would be empty. So in that case we should simply return the best solution best1. B2:: if C < W[i] then return best1 B2:
best2 = { i } \union KS(c-W[i],V[i+1..n],W[i+1..n]) B.U(opt2) S! Now we simply need to compare which of the two sets, best1 and best2 has more value. For this we will assume that we are given a procedure valueofset(set-of-indices) picks out the corresponding elements of the array V, and returns their sum. Writing this procedure is an easy exercise for you. S! B2:: if valueofset(best1) > valueofset(best2)
then return best1
else return best2
} S! At this point we have finished the first part: we now have a recursive algorithm for solving the knapsack problem. S:: You should be able to argue correctness by induction on n-i. S! This algorithm is not efficient: as you can show, it will potentially recurse an exponential number of times in n. S: So we now try to optimize it. The key to this optimization is the main dynamic programming idea: check if the recursive calls made by the algorithm overlap. S! Here is now the key observation: B2:: \claim There can be only (C+1) \cdot (n+1) distinct calls to the procedure KS starting with the call KS(C,1), for integer C. B2:: \proof The first argument must always decrease but never go below 0. The second argument can go up to n+1, but not higher than that. S! Note that the value computed by KS is fixed once we fix the arguments to it, since it does not modify any global variables. S:: In other words, if KS is called more than (C+1) \cdot (n+1) times, some of the calls are with the same arguments and work is being repeated. S! So the obvious question is: S-
    Why not store the result of each call in a table, and use it subsequently instead of repeating the call? S:: So we build a table. B!

    Table for storing results from KS \scene(Memoization) S! In the table we could store the entire set returned by KS, however, to keep the subsequent discussion simple, we will only store the total value of the set returned by KS. B- T[c,i] : total value of the set returned by KS(c,i),
    \sp for 0 \le c \le C, 1 \le i \le n. Initially set to null. S! We will write a new procedure KS2 which will use the table before making recursive calls. However, it will also differ from procedure KS in that it will not return the the optimal set but the value of the optimal set. S:: Later on it will become clear that with a slight modification, you will be able to recover the optimal set as well. This is left for the exercises. S! B:: KS2(c,i){
    if i > n then return 0
    S! Remember that now we are returning the value of the set rather than the set itself -- so instead of returning the empty set, we are returning the associated value, 0. S! Next is the first recursive call. Instead of directly recursing we check the table and recurse. B-
    if T[c,i+1] = null
    \sp T[c,i+1] =     KS2(c,i+1)
    vbest1 = T[c,i+1] S! The next part is the same until we again encounter recursion. B:
    if c < W[i] then return vbest1
    S! Again we check and recurse only if needed. B-
    if T[c-W[i],i+1] = null
    \sp T[c-W[i],i+1] =     KS2(c-W[i],V[i+1..n],W[i+1..n])
    vbest2 = V[i] + T[c-W[i],i+1] S! Notice that since we are returning values of the set, we add in the value of element i, rather than include element i into the set as in KS. S! We return the maximum of best1 or best2 B:: return max(vbest1, vbest2)
    } S! It should be clear to you that KS2(c,i) will compute exactly the total value the set that would have been returned by a call KS(c,i).. S:: The table will potentially make KS2 run faster -- we will now quantify this. S! The standard idea for analysing recursive algorithms is to write down a recurrence. This will give a good estimate for the execution time of KS. However, for KS2, we can do something sharper. S! The first observation comes from the claim- B2.H(memo,yellow) B2:: \claim As a part of the call KS2(C,1), there will be only (C+1) \cdot (n+1) calls made recursively. S! This is because using the table KS2 explicitly checks before making a call again with the same arguments. B2.U(memo) S! This claim will help us in analysing the total time taken. S! One idea is to estimate how much time any single call takes. S:: This is not easy to do because the calls are nested inside one another. S:: However, here is a simple idea which will make the counting easy. S! Imagine that each table entry T[c,i] also has a counter attached to it. This counter is purely meant for helping us in the analysis -- in actual runs of the algorithm, no such counters will be present. S:: Call this Counter(c,i). S:: Suppose everytime an instruction executes, it increments the value of the counter associated with current value of c and i. B2:: \claim Counter(c,i) will get incremented to at most T where T is the maximum number of instructions required to execute the non-recursive portion of the procedure KS2. S! Thus T is the time taken for everything show in yellow- B.H("ks2top,ks2mid,ks2bot",yellow) S:: The time might be different depending upon how the "if" conditions turn out. S:: T is simply the maximum over all possible such executions. S! The key question for the proof is why are the recursive calls excluded. B2: \proof Instructions executed in the recursive call KS2(c,i+1) will increment Counter(c,i+1), or some other counter depending upon further recursive calls. B2- Similarly the instructions executed as part of KS2(c-W[i],i+1) will not affect Counter(c,i). B2:: Note further that because of memoization, KS2 is called at most once for any single value of the pair (c,i). Thus Counter(c,i) will increment just once for every instruction shown in yellow. Thus each counter will reach a maximum value of T. S! Now we have an upper bound on the total time. B2:: \claim The call KS2(C,1) requires at most (C+1) \cdot (n+1) \cdot T time. S! All that remains now is to estimate T. Note that the yellow region does not have any loops, and nothing that depends on the problem size n. S:: Thus T = O(1). S:: Total time will thus be O(1) \cdot (C+1) \cdot (n+1) = O(Cn). B.U("ks2top,ks2mid,ks2bot") B:: Time for call KS2(C,1) = O(Cn). S! We have accomplished our main goal. This time will typically be much less than 2n, which is what would be needed to actually examine every feasible solution. S! It will be shown in the exercises that the optimal set can also be obtained in the same amount of time. S! The final topic is to observe that all this can be done without any recursion at all. B2!

    A non-recursive implementation S! The important observation is that our procedure KS2 clearly gives us the relationships between the different entries of the table. S! From this part of the code- B.H(eq1,yellow) S- it follows that- B2- if c < W[i]: T[c,i] = T[c,i+1] B.U(eq1) S! Otherwise, T[c,i] is the larger of vbest1 and vbest2, which are in turn T[c,i] and T[c-W[i],i+1]. B2: if c \ge W[i]: T[c,i] = max(T[c,i+1], V[i] + T[c-W[i],i+1]) S! The base case of the recursion, i > n returns 0. Thus we might write-- B2:: for all n: T[c, n+1] = 0 S! Notice that this is consistent with the interpretation that T[c,n+1] is the value of the set returned by the call KS(c,n+1) -- which indeed returns the null set having value 0. S! So all we need to do is to solve this recurrence. S:: It will be seen that all table entries can be calculated in decreasing order of the second index as per the following program: B2:: Program:

    for c=1 to C
    \sp T[c,n+1] = 0
    for i=n to 1
    \sp for c=1 to C
    \sp \sp if c < W[i] then T[c,i] = T[c,i+1]
    \sp \sp else T[c,i] = max(T[c,i+1], V[i] + T[c-W[i],i+1]) S! It should be clear that T as calculated above will satisfy the recurrence. S:: T[C,1] gives the optimal value for our original instance (C,V[1..n],W[1..n]). B2: return T[C,1] S! The time taken is seen to be O(Cn) exactly the same as the recursive version. However, this version might be considered to be more direct. B2:: Time = O(Cn) S! B! B2! S! We finally summarize the dynamic programming approach and highlight its main features. B! How to design a dynamic programming algorithm for an instance X of a problem P:
    1. Clearly define the space S of feasible solutions, and the objective function, i.e. what is to be maximized on minimized.
    2. Partition S into subspaces S1,...,Sk. This is typically done by considering all possible ways (k) in which the candidate solutions can start.
    3. Design an algorithm to find an optimal solution si in each Si. This should mainly involve solving smaller size instances Xi' of problem P.
    4. Using the algorithms designed above write a procedure which will
      1. Find si for i=1..k
      2. Return s = most optimal of all si.
    5. Check if the (recursive) procedure defined above will make several calls with the same arguments, if so store previously computed results in a table. This is often called MEMOIZATION.
    6. ALTERNATE PROGRAM: Identify a recurrence relating the table entries. Write a program to solve the recurrence.
    \scene(Summary of Dynamic Programming) B2!

    Exercises:
    1. Show that procedure KS will recurse at least as many times as the number of feasible solutions.
    2. Modify the basic recursive procedure given, KS, so that it prints the cost of every feasible solution in the search space. Hint: add an extra argument giving the value accumulated in the first i-1 elements.
    3. Show how to modify KS2 to compute the optimal set, and not just the value of the optimal set. Hint: Check whether T[c,i] is equal to T[c,i+1] or not. This will tell you whether element i should be in the set, and also what the subsequent elements in the set will be.
    \scene(End)