In this video, we'll develop our second dynamic programming solution for the knapsack problem. Why do we need a second algorithm? Well, it's a crucial building block in our heuristic that achieves arbitrarily close approximation to the knapsack problem in polynomial time. Recall that in the knapsack problem, the input is 2n+1 numbers. There's n items, each one has a positive value, Vi, and a positive size, Wi. Additionally, we're given a knapsack capacity, capital W. Back in the dynamic programming section of this course, we already devised an algorithm for this problem. That algorithm assumed that the item sizes were integral and also that the knapsack capacity is an integer. The running time of that dynamic programming algorithm was O(n), the number of items, times capital W, the knapsack capacity. In particular, we get a polynomial time algorithm for the special case of knapsack when the knapsack capacity is not too big, when it's polynomial in n. It turns out that this is not the right special case on which to build an algorithm which has arbitrarily good approximation in polynomial time. Rather, for that kind of heuristic, what we really want is a polynomial time solution for the special case where item values are small, that is precisely the solution that we're going to provide in this video. We will be assuming that the integer values are all integers. The sizes of the knapsack capacity can be whatever and the dynamic program solution that we developed will have running time. Big O of n^2 times Vmax. Vmax here denotes the maximum value of any item. The running times of the two algorithms are more in parallel than the notation might suggest. Probably, it looks like there's an extra factor of n in the second dynamic programming algorithm, but that's the wrong way to think. Think, for the first algorithm, think of w as an upper bound on the largest total size that a feasible solution might possess. In the second algorithm, think of n times Vmax as an upper bound on the maximum total value that any feasible solution might possess. In the first algorithm, we're focused on size, in the second algorithm, we're focused on value, and in any other case, the running time is the maximum quantity that we have to worry about times the number of items, n. Now, since all of you are survivors of my dynamic programming boot camp, I don't feel the need to develop this solution in great detail, let me just jump to the relevant subproblems. So the subproblems here will be a twist on the ones that we used in our first dynamic programming algorithm for knapsack. The part that's going to be exactly the same is we're going to have an index i, i specifies which prefix of items we're permitted to use in a given subproblem. Now, in general, in the knapsack problem, you're simultaneously trying to get the value high while keeping the weight small. So the way we organized things in our first dynamic programming algorithm is the second index into a subproblem specified the residual capacity x that we were allowed to use, and then, while respecting that capacity x, we asked for the largest value that we could obtain just using the first I, items. Here, we're going to turn that on its head. We're going to have a second parameter x, which is the value that we're striving for. So we want to get value x or more and we're going to try to minimize the total size that we need to use subjects to getting the value at least x. So the first index, i, arranges as usual from 0 to n, this corresponds to all the prefixes of items you might be interested in. The second parameter, x, ranges over all of the targets for total value that you might be interested in. Now, remember, we're assuming in this video, that every item value is an integer, so that means any subset of items will have an integral total value so we only need to worry about integer values of x. In addition, we never need to worry about trying to achieve a total value bigger than n, the number of items, times v max, the largest value of any item. In fact, you could replace this upward value n times Vmax by the sub of the vi's if you prefer. So if we're given choice of i and x, [COUGH] I'm going to use capital S sub i,x to denote the optimal value of that corresponding subproblem. So, that is, the minimum weight, the minimum total size that is sufficient to achieve a total value of x or more while being restricted to using just the first i items. If there is in fact no way to get the target value of x using just the first i items, that is if the sum of the values of these items is already less than x, we just define this to be plus infinity. So let's write down the natural occurrence. Let's assume here that i is at least 1. So, the structure here is going to be exactly the same as it was in our first dynamic programming algorithm for the knapsack problem. Specifically, let's focus on a subproblem with a choice of i and a choice of x. That final item i is either in this optimal solution for the subproblem or it's not. That gives us two cases and the recurrence is just going to do brute-force search over the two case, because we're trying to minimize the total size required to achieve a given value target, here, the brute-force search is going to take the form of a minimum. What are the two candidates for an optimal solution? Well, the boring one is when you don't even bother to use item i, then of course, you just inherit an optimal solution, a minimum sized solution using just the first i-1 items achieving the same value target x. On the other hand, suppose that in an optimal soluton to the subproblem, you do actually use item i. Well, this contributes to the size of item i to the weight of this optimal solution. So that's going to be w sub i. What can we say about the rest of the items in this optimal solution? Well, because the solution here achieves a value target of x, the items in this solution other than i, must be achieving by themselves a value target of x minus v sub i. And, of course, by the usual cut and paste argument amongst all subsets of the first i-1 items with that property, they better will have the minimum total weight. So one quick edge case in this second case, if vi is actually bigger than x and we have a negative index here, we just interpret this quantity as 0, that's because item i alone meets the value target of x. Let's now wrap things up with the pseudocode of the new dynamic programming algorithm. So A will be our usual table. It has two dimensions, because subproblems are indexed by two parameters, i, the prefix that ranges from 0 to n, and x, the value target that ranges from 0 to, to the maximum imaginable value, let's say n times Vax. So the base case is when i equal 0, that is, you're not allowed to use any items. In this case, we have to fill it in with plus infinity. Well, except if x itself is 0, then the answer is 0. Now, we just populate the table using the recurrence in a double for loop. The structure here is exactly the same as in our first knapsack dynamic programming algorithm. In the first dynamic programming solution that we developed for knapsack, we could return the correct answer in constant time given the filled-in table. That's because of one of the subproblems in that dynamic programming algorithm, literally was the original problem. When i=n and x is equal to the full map sack capacity capital W, the responsibility of that subproblem was to compute the max value solution subject to the capacity capital W using all of the items, that's literally the original problem. By contrast, in this dynamic programming algorithm, none of the subproblems are literally the original problem that we wanted to solve. In this new dynamic programming algorithm, however, none of the subproblems correspond directly to the original problem that we wanted to solve, none of them tell you the maximum value of a feasible solution. To see why, let's inspect the largest batch of subproblems. When i is equal to n and you can use whatever subset of items that you want. The second index of one of these problems is a target value x. That might be a number, like say 17,231. So after you've run this algorithm and you've filled in the whole table, what do you know in this subproblem? You will have computed the smallest total size of a bunch, bunch of items that has total value at least 17,231. So that's going to be some number, maybe it's 11,298. But, what if your knapsack capacity's only 10,000? Then, this is not a feasible solution, so it doesn't do you any good. Okay, well that's not quite true, it does do you some good. If you know that every single solution that gets value 17,231 or more has size bigger than your knapsack capacity, well then, you know that the optimal solution has to be less than 17,231. There is no feasible way to get a total value that high. Now, you realize that if you knew this information for every single target value x, and you do once you've filled in the entire table, that's sufficient to figure out the optimal solution, figure out the biggest value of a feasible solution. All you need to do is scan through this final batch of subproblems. You begin with the largest conceivable target value x, and then you get less and less ambitious as you keep finding infeasible solutions. So you scan from high target values to low target values and you're looking for the first that is the largest target value x, such that there exists a subset of items meeting that target value whose total size is at most your knapsack capacity. That is going to be the optimal solution, that first target value x, that can be physically met given your knapsack is at capacity. Analyzing the running time is straightforward, so how many subproblems are there, or equivalently, how many iterations of a double for loop do we have? Well, it's n outer iterations, then n times Vmax inner iterations, so that's n^2 Vmax overall. Our brute-force searches over only two candidates, so we only do constant work per iteration of the double for loop. In the final line, we do a scan through the largest batch of subproblems, so that's O of n times Vmax. So the running time is dominated just by the constant work per subproblem, and so, our overall running time is O of n squared times Vmax, as promised.