L11 - Dynamic Programming.pdf

CP312 Algorithm Design and Analysis I LECTURE 11: DYNAMIC PROGRAMMING Dynamic Programming A technique for algorithm design to solve optimization-type problems Similar to divide-and-conquer: ◦ Solves problems by combining solutions with smaller subproblems Unlike divide-and-conquer, dynamic programmi...

CP312 Algorithm Design and Analysis I LECTURE 11: DYNAMIC PROGRAMMING Dynamic Programming A technique for algorithm design to solve optimization-type problems Similar to divide-and-conquer: ◦ Solves problems by combining solutions with smaller subproblems Unlike divide-and-conquer, dynamic programming is used when the subproblems are not independent and may repeat. ◦ The DP solves each subproblem and then stores the result so that it can later reuse it without resolving the same subproblem. Simple Example: Fibonacci Number Consider the algorithm for computing the Fibonacci number: Recursion Tree Fib(7) Fib(𝑛): If 𝑛 ≤ 2 then return 1 Else return 𝐅𝐢𝐛 𝑛 − 1 + 𝐅𝐢𝐛(𝑛 − 2) Fib(6) Fib(5) Fib(5) Fib(4) Fib(4) Fib(3) 𝑇 𝑛 = 𝑇 𝑛 − 1 + 𝑇 𝑛 − 2 + Θ(1) Running Time is Exponential = 𝑂(2𝑛 ) It keeps re-solving the same subproblem over and over again! Simple Example: Fibonacci Number Consider an alternative way for computing the Fibonacci number: MemFib(𝑛): Initialize array 𝐴 of size 𝑛 If 𝑛 ≤ 2 then return 1 If 𝐴[𝑛] is not defined 𝐴 𝑛 = 𝐌𝐞𝐦𝐅𝐢𝐛 𝑛 − 1 + 𝐌𝐞𝐦𝐅𝐢𝐛(𝑛 − 2) return 𝐴[𝑛] Both have running time: 𝑂(𝑛) Top-Down Memoization: Store the solutions of already solved subproblems then reuse the solutions when seen again. This is Dynamic Programming. It can be thought of as “smart recursion” IterFib(𝑛): Initialize array 𝐴 of size 𝑛 For 𝑖 = 1 to 𝑛: If 𝑖 ≤ 2 then 𝐴𝑖 =1 If 𝐴[𝑖] is not defined 𝐴 𝑖 =𝐴 𝑖−1 +𝐴 𝑖−2 return 𝐴[𝑖] Bottom-Up Iteration: Solve subproblems starting with the base case and moving towards larger subproblems. Recursion Trees and Subproblem Graphs Recursion Tree Fib (5) Fib(5) Fib (4) Fib(4) Fib(3) Fib(2) Fib(3) Fib(2) Fib(2) Subproblem Graph Edges denote dependencies: e.g. Subproblem Fib(5) needs the solution of subproblems Fib(4) and Fib(3) Fib (3) Fib(1) Fib(1) Models the execution of a pure recursive algorithm Fib (2) Fib (1) Identifies the unique number of subproblems to build a memorized DP solution Steps for Applying Dynamic Programming 1. Identify optimal substructure ◦ An optimal solution to a problem contains optimal solutions to subproblems 2. Identify overlapping subproblems ◦ A recursive solution contains a “small” number of distinct subproblems that are repeated many times. 3. Define a recursive formulation ◦ Assuming solutions to sub-problems, recursively define the final solution 4. Compute the value of the final optimal solution ◦ Store the solutions of sub-problems in a table and build the final solution out of the stored values (top-down or bottom-up) ◦ A subproblem graph helps in identifying in what order to compute the values Rod Cutting Problem Problem: Given a rod of length 𝑛 and a table of prices for each length of rod, determine the maximum revenue to obtain by cutting up the rod and selling the pieces. Input: Initial length 𝑛 and list of prices 𝑝𝑖 for 𝑖 = 1, … , 𝑛 Output: The maximum revenue resulting from any rod cutting Rod Cutting Problem Example: Given the following rod and list of prices: 𝑛=4 What are the possible ways of cutting this rod and what is the revenue for each way? The rod cutting that will yield the highest revenue: 10 Rod Cutting Problem Naïve Solution: We can cut up a rod of length 𝑛 in 2𝑛−1 different ways, since we have an independent option of cutting, or not cutting, at distance 𝑖 from the left end. Running time: 𝑂(2𝑛 ) Exponential! Steps for DP: Rod Cutting 1. Identify optimal substructure ◦ An optimal solution to a problem contains optimal solutions to subproblems 2. Identify overlapping subproblems ◦ A recursive solution contains a “small” number of distinct subproblems that are repeated many times. 3. Define a recursive formulation ◦ Assuming solutions to sub-problems, recursively define the final solution 4. Compute the value of the final optimal solution ◦ Store the solutions of sub-problems in a table and build the final solution out of the stored values (top-down or bottom-up) ◦ A subproblem graph helps in identifying in what order to compute the values Rod Cutting Problem We can come up with a DP algorithm based on the following observations: ◦ The optimal solution contains a left piece at some length 𝑖 and then a remaining part of length 𝑛 − 𝑖 ◦ We only then have to consider how to divide the right part. We have optimal substructure (proof omitted) And we have overlapping subproblems 𝑖 𝑛−𝑖 Rod Cutting: Recursive Formulation Let 𝑅(𝑛) denote the revenue we obtain by first cutting the rod at position 𝑖 and then recursively cut the right part of length 𝑛 − 𝑖 𝑅 𝑛 = 𝑝𝑖 + 𝑅(𝑛 − 𝑖) Profit from left part Profit from remaining part How can we choose among all possibilities for the first initial cut? We try them all and pick the best: 𝑛−1 1 2 𝑛−2 … 𝑅 𝑛 = max 𝑝𝑖 + 𝑅 𝑛 − 𝑖 1≤𝑖≤𝑛 𝑛−1 1 𝑅 𝑛 = max 𝑝𝑖 + 𝑅 𝑛 − 𝑖 1≤𝑖≤𝑛 Rod Cutting: Recursive Formulation Straightforward Recursion Recursion Tree CR(4) Cut-Rod(𝑝, 𝑛): If 𝑛 == 0 then return 0 q = −∞ For 𝑖 = 1 to 𝑛 𝑞 = max(𝑞, 𝑝 𝑖 + Cut-Rod(𝑝, 𝑛 − 𝑖)) return 𝑞 How to speed this up? CR(3) CR(1) CR(2) CR(1) CR(0) CR(0) CR(0) CR(2) CR(0) CR(1) CR(0) CR(1) CR(0) CR(0) Same problems solved over and over again. Exponential time! CR(0) Rod Cutting: Memoized DP From the subproblem graph, we can see: ◦ The dependencies between subproblems. For example, we need the solution to CR(2), CR(1), and CR(0) to solve CR(3). ◦ The number of subproblems is 𝑛 + 1 for a problem (rod) size 𝑛 ◦ The amount of memory to set up for memoization will be equal to the number of subproblems. 0 𝑅 CR(0) 𝑛 CR(1) CR(2) … … … … CR (4) CR (3) CR (2) CR (1) CR(n) CR (0) Solving Bottom-up Memoized Top-down Subproblem Graph Rod Cutting: Memoized DP Use an array 𝑟[0, … , 𝑛] of solutions, initialized with -1 Mem-Cut-Rod(𝑝, 𝑛, 𝑟): If 𝑟 𝑛 ≥ 0 then return 𝑟[𝑛] If 𝑛 == 0 𝑞=0 Else 𝑞 = −∞ for 𝑖 = 1 to 𝑛 𝑞 = max(𝑞, 𝑝 𝑖 + Mem-Cut-Rod(𝑝, 𝑛 − 𝑖, 𝑟)) 𝑟 𝑛 =𝑞 return 𝑞 𝑅 Recursive: Memoized Top-down max 𝑝𝑖 + 𝑅 𝑛 − 𝑖 1≤𝑖≤𝑛 Rod Cutting: Bottom-up DP Use an array 𝑟[0, … , 𝑛] of solutions, initialized with -1 𝑅 BottomUp-Cut-Rod(𝑝, 𝑛, 𝑟): 𝑟 0 =0 for 𝑗 = 1 to 𝑛 𝑞 = −∞ for 𝑖 = 1 to 𝑗 𝑞 = max 𝑞, 𝑝 𝑖 + 𝑟 𝑗 − 𝑖 𝑟 𝑗 =𝑞 return 𝑟[𝑛] Iterative Bottom-up max 𝑝𝑖 + 𝑅 𝑛 − 𝑖 1≤𝑖≤𝑛 Longest Common Subsequence (LCS) Problem: Given two sequences, find a longest (not necessarily contiguous) subsequence that is common in both sequences. Input: Two arrays 𝑥[1, … 𝑚] and 𝑦[1, … , 𝑛] Output: A longest common subsequence in 𝑥 and 𝑦 Example: 𝑥 = 𝐴, 𝐵, 𝐶, 𝐵, 𝐷, 𝐴, 𝐵 𝑦 = 𝐵, 𝐷, 𝐶, 𝐴, 𝐵, 𝐴 𝐿𝐶𝑆(𝑥, 𝑦): 𝑩, 𝑪, 𝑩, 𝑨 Longest Common Subsequence (LCS) Naïve solution: Brute-force ◦ Check every subsequence 𝑥[1, … , 𝑚] to see if it is also a subsequence of 𝑦[1, … , 𝑛] Analysis: ◦ There are 𝟐𝒎 subsequences of 𝑥 (each bit-vector of length 𝑚 determines a distinct subsequence of 𝑥) ◦ For each subsequence of 𝑥, we make 𝑂(𝑛) comparisons to check if it is also in 𝑦 ◦ Worst-case running-time = 𝑶 𝒏𝟐𝒎 Exponential Time! Can we do better? Steps for Applying Dynamic Programming 1. Identify optimal substructure ◦ An optimal solution to a problem contains optimal solutions to subproblems 2. Identify overlapping subproblems ◦ A recursive solution contains a “small” number of distinct subproblems that are repeated many times. 3. Define a recursive formulation ◦ Assuming solutions to sub-problems, recursively define the final solution 4. Compute the value of the final optimal solution ◦ Store the solutions of sub-problems in a table and build the final solution out of the stored values (top-down or bottom-up) ◦ A subproblem graph helps in identifying in what order to compute the values Longest Common Subsequence (LCS) Simplification: 1. Look at the length of a longest-common subsequence 2. Extend the algorithm to find the LCS itself Notation: denote the length of a sequence 𝑠 by 𝑠 Strategy: Consider prefixes of 𝑥 and 𝑦 ◦ Define 𝑐 𝑖, 𝑗 = 𝐿𝐶𝑆 𝑥 1, … , 𝑖 , 𝑦 1, … , 𝑗 ◦ Then 𝑐 𝑚, 𝑛 = 𝐿𝐶𝑆 𝑥, 𝑦 Longest Common Subsequence (LCS) Theorem: 𝑐 𝑖 − 1, 𝑗 − 1 + 1 𝑐 𝑖, 𝑗 = ቊ max 𝑐 𝑖 − 1, 𝑗 , 𝑐 𝑖, 𝑗 − 1 Proof: Case 𝑥 𝑖 = 𝑦[𝑗] 1 2 if 𝑥 𝑖 = 𝑦[𝑗] otherwise 𝑖 𝑚 … 𝑥: 1 𝑦: 2 = 𝑛 𝑗 … 𝑐 𝑖, 𝑗 = ቊ 𝑐 𝑖 − 1, 𝑗 − 1 + 1 max 𝑐 𝑖 − 1, 𝑗 , 𝑐 𝑖, 𝑗 − 1 if 𝑥 𝑖 = 𝑦[𝑗] otherwise Longest Common Subsequence (LCS) Proof (continued) for Case 𝑥 𝑖 = 𝑦[𝑗] 1. Let 𝑧 1, … , 𝑘 = 𝐿𝐶𝑆 𝑥 1, … , 𝑖 , 𝑦 1, … , 𝑗 where 𝑐 𝑖, 𝑗 = 𝑘. ◦ Then 𝑧 𝑘 = 𝑥 𝑖 = 𝑦[𝑗] 2. 3. Thus, 𝑧[1, … , 𝑘 − 1] is a common subsequence of 𝑥[1, … , 𝑖 − 1] and 𝑦[1, … , 𝑗 − 1] Furthermore, 𝑧 1, … , 𝑘 − 1 = 𝐿𝐶𝑆 𝑥 1, … , 𝑖 − 1 , 𝑦[1, … , 𝑗 − 1] ◦ If it is not, then this means there exists a longer common subsequence 𝑤 of 𝑥 1, … , 𝑖 − 1 and 𝑦[1, … , 𝑗 − 1] such that 𝑤 > 𝑘 − 1 whereby appending x[i] or y[j] to w makes 𝑤 + 1 > 𝑘 (Contradiction!) 4. Therefore, 𝑐 𝑖 − 1, 𝑗 − 1 = 𝑘 − 1, which implies that: 𝑐 𝑖, 𝑗 = 𝑐 𝑖 − 1, 𝑗 − 1 + 1 Longest Common Subsequence (LCS) Property 1 Optimal Substructure An optimal solution to a problem contains optimal solutions to subproblems If 𝑧 = 𝐿𝐶𝑆(𝑥, 𝑦) then any prefix of 𝑧 is an LCS of a prefix of 𝑥 and a prefix of 𝑦 𝑐 𝑖, 𝑗 = ቊ 𝑐 𝑖 − 1, 𝑗 − 1 + 1 max 𝑐 𝑖 − 1, 𝑗 , 𝑐 𝑖, 𝑗 − 1 if 𝑥 𝑖 = 𝑦[𝑗] otherwise Recursive algorithm for LCS LCS 𝑥, 𝑦, 𝑖, 𝑗 : if 𝑥 𝑖 == 𝑦[𝑗] 𝑐 𝑖, 𝑗 = LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 − 1 + 1 else 𝑐 𝑖, 𝑗 = max{ LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 , LCS 𝑥, 𝑦, 𝑖, 𝑗 − 1 } Worst-case: 𝑥 𝑖 ≠ 𝑦[𝑗] in which case the algorithm evaluates two subproblems, each with only one parameter decremented. Recursion Tree for LCS 𝑚 = 3, 𝑛 = 4 Height = 𝑚 + 𝑛 ⇒ work potentially exponential 3,4 3,3 2,4 Same subproblem 1,4 2,3 1,3 2,3 2,2 1,3 3,2 2,2 But we’re solving subproblems already solved! ℎ =𝑚+𝑛 Longest Common Subsequence (LCS) Property 2 Overlapping Subproblems A recursive solution contains a “small” number of distinct subproblems that are repeated many times The number of distinct LCS subproblems for two strings of lengths 𝑚 and 𝑛 is only 𝑚𝑛 Memoization algorithm for LCS Memoization: After computing a solution to a subproblem, store it in a table. Subsequent calls check the table to avoid redoing work. LCS 𝑥, 𝑦, 𝑖, 𝑗 : if 𝑐 𝑖, 𝑗 = 𝑁𝑈𝐿𝐿 if 𝑥 𝑖 == 𝑦[𝑗] Same as before 𝑐 𝑖, 𝑗 = LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 − 1 + 1 else 𝑐 𝑖, 𝑗 = max{ LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 , LCS 𝑥, 𝑦, 𝑖, 𝑗 − 1 } Time = Θ 𝑚𝑛 = constant work per table entry Space = Θ(𝑚𝑛) Memoization algorithm for LCS 𝑥 The values in the table are computed top-down 𝐴 Time = Θ(𝑚𝑛) 𝐵 𝐶 𝐵 𝐷 𝐴 𝐵 𝐵 𝐷 𝑦 𝐶 𝐴 LCS 𝑥, 𝑦, 𝑖, 𝑗 : 𝐵 if 𝑐 𝑖, 𝑗 = 𝑁𝑈𝐿𝐿 if 𝑥 𝑖 == 𝑦[𝑗] 𝐴 𝑐 𝑖, 𝑗 = LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 − 1 + 1 else 𝑐 𝑖, 𝑗 = max{ LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 , LCS 𝑥, 𝑦, 𝑖, 𝑗 − 1 } Start by running LCS(𝑥, 𝑦, 𝑚, 𝑛) Memoization algorithm for LCS 𝑥 The values in the table are computed top-down 𝐴 Time = Θ(𝑚𝑛) 𝐵 𝐷 𝑦 𝐶 𝐴 LCS 𝑥, 𝑦, 𝑖, 𝑗 : 𝐵 if 𝑐 𝑖, 𝑗 = 𝑁𝑈𝐿𝐿 if 𝑥 𝑖 == 𝑦[𝑗] 𝐴 𝑐 𝑖, 𝑗 = LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 − 1 + 1 else 𝑐 𝑖, 𝑗 = max{ LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 , LCS 𝑥, 𝑦, 𝑖, 𝑗 − 1 } 𝐵 𝐶 𝐵 𝐷 𝐴 𝐵 Memoization algorithm for LCS 𝑥 The values in the table are computed top-down Time = Θ(𝑚𝑛) 𝑦 𝐴 𝐵 𝐶 0 0 0 0 𝐵 0 0 1 1 𝐷 0 0 1 1 𝐶 0 0 1 2 𝐴 0 1 1 1 2 1 2 LCS 𝑥, 𝑦, 𝑖, 𝑗 : 𝐵 0 if 𝑐 𝑖, 𝑗 = 𝑁𝑈𝐿𝐿 if 𝑥 𝑖 == 𝑦[𝑗] 0 𝐴 𝑐 𝑖, 𝑗 = LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 − 1 + 1 else 𝑐 𝑖, 𝑗 = max{ LCS 𝑥, 𝑦, 𝑖 − 1, 𝑗 , LCS 𝑥, 𝑦, 𝑖, 𝑗 − 1 } 𝐵 𝐷 𝐴 𝐵 … 4 Bottom-up algorithm for LCS 𝑥 Alternatively: Compute the table bottom-up 0 Time = Θ(𝑚𝑛) 𝑦 𝐵 0 𝐷 0 𝐶 0 𝐴 0 𝐵 0 𝐴 0 𝐴 𝐵 𝐶 𝐵 𝐷 𝐴 𝐵 0 0 0 0 0 0 0 Bottom-up algorithm for LCS 𝑥 Alternatively: Compute the table bottom-up Time = Θ(𝑚𝑛) 𝑦 𝐴 𝐵 𝐶 𝐵 𝐷 𝐴 𝐵 0 0 0 0 0 0 0 0 𝐵 0 0 1 1 1 1 1 1 𝐷 0 0 1 1 1 2 2 2 𝐶 0 0 1 2 2 2 2 2 𝐴 0 1 1 2 2 2 3 3 𝐵 0 1 2 2 3 3 3 4 𝐴 0 1 2 2 3 3 4 4 Reconstructing the LCS 𝑥 Reconstruct LCS by tracing backwards 𝑦 𝐴 𝐵 𝐶 𝐵 𝐷 𝐴 𝐵 0 0 0 0 0 0 0 0 𝐵 0 0 1 1 1 1 1 1 𝐷 0 0 1 1 1 2 2 2 𝐶 0 0 1 2 2 2 2 2 𝐴 0 1 1 2 2 2 3 3 𝐵 0 1 2 2 3 3 3 4 𝐴 0 1 2 2 3 3 4 4 0/1 Knapsack Problem Problem: Given a set of items, find a combination of items to add to a bag of some capacity that yields the most value. Input: A set of 𝑛 weight/value pairs S = 1, 𝑣1 , 𝑤1 , 2, 𝑣2 , 𝑤2 , … , 𝑛, 𝑣𝑛 , 𝑤𝑛 and capacity 𝑊 Output: A subset 𝑇 ⊆ {1,2, … , 𝑛} that: Maximizes σ𝑖∈𝑇 𝑣𝑖 Subject to σ𝑖∈𝑇 𝑤𝑖 ≤ 𝑊 The Knapsack Problem Weight (kg) 6 2 4 3 11 Value ($) 20 8 14 13 35 We have a knapsack that can only carry so much weight Capacity: 10 kg The Knapsack Problem Weight (kg) 6 2 4 3 11 Value ($) 20 8 14 13 35 Capacity: 10 kg Total weight: 9 Total value: 35 Suppose I only have one copy of each item What is the most valuable way to fill the bag? 0/1 Knapsack Problem Naïve solution: Brute force: Try all possible subsets of 𝑇 ◦ E.g. Try {1} then {1,2} then {1,2,3} then {1,3} etc. Running time? ◦ Θ(2𝑛 ) Not good! Steps for DP: 0/1 Knapsack Problem 1. Identify optimal substructure ◦ An optimal solution to a problem contains optimal solutions to subproblems 2. Identify overlapping subproblems ◦ A recursive solution contains a “small” number of distinct subproblems that are repeated many times. 3. Define a recursive formulation ◦ Assuming solutions to sub-problems, recursively define the final solution 4. Compute the value of the final optimal solution ◦ Store the solutions of sub-problems in a table and build the final solution out of the stored values (top-down or bottom-up) ◦ A subproblem graph helps in identifying in what order to compute the values 0/1 Knapsack Problem 1. Identify optimal substructure with overlapping subproblems. First solve the problem for small knapsacks Then larger knapsacks Then larger knapsacks 0/1 Knapsack Problem 1. Identify optimal substructure with overlapping subproblems. First solve the problem for small knapsacks Then larger knapsacks Then larger knapsacks First solve the problem for few items Then more items Then more items We need a two-dimensional table 0/1 Knapsack Problem 1. Identify optimal substructure with overlapping subproblems. Case 1: If the optimal solution for 𝑗 items does not use item 𝑗 The first 𝑗 items 𝑗 Capacity: 𝑥 Value: 𝑉 Then the following is an optimal solution for 𝑗 − 1 items: The first 𝑗 − 1 items Capacity: 𝑥 Value: 𝑉 0/1 Knapsack Problem 1. Identify optimal substructure with overlapping subproblems. Case 2: If the optimal solution for 𝑗 items uses item 𝑗 The first 𝑗 items 𝑗 Capacity: 𝑥 Value: 𝑉 Then the following is an optimal solution for 𝑗 − 1 items: The first 𝑗 − 1 items Capacity: 𝑥 − 𝑤𝑗 Value: 𝑉 − 𝑣𝑗 Steps for DP: 0/1 Knapsack Problem 1. Identify optimal substructure ◦ An optimal solution to a problem contains optimal solutions to subproblems 2. Identify overlapping subproblems ◦ A recursive solution contains a “small” number of distinct subproblems that are repeated many times. 3. Define a recursive formulation ◦ Assuming solutions to sub-problems, recursively define the final solution 4. Compute the value of the final optimal solution ◦ Store the solutions of sub-problems in a table and build the final solution out of the stored values (top-down or bottom-up) ◦ A subproblem graph helps in identifying in what order to compute the values 0/1 Knapsack Problem 3. Define a recursive formulation. Let 𝐾[𝑗, 𝑥] be the optimal value for capacity 𝑥 with 𝑗 items 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 Item 𝑗 is not used Item 𝑗 is used if 𝑥 or 𝑗 are 0 otherwise Steps for DP: 0/1 Knapsack Problem 1. Identify optimal substructure ◦ An optimal solution to a problem contains optimal solutions to subproblems 2. Identify overlapping subproblems ◦ A recursive solution contains a “small” number of distinct subproblems that are repeated many times. 3. Define a recursive formulation ◦ Assuming solutions to sub-problems, recursively define the final solution 4. Compute the value of the final optimal solution ◦ Store the solutions of sub-problems in a table and build the final solution out of the stored values (top-down or bottom-up) ◦ A subproblem graph helps in identifying in what order to compute the values 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem 4. Compute the value of the optimal solution bottom-up Knapsack 𝑊, weights, values : 𝑛 = weights. length for 𝑥 = 0 to 𝑊 and 𝑗 = 0 to 𝑛 𝐾 𝑗, 𝑥 = 0 for 𝑥 = 1 to 𝑊 for 𝑗 = 1 to 𝑛 𝐾 𝑗, 𝑥 = 𝐾[𝑗 − 1, 𝑥] 𝑤𝑗 = weights 𝑗 𝑣𝑗 = values[𝑗] if 𝑤𝑗 ≤ 𝑥 𝐾 𝑗, 𝑥 = max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 return 𝐾[𝑛, 𝑊] Capacity: 𝑊 weights 6 2 4 3 11 values 20 8 14 13 35 Runtime: 𝑂(𝑛𝑊) Steps for DP: 0/1 Knapsack Problem 1. Identify optimal substructure ◦ An optimal solution to a problem contains optimal solutions to subproblems 2. Identify overlapping subproblems ◦ A recursive solution contains a “small” number of distinct subproblems that are repeated many times. 3. Define a recursive formulation ◦ Assuming solutions to sub-problems, recursively define the final solution 4. Compute the value of the final optimal solution ◦ Store the solutions of sub-problems in a table and build the final solution out of the stored values (top-down or bottom-up) ◦ A subproblem graph helps in identifying in what order to compute the values 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 3 0 0 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 3 0 0 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 0 1 3 0 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 0 1 3 0 1 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 1 0 1 3 0 1 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 1 0 1 4 3 0 1 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 1 0 1 4 3 0 1 4 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 1 1 0 1 4 3 0 1 4 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 1 1 0 1 4 5 3 0 1 4 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise 0/1 Knapsack Problem Example: Capacity: 3 𝑥 𝐾[𝑗, 𝑥] 𝑗 0 1 2 3 0 0 0 0 0 1 2 0 1 1 1 0 1 4 5 3 0 1 4 6 weights 1 2 3 values 1 4 6 0 𝐾 𝑗, 𝑥 = ൝ max 𝐾 𝑗 − 1, 𝑥 , 𝐾 𝑗 − 1, 𝑥 − 𝑤𝑗 + 𝑣𝑗 if 𝑥 or 𝑗 are 0 otherwise Greedy vs. Dynamic Programming 0/1 Knapsack (using dynamic programming) Fractional Knapsack (using greedy approach) 𝑥 𝐾[𝑗, 𝑥] 0 1 3 Next best choice 0 𝑗 2 1 2 Next best choice 3 𝑇 𝑛 = Θ 𝑛𝑊 𝑇 𝑛 = Θ(𝑛 lg 𝑛) Matrix Chain Multiplication Problem: Given a sequence of matrices, output their product. Input: A sequence of 𝑛 matrices (𝑀1 , … , 𝑀𝑛 ) such that for every pair (𝑖, 𝑗) where 𝑖 < 𝑗, if the dimension of 𝑀𝑖 is (𝑛𝑖 , 𝑚𝑖 ) and the dimension of 𝑀𝑗 is (𝑛𝑗 , 𝑚𝑗 ) then 𝑚𝑖 = 𝑛𝑗 Output: A sequence of matrix multiplications that minimizes the number of multiplication operations. Matrix Chain Multiplication To multiply an 𝑛 × 𝑚 matrix 𝐴 with a 𝑚 × 𝑝 matrix 𝐵 to get a 𝑛 × 𝑝 matrix 𝐶 we use the formula: 𝑚 𝐶𝑖,𝑗 = ෍ 𝐴𝑖,𝑘 𝐵𝑘,𝑗 𝑘=1 Our complexity measure is the number of multiplications: ◦ 𝑚 multiplications are needed to compute each 𝐶𝑖,𝑗 ◦ (𝑛 × 𝑚) × 𝑝 multiplications are needed to compute all elements of 𝐶 Matrix Chain Multiplication Example: Suppose we are trying to compute the product of the 3-matrix sequence (𝑋, 𝑌, 𝑍) ◦ Dimensions of 𝑋 is 100 × 1 ◦ Dimensions of 𝑌 is 1 × 100 ◦ Dimensions of 𝑍 is 100 × 1 One Solution: ◦ Multiply 𝑋 and 𝑌 to get a 100 × 100 matrix 𝑋𝑌 ◦ No. of multiplications = 100 × 1 × 100 = 10,000 ◦ Multiply 𝑋𝑌 and 𝑍 to get the 100 × 1 result ◦ No. of multiplications = 100 × 100 × 1 = 10,000 ◦ Total cost: 20,000 multplications Matrix Chain Multiplication Example: Suppose we are trying to compute the product of the 3-matrix sequence (𝑋, 𝑌, 𝑍) ◦ Dimensions of 𝑋 is 100 × 1 ◦ Dimensions of 𝑌 is 1 × 100 ◦ Dimensions of 𝑍 is 100 × 1 Another Solution: ◦ Multiply 𝑌 and 𝑍 to get a 1 × 1 matrix 𝑌𝑍 ◦ No. of multiplications = 1 × 100 × 1 = 100 ◦ Multiply 𝑋 and 𝑌𝑍 to get the 100 × 1 result ◦ No. of multiplications = 100 × 1 × 1 = 100 ◦ Total cost: 200 multplications Matrix Chain Multiplication Example: Suppose we are trying to compute the product of the 4-matrix sequence (𝑋, 𝑌, 𝑍, 𝑊) ◦ ◦ ◦ ◦ Dimensions of 𝑋 is 10 × 20 Dimensions of 𝑌 is 20 × 50 Dimensions of 𝑍 is 50 × 1 Dimensions of 𝑊 is 1 × 100 To represent the order of the multiplication, we use parentheses: ◦ 𝑋 × (𝑌 × 𝑍 × 𝑊 ) leads to 125,000 multiplications ◦ 𝑋 × 𝑌 × 𝑍 × 𝑊 leads to 2,200 multiplications Matrix Chain Multiplication Naïve Approach: Try all possible ways of parenthesization. ◦ Is this a good idea? Let 𝑃(𝑛) be the number of different ways to parenthesize 𝑛 matrices. Then: σ𝑛−1 𝑃 𝑛 = ቊ 𝑘=1 𝑃 𝑘 𝑃(𝑛 − 𝑘) if 𝑛 ≥ 2 1 if 𝑛 = 1 This recurrence is related to the Catalan numbers and solves to Exponential! 𝑃 𝑛 = 𝑂 4𝑛 /𝑛1.5 Matrix Chain Multiplication Let us try to apply DP to solve this using polynomial time. Let 𝑀1 , … , 𝑀𝑛 be the 𝑛 matrices whose product 𝑀1 × ⋯ × 𝑀𝑛 we want to compute. Denote the dimensions of matrix 𝑀𝑖 by 𝑝𝑖−1 × 𝑝𝑖 Let 𝑀𝑖,𝑗 where 𝑖 ≤ 𝑗 be the matrix corresponding to the partial result 𝑀𝑖 × 𝑀𝑖+1 × ⋯ × 𝑀𝑗 Matrix Chain Multiplication Steps for Applying Dynamic Programming: 1. Identify optimal substructure with overlapping subproblems. 2. Define a recursive formulation ◦ Assuming solutions to sub-problems, recursively define the final solution 3. Compute the value of the optimal solution bottom-up ◦ Store the solutions of sub-problems in a table (memorization) and build the final solution out of the stored values. Matrix Chain Multiplication Any optimal parenthesization of 𝑀𝑖 × 𝑀𝑖+1 × ⋯ × 𝑀𝑗 must split the product into two parts: 𝑀𝑖 × 𝑀𝑖+1 × ⋯ × 𝑀𝑘 and 𝑀𝑘+1 × 𝑀𝑘+2 × ⋯ × 𝑀𝑗 for some 𝑘 ∈ [𝑖, 𝑗] What is the cost of such split: ◦ Cost = cost of computing 𝑀𝑖,𝑘 + cost of computing 𝑀𝑘+1,𝑗 + cost of computing 𝑀𝑖,𝑘 𝑀𝑘+1,𝑗 1. Do we have optimal substructure? 2. Do we have overlapping subproblems? Matrix Chain Multiplication 1. Do we have optimal substructure? ◦ Yes! Proof sketch: suppose not. If the parenthesization of each of the subproducts is not optimal then we could substitute a better one and obtain a solution to the original problem with smaller cost. Thus the problem has optimal substructure. Matrix Chain Multiplication 2. Do we have overlapping subproblems? ◦ Yes! Proof sketch: Recall that there are 𝑃 𝑛 = 𝑂(4𝑛 /𝑛1.5 ) different ways to parenthesize (i.e. that many different subproblems), but there are Θ(𝑛2 ) unique subproblems since a subproblem of the form 𝑀𝑖,𝑗 and 𝑖, 𝑗 ∈ [1, 𝑛]. Thus we are solving some subproblems multiple times. By tabulating the solutions, we can solve every subproblem just once. Matrix Chain Multiplication Having defined the type of subproblems it is very easy to recursively define the cost of the optimal solution. ◦ Let 𝑚𝑖,𝑗 be the minimum number of multiplications for computing the product 𝑀𝑖,𝑗 = 𝑀𝑖 × 𝑀𝑖+1 × ⋯ × 𝑀𝑗 ◦ Our goal is to compute 𝑚1,𝑛 How do we define 𝑚𝑖,𝑗 recursively? ◦ Hint: consider the cases 𝑖 = 𝑗 and 𝑖 ≠ 𝑗 Matrix Chain Multiplication Case 1: 𝑖 = 𝑗 ◦ The product 𝑀𝑖,𝑗 = 𝑀𝑖 × 𝑀𝑖+1 × ⋯ × 𝑀𝑗 consists of just one matrix, so there is nothing to multiply. ◦ The cost 𝑚𝑖,𝑗 = 0 Case 2: 𝑖 ≠ 𝑗 ◦ We use the optimal substructure property ◦ There is going to be some index 𝑘 such that the product 𝑀𝑖 × 𝑀𝑖+1 × ⋯ × 𝑀𝑗 is split into two parts 𝑀𝑖 × 𝑀𝑖+1 × ⋯ × 𝑀𝑘 and 𝑀𝑘+1 × 𝑀𝑘+2 × ⋯ × 𝑀𝑗 ◦ The cost of this split will be 𝑚𝑖,𝑗 = 𝑚𝑖,𝑘 + 𝑚𝑘+1,𝑗 + 𝑝𝑖−1 𝑝𝑘 𝑝𝑗 ◦ How do we find the best split? Matrix Chain Multiplication Case 2: 𝑖 ≠ 𝑗 ◦ How do we find the best split? Try all possible 𝑘 and take the minimum Thus, the recursive formulation is: 𝑚𝑖,𝑗 0 = ቐ min 𝑚 + 𝑚 𝑖,𝑘 𝑘+1,𝑗 + 𝑝𝑖−1 𝑝𝑘 𝑝𝑗 𝑖≤𝑘