0:00

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.

Â