UC Berkeley—CS 170: Efficient Algorithms and Intractable Problems Handout 16Lecturer: Michael Jordan November 2, 2005Notes 16 for CS 1701 Chain Matrix MultiplicationSuppose that you want to multiply four matrices A × B × C × D of dimensions 40 × 20,20 × 300, 300 × 10, and 10 × 100, respectively. Multiplying an m × n matrix by an n × pmatrix takes mnp multiplications (a good enough estimate of the running time).To multiply these matrices as (((A×B)×C)×D) takes 40·20·300+40·300·10+40·10·100 =380, 000. A more clever way would be to multiply them as (A × ((B × C) × D)), with totalcost 20 · 300 · 10 + 20 · 10 · 100 + 40 · 20 · 100 = 160, 000. An even better order would be((A × (B × C)) × D) with total cost 20 · 300 · 10 + 40 · 20 · 10 + 40 · 10 · 100 = 108, 000. Amongthe five possible orders (the five possible binary trees with four leaves) this latter methodis the best.How can we automatically pick the best among all possible orders for multiplying ngiven matrices? Exhaustively examining all binary trees is impractical: There are C(n) =1n2n−2n−1≈4nn√nsuch trees (C(n) is called the Catalan number of n). Naturally enough,dynamic programming is the answer.Suppose that the matrices are A1× A2× · · · × An, with dimensions, respectively, m0×m1, m1× m2, . . . mn−1× mn. Define a subproblem (remember, this is the most crucialand nontrivial step in the design of a dynamic programming algorithm; the rest is usuallyautomatic) to be to multiply the matrices Ai× · · · × Aj, and let M (i, j) be the optimumnumber of multiplications for doing so. Naturally, M (i, i) = 0, since it takes no effort tomultiply a chain consisting just of the i-th matrix. The recursive equation isM(i, j) = mini≤k<j[M(i, k) + M (k + 1, j) + mi−1· mk· mj].This equation defines the program and its complexity—O(n3).for i := 1 to n do M(i, i) := 0for d := 1 to n − 1 dofor i := 1 to n − d doj = i + d, M(i, j) = ∞, best(i, j) :=nilfor k := i to j − 1 doif M(i, j) > M(i, k) + M (k + 1, j) + mi−1· mk· mjthenM(i, j) := M(i, k) + M (k + 1, j) + mi−1· mk· mj, best(i, j) := kAs usual, improvements are possible (in this case, down to O(n log n)).Run this algorithm in the simple example of four matrices given to verify that theclaimed order is the best!Notes number 16 22 KnapsackA burglar breaks into a house, and finds n objects that he may want to steal. Object i hasweight viand costs about cidollars, and the burglar knows he cannot carry a weight largerthan B. What is the set of objects of larger total value, subject to the constraint that theirtotal weight is less than B? (In an alternative, legal, formulation, you are packing yourknapsack for a hike, the knapsack has volume B, and there are i items that you may wantto pack, item i has volume viand its “usefulness” is ci; what is the set of items of largertotal usefulness that will fit into the knapsack?)Formally, the knapsack problem is as follows:Given: n items of “cost” c1, c2, . . . , cn(positive integers), and of “volume” v1, v2, . . . , vn(positive integers); a volume value B (for bound).Find a subset S ⊆ {1, . . . , n} of the items such thatXi∈Svi≤ B (1)and such that the total costPi∈Sciis maximized.For reasons that will be clear later in the course, there is probably no algorithm for thisproblem that runs in time polynomial in the length of the input (which is about n log B),however there is an algorithm that runs in time polynomial in n and B.We want to solve this problem using dynamic programming, so we should think of howto reduce it to a smaller problem. Let us think of whether item n should or should not bein the optimal solution. If item n is not in the optimal solution, then the optimal solutionis the optimal solution for the same problem but only with items 1, . . . , n − 1; if item n isin the optimal solution, then it leaves B − vnunits of volume for the other items, whichmeans that the optimal solution contains item n, and then contains the optimal solution ofthe same problem on items 1, . . . , n − 1 and volume bound B − vn.This recursion generates subproblems of the form “what is the optimal solution thatuses only items 1, . . . , i and volume B0”?Our dynamic programming algorithm constructs a n × (B + 1) table M [·, ·], whereM[k, B0] contains the cost of an optimum solution for the instance that uses only a subsetof the first k elements (of volume v1, . . . , vkand cost c1, . . . , ck) and with volume B0. Therecursive definition of the matrix is• M[1, B0] = c1if B0≥ v1; M[1, B0] = 0 otherwise.• for every k, B0≥ 1,M[k, B0] = max{M[k − 1, B0] , M[k − 1, B0− vk] + ck}The matrix can be filled in O(Bn) time (constant time per entry), and, at the end, the costof the optimal solution for our input is reported in M [n, B].Notes number 16 3To construct an optimum solution, we also build a Boolean matrix C[·, ·] of the samesize.For every i and B0, C[i, B0] = T rue if and only if there is an optimum solution thatpacks a subset of the first i items in volume B0so that item i is included in the solution.Let us see an example. Consider an instance with 9 items and a bag of size 15. Thecosts and the volumes of the items are as follows:Item 1 2 3 4 5 6 7 8 9Cost 2 3 3 4 4 5 7 8 8Volume 3 5 7 4 3 9 2 11 5This is table MB00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15k = 9 0 0 7 7 7 11 11 15 15 15 19 19 19 21 23 23k = 8 0 0 7 7 7 11 11 11 13 15 15 15 17 17 18 18k = 7 0 0 7 7 7 11 11 11 13 15 15 15 17 17 18 18k = 6 0 0 0 4 4 4 6 8 8 8 10 10 11 11 11 13k = 5 0 0 0 4 4 4 6 8 8 8 10 10 11 11 11 13k = 4 0 0 0 2 4 4 4 6 6 7 7 7 9 9 9 9k = 3 0 0 0 2 2 3 3 3 5 5 5 5 6 6 6 8k = 2 0 0 0 2 2 3 3 3 5 5 5 5 5 5 5 5k = 1 0 0 0 2 2 2 2 2 2 2 2 2 2 2 2 2And this is …