So in these next two videos we'll give our second application of the dynamic programming paradigm. It's to a quite well known problem, it's called the knapsack problem. And we'll show how following the exact same recipe that we used for computing independent sets in path graphs leads to the very well known dynamic programming solution to this problem. So lets jump right into the definition of a knapsack problem. So the input is given by N items. So each item comes with a value V sub I, the more the better for us, and also a size W sub I. We're going to assume that both of these are non negative. For the sizes we're going to make an additional assumption that they're integral. In addition to these two N numbers we're given one more which is called the capacity capital W, again we'll assume this is both non negative and an integer. The role of this integrality assumptions will become clear in due time. The knapsack problem, the responsibility of an algorithm is, is to select a subset of the items. What do we want? What we want is much value as possible. So we want maximize the sum of the values of the items that we select. So, what prevents us from picking everything, well, the sum of the sizes of the items that we pick have to total to at most the capacity of capital W. Now, I could tell you some cheesy story about a burglar breaking into a house with a knapsack, with a certain size capital W, and wants to make away with sort of the best loot possible. But, that would really be doing a disservice to this problem, which is actually quite fundamental. this problem comes up quite a bit, especially as a sub-routine in some larger task. Really, just whenever you have sort of a budget of a resource that you can use, and you want to use it in the smartest way possible, that's basically the knapsack problem. So, you can imagine how it would come up in a lot of contexts. So let's now execute a recipe for developing a dynamic programming algorithm. Remember the key to any dynamic programming solution is to figure out what is the right set of sub-problems. And we're going to arrive at the sub problems for the knapsack problem, just as we did for max weight independence sets by doing a thought experiment about the optimal solution, and understanding what it has to look like, in terms of solutions to smaller sub problems. The bottom line of this thought experiment, the deliverable, will be a recurrence. It'll be a formula which tells us how the optimal value of one subproblem depends on the value of smaller sub problems. So to begin the thought experiment, fix an instance of knapsack, and let capital S denote an optimal solution, a max value solution. We began our previous thought experiment with a content-free statement that the final vertex of a path is either in the optimal solution or it's not. Now, what is the analog of the rightmost vertex in this knapsack problem? Well, unlike a path graph, there's no intrinsic sequentiality to the items that we're given. They're just an unordered set. But it's actually useful to think of the items as sort of literally ordered, one, two, three, all the way up to n. And then, the analog of the rightmost vertex is just the final item. So the content free statement we're going to work with here is either the last item belongs to the optimal solution, capital S, or it doesn't. We'll again start with an easy case when it doesn't. What we argued in the path graph problem was that the max weight independent set in the analogous case one has to be optimal if we just delete that rightmost edge from the graph. So here the analogous claim is that this set s should still be optimal if we delete the final item n from the knapsack instance. The argument is the exact same near trivial contradiction. If there was a different solution as star amongst the first and minus one items, with weight even bigger than that of S. What we could regard this equally well as a superior knapsack feasible solution, back with all N of the items, but that contradicts the purported optimality of S. So let's go through the slightly trickier case two together, using a quiz. So suppose the optimal knapsack solution does, in fact, make use of this final item, N. Now we want to talk about this being somehow composed of an optimal solution to a smaller sub problem. So if we're going to delete the last item, than we can't talk about S, right?'Cause that's has the last item. So we need to remove the last item from S before we talk about its optimality. That's analogous to back in the independence set problem, we removed the right most vertex from the optimal solution before talking about its optimality in a smaller sub problem. So the question then is, if we take capital S, the optimal solution. We remove item N. In what sense is the residual solution optimal, put differently for what kind of knapsack instance, if any is that an optimal solution for? Alright so the correct answer is C. So back in the independent set problem what we said is if we remove the right nosed vertex then what's left is optimal for the residual independent set problem again by plucking off the right most two vertices. Here when we remove the inth item from the optimal solution S, the claim is what we get is optimal for the nap sack problem. Involving the first n minus one items and a residual knapsack capacity of capital W minus little w sub n. So the overall, the original knapsack capacity with space reserved or deleted for the nth item. So before I give you a quick proof, let me just briefly explain why a couple of the other answers are not correct. so first of all, answer B, I hope you can rule out quickly it just doesn't type check, so capital W that's the knapsack capacity, so that's in units of size. Eh, little v sevin, that's the items value, that's in dollars, so it doesn't really make sense to talk about the difference between those two. They're just, it's apples and oranges. part D, if you're worried about feasibility at any point, so if you take capital S and remove the Nth item, what have you done, you've taken a set of items who's, you know, size was at most capital W by feasibility of S and you've removed an item with size Wn from it, so what remains has total size of most capital W minus little w sub n. So, s and minus n would indeed be feasible for this reduced this residual knapsack capacity capital W minus little w sub n. A much more subtle point is part A. That's a very natural one to guess. that turns out to not be correct. So it turns out there might be smarter ways of using the first N minus one items. Then S minus item N, if you had a full knapsack of capacity of capital W to work with. So that's a subtler point, and it's a good exercise for you to actually convince yourself that A is wrong, and that there's no reason that when you take out item N from S, and you still keep using the original knapsack capacity, that this has to be optimal. That's not going to be true. Alright, so why is capital C correct? Well this is going to have the same spirit of case two, of our weighted independence set thought experiment. So let me give you the proof. The proof is going to be the usual contradiction analogous to case two of our argument in the weighted independent set problem. So suppose there was something better than S with N removed with the residual capacity W minus w sub n, call that supposedly better solution S star. So what can we do to get a contradiction? Well let's just take S star, which involves only the first n minus one items. Let's add item n to it. Since S star has total size of most capital W minus w should n and item N has size W sub N. The results has total size at most capital W. So the feasible solution to take S star and extend it by item number N. And if S star had more value than S with n removed, then S star with N included has more value than S. So, for example, if S had total value, 1,100, 100 of which was coming from the nth item. Then S would end removed, had value 1,000. If S star was better, it had a value, 1,050. Well, then we just put N back in. And it has value 1,150, which contradicts the purported optimality of S star, which had total value, merely 1,100. So, notice what's going on here. So, in taking away W sub N for the knapsack capacity. Before we look at, the residual problem. We're, in effect, reserving a buffer for item N, if we ever need it, that's how we know we're feasible when we stick N back into this solution as star. That's analogous to deleting the penultimate vertex of the path, again as a buffer to ensure feasibility when we include the Nth vertex back in the independent set problem. So what was the point of this whole thought experiment, which we've now completed? Well, again, the point was to say, the optimal solution, whatever it is, it has to have only one of two forms. We've narrowed the list of candidates down to two possibilities. Either you just inherit the optimal solution with one less item in the same knapsack capacity, or you look at the optimal solution with one less item and less knapsack capacity by W sub N and you extend that by item N. But those are the only two possibilities. So, again, if we only knew which of these two cases were true, if we only knew whether or not item N was in the optimal solution or not, in some sense we could recursively compute the rest of the solution. So just as that was enough to get us going with a dynamic programming algorithm for weighted independent sets, so it goes with knapsack, as I'll show you on the next video.