1 00:00:00,000 --> 00:00:04,905 So now that we understand the way in which optimal solutions must be composed 2 00:00:04,905 --> 00:00:07,672 of optimal solutions to smaller subproblems. 3 00:00:07,672 --> 00:00:12,200 We're well positioned to turn that into a recurrence, and then a dynamic 4 00:00:12,200 --> 00:00:15,093 programming solution for the knapsack problem. 5 00:00:15,093 --> 00:00:20,187 To compile our discussion from last time into a recurrence, let me just introduce 6 00:00:20,187 --> 00:00:26,140 a little notation. So by capital v sub I x, what I mean is 7 00:00:26,140 --> 00:00:31,910 the maximum value you can get of a solution that satisfies two constraints. 8 00:00:31,910 --> 00:00:36,372 First of all, it should make use only of the first I items. 9 00:00:36,372 --> 00:00:42,220 Second of all, the total size of the items that you pick should be at most x. 10 00:00:44,240 --> 00:00:48,284 The analogue of this notation in the independent set problem was G sub I, the 11 00:00:48,284 --> 00:00:52,013 graph with the first I vertices. We're now using two indices instead of 12 00:00:52,013 --> 00:00:55,741 one because sub-problems have two different ways in which they can get 13 00:00:55,741 --> 00:00:57,737 smaller. Recall case two of our though 14 00:00:57,737 --> 00:01:01,886 experiments, when we look at a smaller sub-problem there was both one less item 15 00:01:01,886 --> 00:01:05,856 and there was also less capacity. So when thinking about a sub-problem we 16 00:01:05,856 --> 00:01:08,965 need to keep track of both. We need to keep track of how many items 17 00:01:08,965 --> 00:01:12,863 are we allowed to use and we need to keep track of what's the total size that we're 18 00:01:12,863 --> 00:01:15,671 allowed to use. So let's express our conclusion to the 19 00:01:15,671 --> 00:01:19,029 last video in this notation. What did we figure out last video? 20 00:01:19,029 --> 00:01:22,820 We figured out that the optimal solution has to have one of two forms. 21 00:01:22,820 --> 00:01:27,043 Either you just inherit the optimal solution from that tech instance with one 22 00:01:27,043 --> 00:01:30,942 less prop, one less item, that was the first case, or you take the optimal 23 00:01:30,942 --> 00:01:35,491 solution to the sub-problem which has one less item and less capacity by the weight 24 00:01:35,491 --> 00:01:39,661 of the current item and you extend it to an optimal solution for the current 25 00:01:39,661 --> 00:01:45,566 sub-problem using the ith item. So V sub I, X. 26 00:01:45,566 --> 00:01:48,916 The optimal value for the current sub problem. 27 00:01:48,916 --> 00:01:53,140 It's the better of the two possibilities, so we take a max. 28 00:01:54,320 --> 00:01:59,847 The first possibility is just the optimal solution to the, with the same capacity 29 00:01:59,847 --> 00:02:02,781 in one pure item, we're using that solution. 30 00:02:02,781 --> 00:02:07,080 The second one is you commit to using item I, you gain value vi. 31 00:02:13,720 --> 00:02:17,556 And you combine that with the optimal solution using the first I minus one 32 00:02:17,556 --> 00:02:21,240 items in the reduced capacity of X minus the weight of the current item. 33 00:02:22,880 --> 00:02:27,190 So one quick edge case. If the weight of the ith item is bigger 34 00:02:27,190 --> 00:02:32,389 than our permitted capacity x, then of course we can't use it, and then we're 35 00:02:32,389 --> 00:02:36,494 forced to use the first case. We're forced to be in case one. 36 00:02:36,494 --> 00:02:40,120 This then is our recurrence for the knapsack problem. 37 00:02:41,780 --> 00:02:45,997 So that completes step one where we think about the optimal solution structure and 38 00:02:45,997 --> 00:02:49,808 use that to devise a recurrence. Now, in the step two, we're going to 39 00:02:49,808 --> 00:02:53,960 precisely nail down what exactly are the subproblems we have to care about. 40 00:02:53,960 --> 00:02:58,170 Well in our maximum waited independence set example on path graphs remember the 41 00:02:58,170 --> 00:03:02,012 reasoning every time we recursed every time we needed to look up a, a sub 42 00:03:02,012 --> 00:03:05,959 problem solution it was obtained by plucking verticies off of the right of 43 00:03:05,959 --> 00:03:10,275 the graph and for that reason all we ever cared about was the various prefixes of 44 00:03:10,275 --> 00:03:13,011 the graph. In one dimension we got something similar 45 00:03:13,011 --> 00:03:17,327 going on here whenever we look at smaller sub problems it's always with one fewer 46 00:03:17,327 --> 00:03:21,380 item we're always sort of deleting the last item before we do our look up. 47 00:03:21,380 --> 00:03:24,887 So again, we need to worry about all possible prefixes of the items. 48 00:03:24,887 --> 00:03:27,872 So sub-problems, of the first I items for all values of I. 49 00:03:27,872 --> 00:03:32,165 For the knapsack problem however there's a second sense in which sub-problems can 50 00:03:32,165 --> 00:03:34,678 be smaller. And remember case two of our thought 51 00:03:34,678 --> 00:03:37,768 experiment, when we want to know the optimal solution 52 00:03:37,768 --> 00:03:40,071 that's guaranteed to use the current item I. 53 00:03:40,071 --> 00:03:43,998 We have to reduce the capacity before looking up the corresponding optimal 54 00:03:43,998 --> 00:03:49,637 solution of a sub-problem. That is we're not just peeling off items, 55 00:03:49,637 --> 00:03:53,690 but we're also sort of peeling off parts of the knapsack capacity. 56 00:03:53,690 --> 00:03:57,704 Now, here is where we're going to use our assumption, that I told you at the 57 00:03:57,704 --> 00:04:01,272 beginning, at our input, that sizes are all integers, and that the 58 00:04:01,272 --> 00:04:05,007 knapsack capacity is an integer. So, the knapsack capacity starts at 59 00:04:05,007 --> 00:04:07,572 capital W. Every time we peel off some integer 60 00:04:07,572 --> 00:04:11,196 amount of capacity from it. So at all sub problems, we're going to be 61 00:04:11,196 --> 00:04:13,537 working with integral knapsack capacities. 62 00:04:13,537 --> 00:04:15,768 So therefore, in the worst case, you know, 63 00:04:15,768 --> 00:04:18,611 what are the various sub problems that might arise? 64 00:04:18,611 --> 00:04:22,737 Well, perhaps, each choice of a residual capacity, 012, all the way up to the 65 00:04:22,737 --> 00:04:27,833 original knapsack capacity, capital W. So now we're in great shape. 66 00:04:27,833 --> 00:04:31,163 In step two, we figured out exactly what subproblems we care about. 67 00:04:31,163 --> 00:04:35,100 In step one, we figured out a formula by which we can solve bigger subproblems 68 00:04:35,100 --> 00:04:39,087 given the solutions of smaller ones, so all that remains now is to write down a 69 00:04:39,087 --> 00:04:42,922 table and fill it in systematically using the recurrence, beginning with the 70 00:04:42,922 --> 00:04:45,900 smaller subproblems, ending up with the largest subproblems. 71 00:04:45,900 --> 00:04:49,249 So here's this pseudo-code. It's again going to be very simple. 72 00:04:49,249 --> 00:04:53,139 In this algorithm, the array A that we're going to be filling in has two 73 00:04:53,139 --> 00:04:57,299 dimensions, in contrast to one dimension in the wave independence set problem. 74 00:04:57,299 --> 00:05:00,487 That's because our sub-problems have two different indices. 75 00:05:00,487 --> 00:05:04,647 We have to keep track of both of which set of items we're allowed to use, and 76 00:05:04,647 --> 00:05:08,865 also what capacity we need to respect. So the two independent varables indexing 77 00:05:08,865 --> 00:05:13,195 sub problems forces us to have a 2D array that we're going to go through now in a 78 00:05:13,195 --> 00:05:19,793 double four loop. So in the init-, initialization step, we 79 00:05:19,793 --> 00:05:22,311 fill in all the entries, where I equals zero, 80 00:05:22,311 --> 00:05:26,773 where there's no items there, of course, the optimal solution value is zero, and 81 00:05:26,773 --> 00:05:29,920 then we just go through the sub problem systematically. 82 00:05:32,840 --> 00:05:37,396 When we get to a sub-problem we use the recurrence that we developed to compute 83 00:05:37,396 --> 00:05:41,611 the entry in that table using, of course, the entries that we've previously 84 00:05:41,611 --> 00:05:45,654 computed in earlier iterations. So for a given sub-problem where you're 85 00:05:45,654 --> 00:05:49,300 allowed to use the first I items and the residual capacity is X. 86 00:05:49,300 --> 00:05:52,132 What do we know from my thought experiment? 87 00:05:52,132 --> 00:05:57,005 This can only be one of two things. We're just going to do brute force search 88 00:05:57,005 --> 00:06:01,681 through the two possibilities. The two possibilities where we have case 89 00:06:01,681 --> 00:06:06,094 one where we just inherit the optimal solution with one fewer item, 90 00:06:06,094 --> 00:06:10,441 and the same capacity. Or if we're going to actually use item I, 91 00:06:10,441 --> 00:06:15,051 then we compose that with the optimal solution from the first I items. 92 00:06:15,051 --> 00:06:20,057 That leaves enough space for item I. And in that case, we get the value V sub 93 00:06:20,057 --> 00:06:29,062 I for including this Ith item. So this code doesn't quite make sense in 94 00:06:29,062 --> 00:06:33,687 the case where the weight of the current item, wy, is strictly bigger than the, 95 00:06:33,687 --> 00:06:36,930 the capacity, x. that would give us a negative array 96 00:06:36,930 --> 00:06:39,633 index, which, of course, is a no-no. But in that 97 00:06:39,633 --> 00:06:44,378 case, you know, amongst friends we just interpret it as ignoring the second case 98 00:06:44,378 --> 00:06:45,760 of the max. So, you know? 99 00:06:45,760 --> 00:06:48,162 I'm not going to write down the extra code. 100 00:06:48,162 --> 00:06:52,607 But what you would write down is. If WI is strictly bigger than x, then you 101 00:06:52,607 --> 00:06:55,190 just define a of I, x to be equal to a of ai-1, x. 102 00:06:55,190 --> 00:07:00,124 And one crucial point, is that, you know, by the time we need to solve subproblem 103 00:07:00,124 --> 00:07:04,998 with a given I and a given X, we have at our disposal the solutions to all of the 104 00:07:04,998 --> 00:07:08,909 subproblems that we need. In particular, in the previous iteration 105 00:07:08,909 --> 00:07:13,723 of the outer for loop, we computed the solutions to the two relevant subproblems 106 00:07:13,723 --> 00:07:17,935 for evaluating this recurrence. They're there waiting for us available 107 00:07:17,935 --> 00:07:24,186 for constant time lookup. So after this double four loop completes, 108 00:07:24,186 --> 00:07:29,281 sitting there waiting for us in A, in the entry N comma capital W, is the solution 109 00:07:29,281 --> 00:07:32,557 that we wanted. That's the max value solution that can 110 00:07:32,557 --> 00:07:37,591 use any items that it wants and that can use the entire original knapsack capacity 111 00:07:37,591 --> 00:07:40,017 capital W. That's what we want to return. 112 00:07:40,017 --> 00:07:43,050 So that's it. That's the whole dynamic programming 113 00:07:43,050 --> 00:07:47,417 solution for the knapsack problem. Just to make sure this makes sense, in 114 00:07:47,417 --> 00:07:51,905 the next quiz, I want to ask you to analyze the running time of this dynamic 115 00:07:51,905 --> 00:08:01,918 programming algorithm. Alright, so the correct answer is the 116 00:08:01,918 --> 00:08:05,001 second one. And the running time analysis is as 117 00:08:05,001 --> 00:08:08,962 straightforward as it was for the max weight independent set problem. 118 00:08:08,962 --> 00:08:13,153 We just count up the number of sub-problems and look at how much work we 119 00:08:13,153 --> 00:08:15,794 do in each. So how many sub-problems are there? 120 00:08:15,794 --> 00:08:20,329 Where they're indexed by both I and x, there are n plus one choices for I, there 121 00:08:20,329 --> 00:08:24,520 are capital w plus one choices for x. So that gives us theta of n times w 122 00:08:24,520 --> 00:08:27,850 different sub-problems. And all we do for each is a single 123 00:08:27,850 --> 00:08:30,663 comparison amongst previously computed solutions. 124 00:08:30,663 --> 00:08:33,190 So we just do constant work per sub-problem, 125 00:08:33,190 --> 00:08:37,190 giving us the overall running time of n times capital W. 126 00:08:37,190 --> 00:08:41,327 So, a couple other quick notes, which play out in exactly the same way as for 127 00:08:41,327 --> 00:08:45,355 the Maximum Independence Set problem. So I'm not going to discuss the details 128 00:08:45,355 --> 00:08:47,151 here. So first of all, correctness. 129 00:08:47,151 --> 00:08:51,288 Again, it's exactly the same template as in the previous dynamic programming 130 00:08:51,288 --> 00:08:54,064 algorithm, and in our divide and conquer algorithms. 131 00:08:54,064 --> 00:08:56,514 You just go by induction on the problem size. 132 00:08:56,514 --> 00:09:00,705 And, you use the case analysis or a thought experiment to justify, formally, 133 00:09:00,705 --> 00:09:04,031 the inductive step. So this algorithm suffers from a similar 134 00:09:04,031 --> 00:09:09,004 drawback to the max independent set algorithm for path graphs that we looked 135 00:09:09,004 --> 00:09:11,127 at. Namely it computes the value of an 136 00:09:11,127 --> 00:09:13,865 optimal solution not the optimal solution itself. 137 00:09:13,865 --> 00:09:17,280 It returns a number, not an actual subset of items. 138 00:09:17,280 --> 00:09:21,315 But, just like with the independence set problem, you can reconstruct an optimal 139 00:09:21,315 --> 00:09:24,329 solution from the filled in array just by tracing backward. 140 00:09:24,329 --> 00:09:28,415 So the intuition is that you begin with the biggest sub-problem, and you look at 141 00:09:28,415 --> 00:09:31,173 which of the two cases was used to fill in that entry. 142 00:09:31,173 --> 00:09:34,391 If case one was used, you know you should exclude the last item. 143 00:09:34,391 --> 00:09:37,610 If case two was used, you know you should include the last item. 144 00:09:37,610 --> 00:09:41,645 And also, which of those two cases tells you which sub-problem you should trace 145 00:09:41,645 --> 00:09:45,355 back to, to continue the process. So I encourage you to spell out the 146 00:09:45,355 --> 00:09:49,564 details of this reconstruction algorithm in the privacy of your own home. 147 00:09:49,564 --> 00:09:54,349 That'll give you some nice practice with this reconstruction aspect of the dynamic 148 00:09:54,349 --> 00:09:55,560 programming paradigm.