[MUSIC] In the previous lesson, I introduced the Knapsack problem to you. In this lesson, we're going to develop an algorithm for the knapsack problem which is exact. So not an approximation but an exact algorithm. But for the special case where all the input values are integers. So let's first review the basic notation that we use to specify the problem. So we have sex X of items, n items, and each item has a weight, which is positive and the value. And here you see the notation for these concepts. And we also have a value W which is the maximum weight we want to carry. So in other words, what we want to do, what we want to achieve is to select a subset of the items. Such that the total weight of the subset is at most W, and the value of the subset is as large as possible. Okay, and as I said, we're going to develop an exact algorithm for this. So we're going to prove the following theorem. When all of the items have integer values, then we can compute an optimal solution. And the running time of our algorithm will be n the number of items times the total value of all the items in our set. So this is the goal, this is what we want to prove in this lesson, okay. Let's introduce a little bit more notation. So if we have a subset S of our set X of items, then by value of S, i simply denote the total value of tall the items in the subset S. And weight of S is defined in a similar way. I also need the notation S of i which is the sub set of the first I items, right. So we have items X1, X2, all the way up to Xn. And Si are the items X one up to Xi. And it will be convenient to use a zero to denote the empty sets. Okay, when you want to develop a dynamic programming algorithm and that's what we're going to do in this lesson, then we always need to define suitable sub problems. So here, the subproblems are specified by two parameters, i and j. And by A of i, j, I will denote the value of the optimal solution for this particular subproblem. So let's look at this in a little bit more detail. So A[i,j] is the minimum weight of any subset of the first i items, right? So the minimum weight of any subset of Si such that the total value of the subset is exactly j. Okay, and we're going to define this for i between 0 and n, and j between 0 and the total value of all the items together, okay? And well, if, which could easily happen, there is no subset whose value is exactly j In that case, I define A [i,j ] to be infinity. Okay, so how does this table, if we can compute all these values A [i,j], how does it help us? Well, remember that what we want to compute is the maximum value of any subset whose weight at most W. Okay, now, suppose we have all these values A [i ,j] how does it help us? Well, this maximum value is the largest j such that A [n, j] is at most W, but why is this the case? Well, first of all, in our initial problem we are of course, allowed to select items from the whole subset, all right? From items X1 all the way up to Xn, so that's why we're interested in Sn, so that explains the n in A [n, j], okay? And now, what we want is a subset whose total weight is at most W. So we want A [n,j]to be at most W. And then, we want to have the largest value. So indeed, we want to have the largest j such that A [n,j] is at most W, okay, good? So this is what we want to compute. So the conclusion is that if we can compute all these values A [i, j], then we can solve our problem. And our dynamic programming, this method suggests to do this in the following way. First, we are going to develop a recursive formula for the values A[i, j], okay? Once we have such a recursive formula, we are going to compute all these values using this formula by filling in a table. And then, once we have the table, well, then we can easily find the largest j, such that A [n, j] is at most W. So that's the plan. So here, you see again this A [i ,j], the definition of A [i, j]. Now, let's do indeed the first step, which is to develop a recursive formula that specify the value. So our recursive formula is going to look something like this A [i, j] is. And then, we have a number of cases, some base cases in our recursive formula and the general case. So let's first look a little bit at base case. Okay, so the base case, one of the base cases is j = 0. So what would be the value when j = 0? Well, what does it mean? It means that we want to find a subset whose total value, right, is j is 0. Well, we can always do that by simply taking as a subset the empty set. Okay, and the empty set has weight 0. So for j = 0, we get a value of 0. So now, let's look at the case which is bigger than 0, but i is 0. Okay, what does it mean that i is 0? Well, remember that Si were the first i items, X1 up to Xi. And we defined this to be the empty set for i equals 0. Okay, so what do we get when i = 0? Well, we want to select something with a certain value j but from the empty set. Well, if j is bigger than 0, then from the empty sets we cannot select anything, so this is simply impossible. So that means that in this case, A [i, j] would be infinity. So the interesting case is of course when j is bigger than 0 and i is bigger than 0. So lets have a look at this case. Okay, so here you see a picture of Si, right? We want to select our subset from Si, and the question is, can we come up with a recursive formula that tells us what is the best way to select a subset of total value exactly j from Si? Well, there are two things we can do. If you look at the last item Xi, well there are two types of solutions you could say. The solutions that have Xi as part of the solution and the solutions that do not include Xi. And of course, the best solution is simply given by the best over these two options. So now, let's look at the option where we do not include Xi. Can we express A [i,j] using some recursive formula for the case where the solution does not include xi? Well, that's very simple, because if we do not include Xi, well, it simply means that to get exactly j. Well, we have to get value exactly j from the first i minus 1 items. So, in this case, A [i,j] is equal to A [i-1, j]. Okay, let's look at the other case. Suppose we do include Xi, well, in this case, what we get is, while we include Xi. So the remaining value that we must select from the first i-1 items is j, the value that we had to get in total, minus the value of Xi because we include xi in the subset. What's the minimum possible weight that we can get to do this? Well, that's the weight of Xi because we select it, we put it in our Knapsack. Plus the minimum weight that we get from the first i- 1, if we make a selection out of those, of total value j- value(xi). So also here, we have a nice recursive formulation for A [i, j]. There's one slight detail that we have to take into account, which is the following that, well, if we want to include Xi, that's only possible when the value of Xi is at most j, right? Because if in total we want to get value exactly j. We cannot include an i to move more than j because then it will no longer be possible to get a solution. So that leads to the following final formula that we get A[i, j] is well, we had two base cases, i = 0 or j = 0. And in the general case, when both are bigger than 0 we have two cases. One for where the value of Xi is bigger than j, in this case we're not allowed to include Xi and the value were simply A[i-1, j]. Or if the value of Xi is at most j, then we also have the option to include j, and then you get this other recursive formula. Okay, so this is nice and now, actually what we have is we already did the hard work, and given this recursive formula, things become pretty simple. So let's see how, based on this recursive formula, we can now write our algorithm, okay. So the algorithm is going to use dynamic programming, and that says that, what you may expect if you would not know about that dynamic programming, that you simply write a recursive algorithm. Because we have a recursion formula for A[ i, j]. But instead of that we're going to fill in a table. So let's see how that works. Okay, so here's my table. So in this table, I want to put all my values A [i, j], okay? We have our recourse of formula, so let's first look at the first base case. Well, if i=0, or sorry, if j=0 then the value is 0. So we can simply put all 0's here, okay? Second base case, when j is bigger than 0 but i is 0, then it's not feasible, so our values were infinity, okay? So now, we have the general case. So suppose I want to compute right here, one of these table entries, A [i, j]. If you look at the first of these two remaining cases, then what you see is to be able to compute this table entry. I will need this particular table entry, right, I need the entry with the same value of j but for i-1. Okay, in the other case, the fourth case then to compute this value, well, I also need the one right above it but I will also need another table entry which is also in the previous row, okay? If I already have these two values then in constant time I can compute my A [i, j], so things are pretty simple now. I simply go over the array in the order that you see here. So we go over the table in this order and then, when I get to any A [i j], what you will see is that we have all the values available that we need to compute this value. So in constant time, we can fill in this table entry and proceed to the next table entry. Okay, so remember that at the end after filling in the whole table, we wanted to know the largest j such that A[n,j] is at most W. Well, if we have computed all the values, this is pretty simple. We simply look at the bottom row of our table and there we find the largest j, such that this table entry is at most W. So what you can see is since for each entry in the table, I spent constant time. That in total in well, the running time is linear in the number of cells in this table, which is n the number of items, times the total value of all of these items, okay. So what I explained so far is how to compute the values in this table, which will give us the value of the solution, right? So it will go, it's going to tell us that, well the best subset that you can get has this total value. But of course, we would also like to know what is this particular subset that gives the optimal value. Well, in our standard way and I'm not going to explain that, you can read it in the course notes. In our standard way, you can actually transform the algorithm that you had just solved. Or I should rather say, add a post processing step that not only gives the value of the optimal solution but also gives the optimal solution itself. So that's nice, we have now proven the theorem that we set out to prove. When all the item values are integers, then we can solve the Knapsack problem in total time n times the total value of all the items. So in the next lesson, what we're going to do is we're going to look at the case where the values are not integers. And we're going to develop based on the theorem we just proved a PTAS for this problem [MUSIC]