6.006 Introduction to Algorithms, Recitation 18

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Recitation 18: Subset Sum Variants Recitation 18: Subset Sum Variants Subset Sum Review • Input: Set of n positive integers A[i] • Output: Is there subset A0 ⊂ A such that P a∈A0 a = S? • Can solve with dynamic programming in O(nS) time Subset Sum 1. Subproblems • Here we’ll try 1-indexed prefixes for comparison • x(i, j): True if can make sum j using items 1 to i, False otherwise 2. Relate • Is last item i in a valid subset? (Guess!) • If yes, then try to sum to j − A[i] ≥ 0 using remaining items • If no, then try to sum to j using remaining items ( ) x(i − 1, j − A[i]) if j ≥ A[i] • x(i, j) = OR x(i − 1, j) always • for i ∈ {0, . . . , n}, j ∈ {0, . . . , S} 3. Topo • Subproblems x(i, j) only depend on strictly smaller i, so acyclic 4. Base • x(i, 0) = True for i ∈ {0, . . . , n} (trivial to make zero sum!) • x(0, j) = False for j ∈ {1, . . . , S} (impossible to make positive sum from empty set) 5. Original • Solve subproblems via recursive top down or iterative bottom up • Maximum evaluated expression is given by x(n, S) 6. Time • (# subproblems: O(nS)) × (work per subproblem O(1)) = O(nS) running time. Recitation 18: Subset Sum Variants 2 Exercise: Partition - Given a set of n positive integers A, describe an algorithm to determine whether A can be partitioned into two non-intersecting P P subsets A1 and A2 of equal sum, i.e. A1 ∩ A2 = ∅ and A1 ∪ A2 = A such that a∈A1 a = a∈A2 a. Example: A = {1, 4, 3, 12, 19, 21, 22} has partition A1 = {1, 19, 21}, A2 = {3, 4, 12, 22}. Solution: Run subset sum dynamic program with same A and S = 1 2 P a∈A a. Exercise: Close Partition - Given a set of n positive integers A, describe an algorithm to find a partition of A into two non-intersecting subsets A1 and A2 such that the difference between their respective sums are minimized. P Solution: Run subset sum dynamic program as above, but evaluate for every S 0 ∈ {0, . . . , 12 a∈A a}, and return the largest S 0 such that the subset sum dynamic program returns true. Note that this still only takes O(nS) time: O(nS) to compute all subproblems, and then O(nS) time again to loop over the subproblems to find the max true S 0 . Exercise: Can you adapt subset sum to work with negative integers? Solution: Same as subset sum (see L19), but we allow calling subproblems with larger j. But now instead of solving x(i, j) only in the range P i ∈ {0, . . . , n}, j ∈ {0, . . . , S} as in positive P subset sum, we allow j to range from jmin = a∈A,a<0 a (smallest possible j) to jmax = a∈A,a>0 a (largest possible j). x(i, j) = OR {x(i − 1, j − A[i]), x(i − 1, j)} (note jmin ≤ j − A[i] ≤ jmax is always true) Subproblem dependencies are still acyclic because x(i, j) only depend on strictly smaller i. Base cases are x(0, 0) = True and x(0, j) = False if j 6= 0. Running time is then proportional to number of constant work subproblems, O(n(jmax − jmin )). Alternatively, you can convert to an equivalent instance of positive subset sum and solve that. P Choose large number Q > max(|S|, a∈A |a|). Add 2Q to each integer in A to form A0 , and append the value 2Q, n − 1 times to the end of A0 . Every element of A0 is now positive, so solve positive subset sum with S 0 = S + n(2Q). Because (2n − 1)Q < S 0 < (2n + 1)Q, any satisfying 0 subset will contain exactly P n integers from A since the sum of any fewer would have sum no greater than (n − 1)2Q P + a∈A |a| < (2n − 1)Q, and sum of any more would have sum no smaller than (n + 1)2Q − a∈A |a| > (2n + 1)Q. Further, at least one integer in a satisfying subset of A0 corresponds to an integer of A since S 0 is not divisible by 2Q. If A0 has a subset B 0 summing to S 0 , then the items in A corresponding to integers in B 0 will comprise a nonempty subset that sums to S. Conversely, if A has a subset B that sums to S, choosing the k elements of A0 corresponding the integers in B and n − k of the added 2Q values in A0 will comprise a subset B 0 that sums to S 0 . This is an example of a reduction: we show how to use a black-box to solve positive subset sum to solve general subset sum. However, this reduction does lead to a weaker pseudopolynomial time bound of O(n(S + 2nQ)) than the modified algorithm presented above. Recitation 18: Subset Sum Variants 3 0-1 Knapsack • Input: Knapsack with size S, want to fill with items each item i has size si and value vi . P P • Output: A subset of items (may take 0 or 1 of each) with si ≤ S maximizing value vi • (Subset sum same as 0-1 Knapsack when each vi = si , deciding if total value S achievable) • Example: Items {(si , vi )} = {(6, 6), (9, 9), (10, 12)}, S = 15 • Solution: Subset with max value is all items except the last one (greedy fails) 1. Subproblems • Idea: Is last item in an optimal knapsack? (Guess!) • If yes, get value vi and pack remaining space S − si using remaining items • If no, then try to sum to S using remaining items • x(i, j): maximum value by packing knapsack of size j using items 1 to i 2. Relate ( • x(i, j) = max vi + x(i − 1, j − si ) if j ≥ si x(i − 1, j) ) always • for i ∈ {0, . . . , n}, j ∈ {0, . . . , S} 3. Topo • Subproblems x(i, j) only depend on strictly smaller i, so acyclic 4. Base • x(i, 0) = 0 for i ∈ {0, . . . , n} (zero value possible if no more space) • x(0, j) = 0 for j ∈ {1, . . . , S} (zero value possible if no more items) 5. Original • Solve subproblems via recursive top down or iterative bottom up • Maximum evaluated expression is given by x(n, S) • Store parent pointers to reconstruct items to put in knapsack 6. Time • # subproblems: O(nS) • work per subproblem O(1) • O(nS) running time Recitation 18: Subset Sum Variants 4 Exercise: Close Partition (Alternative solution) Solution: Given integers A, solve a 0-1 Knapsack instance with si = vi = A[i] and S = where the subset returned will be one half of a closest partition. 1 2 P a∈A a, Exercise: Unbounded Knapsack - Same problem as 0-1 Knapsack, except that you may take as many of any item as you like. Solution: The O-1 Knapsack formulation works directly except for a small change in relation, where i will not be decreased if it is taken once, where the topological order strictly decreases i + j with each recursive call. ( ) vi + x(i, j − si ) if j ≥ si x(i, j) = max x(i − 1, j) always An equivalent formulation reduces subproblems to expand work done per subproblem: 1. Subproblems: • x(j): maximum value by packing knapsack of size j using the provided items 2. Relate: • x(j) = max{vi + x(j − si ) | i ∈ {1, . . . , n} and si ≤ j} ∪ {0}, 3. Topo • Subproblems x(j) only depend on strictly smaller j, so acyclic 4. Base • x(0) = 0 (no space to pack!) 5. Original • Solve subproblems via recursive top down or iterative bottom up • Maximum evaluated expression is given by x(S) • Store parent pointers to reconstruct items to put in knapsack 6. Time • # subproblems: O(S) • work per subproblem O(n) • O(nS) running time We’ve made CoffeeScript visualizers solving subset sum and 0-1 Knapsack: https://codepen.io/mit6006/pen/JeBvKe https://codepen.io/mit6006/pen/VVEPod for j ∈ {0, . . . , S}