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.