CMSC 451 Subset Sum Knapsack Slides By Carl Kingsford Department of Computer Science University of Maryland College Park Based on Section 6 4 of Algorithm Design by Kleinberg Tardos Subset Sum Subset Sum Given an integer bound W and a collection of n items each with a positive integer weight wi find a subset S of items that P P maximizes i S wi while keeping i S wi W Motivation you have a CPU with W free cycles and want to choose the set of jobs each taking wi time that minimizes the number of idle cycles Assumption We assume W and each wi is an integer Optimal Notation Notation Let S be an optimal choice of items e g a set 1 4 8 Let OPT n W be the value of the optimal solution We design an dynamic programming algorithm to compute OPT n W Subproblems To compute OPT n W We need the optimal value for subproblems consisting of the first j items for every knapsack size 0 w W Denote the optimal value of these subproblems by OPT j w Recurrence Recurrence How do we compute OPT j w given solutions to smaller subproblems OPT j 1 W if j 6 S OPT j W max wj OPT j 1 W wj if j S Special case if wj W then OPT j W OPT j 1 W Another way to write it j 1 W if wj W OPT OPT j W OPT j 1 W if j 6 S max wj OPT j 1 W wj if j S Note Because we don t know the answer to the blue questions we have to try both The table of solutions OPT n W 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 OPT 4 11 Filling in a box using smaller problems OPT j 1 W wj 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 OPT j w OPT j 1 W Filling in a box using smaller problems OPT j 1 W wj 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 OPT j w OPT j 1 W Remembering Which Subproblem Was Used When we fill in the gray box we also record which subproblem was chosen in the maximum OPT j 1 W wj 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 OPT j w OPT j 1 W Filling in the Matrix Fill matrix from bottom to top left to right 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 When you are filling in box you only need to look at boxes you ve already filled in Pseudocode SubsetSum n W Initialize M 0 w 0 for each w 0 W Initialize M i 0 0 for each i 1 n For i 1 n For w 0 W If w i w M i w M i 1 w for every row for every column case where item can t fit M i w max which is best M i 1 w w j M i 1 W w j Return M n W Finding The Choice of Items Follow the arrows backward starting at the top right 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 Which items does this path imply Finding The Choice of Items Follow the arrows backward starting at the top right 9 0 8 0 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 Which items does this path imply 8 5 4 2 Runtime Runtime O nW to fill in the matrix O n time to follow the path backwards Total running time is O nW This is pseudo polynomial because it depends on the size of the input numbers Knapsack Knapsack Given a bound W and a collection of n items each with a weight wi a value vi for each weight Find a subset S of items that P P maximizes i S vi while keeping i S wi W Difference from Subset Sum want to maximize value instead of weight How can we solve Knapsack How can we solve Knapsack Knapsack Subset Sum OPT j 1 W if j 6 S OPT j W max wj OPT j 1 W wj if j S Knapsack Subset Sum OPT j 1 W if j 6 S OPT j W max wj OPT j 1 W wj if j S Knapsack OPT j 1 W OPT j W max vj OPT j 1 W wj if j 6 S if j S Fractional Knapsack 0 1 Knapsack You re presented with n where item i has value vi and size wi You have a knapsack of size W and you want to take the items S so that P vi is maximized and Pi S i S wi W This is a hard problem However if we are allowed to take fractions of items we can do it with a simple greedy algorithm Value of a fraction f of item i is f vi Weight of a fraction f is f wi Knapsack Example Idea Sort the items by pi vi wi Larger vi is better smaller wi is better 30 1 40 p1 30 2 45 p2 20 100 knapsack size 6 p3 15 3 p4 25 4 1 30 4 100 1 2 1 2 40 150 0 1 Knapsack This greedy algorithm doesn t work for 0 1 knapsack where we can t take part of an item 30 1 40 p1 30 2 45 p2 20 100 knapsack size 6 Greedy Choice p4 25 4 1 30 A better choice p3 15 3 4 100 4 130 2