So, what I'm going to do is basically com, be completely outrageous.

I'm going to assume that I can solve all the sub problems

for a capacity k, any capacity k and j minus one item.

So, I have this oracle, okay?

Delphi oracle that's going to tell me the optimal value

for these two, fo, for all these things, okay?

I'm assume that I'm basically given this, okay?

So that's the oracle that I have.

And then I can query. I can always ask: Ooo,

what is the value for the j minus one item for this particular capacity.

And I can query this oracle and get this value.

Okay?

So the next, usually what I want to do now is add one tiny little item, okay?

O(k,j).

So I know how to compute O O(k,j-1) for any value of

k, and what I want to do now is compute O(k,j) for all

the values of k as well, okay?

I'm just considering one item, and you're going to see

it's pretty simple what you have to do, okay?

So the first thing you have to do Is to find out if that particular

item, if you have a capacity k, if

that particular item can fit inside and outside.

If it's weight is lower down than the capacity k.

If this is the case, then there are two

other, there are two cases that you need to consider.

The first one is, whether you are right to be selecting the item or not.

Okay. If whether you are selecting the item.

If you don't select the item, the value that you get is simply

the value of the item with the same capacity and j minus 1 item.

Okay? And we have the O record to compute that.

That's the value that you see there.

Okay?

So if the item fits and we decide not to select

it, what you get is Is basically O(k,j) minus 1, okay?

Now, you can select the item.

Okay?

Because we know that it fits and in that particular case,

what is the value that you get? Okay?

You get obviously the value of the item because you put

it inside the knapsack and then you get the value, the optimal

value that you can get by using the g minus 1 item

and the capacity which is obtained by removing the weight from k.

Okay the weight of the item you just selected and

as this expression that you say, that you see here.

Is v j plus the value of a k w,

you know, let me, let me start out again.

It's the value of vj which is the value of

the item, and then o, you know, call this orecorsursivly

with the value of the capacity k minus the weight

of the item, wj, and then obviously j minus one item.

And so these are the two things that you can do if the item fits in the knapsack.

If the item doesn't fit in the knapsack, what do you have?

Well, you are, you are only left with the value

of the j minus one item and the same capacity k.

Okay?

So we can build this beautiful recurrence relationship here, okay?

Which consider the capacity k and j item and you

basically re-express it as a maximum between these two value.

If the act, if the item can fit inside

the knapsack, and otherwise it's simply the same val,

the, the same the, the, is basically the same

value as you would get If you use only j

minus 1 item, okay?

So you have this beautiful recurrence relationship, finding the best case when

the item can fit whether you select or you don't select the item.

Or if the item doesn't fit you just, you know, end the

value that you could do with the j minus 1 item, okay?

And of course you have to start from where, if the

capacity is zero There is no item that you can put

in the [UNKNOWN] and what I am basically climbing is that

if you have these swings okay, you can compute the optimal value

of the [UNKNOWN] and which item you need to select okay.

How do you do that?

Well let me show you.

This is a very simple c program or Python

program, you can derive the same thing in Python to

do actually that because you know where computer science

is just computing this Oracle for you for free okay?

So you see basically O(k,j), okay and that's the function that we're defining

here obviously if j is equal to zero there are no item okay?

There is nothing you can do, therefore the value is zero.

Otherwise you look at the item j and whether it fits or not

in, in the knapsack, okay so you have the capacity k, you have w

j, if it fits in the knapsack what you have to do the

optimum value of the knapsack is going to be the max of this expression.

Okay?

And once again this consider the two cases that I have discussed before, and

otherwise if it doesn't fit you simply

come, you know, call the function recursively.

That's the oracle, right?

With one fewer item in the same capacity, okay?

That program is actually computing the optimal value for the knapsack, okay?

Now one question that I have for you is that, is this actually efficient?

Okay?

Can you tell me how efficient this algorithm is?

Okay?

And let me use an analogy here.

This is, what I am going to show you here

is a program for computing Fibonacci numbers and it's basically

the same structure, a little bit simpler, than

what I've shown you for the knapsack problem, okay?

If you want to compute a value of the fibona, the fibonacci number of n, Okay?

if n is equal to one Okay, the value is

one, and otherwise if the value that you obtain by computing

the Fibonacci of n minus one, then minus two and

then adding that to the Fibonacci of n minus one Okay.

That's how you can compute Fibonacci number, and

I have the same question for you right,

is this efficient or not Okay, and what you can see here

is that okay, so if you want to compute when you look at

this one, the value of Fibonacci n minus one What will you have,

what, what do you have to do to actually compute that value, right?

So you're going to compute this function and you're going to compute Fibonacci

of n minus 2 and n minus 3, but you just

have computed Fibonacci n minus 2 and for computing that you

have computed the Fibonacci of n minus 3 and n minus 4.

So yeah,

basically, we are computing many, many, many times the same values, okay?

So this program is actually very, very, very inefficient, okay?

You never want to use anything like that, okay?

And why?

Because in this particular case, it's top-down

and we are not doing anything fancy.

Okay?

So what I'm going to do is take the exactly the

opposite approach and we're going to do a bottom up computation.

Okay.

So we're going to start with zero item.

And that's what dynamic programming does. Right?

We start with zero item.

And then, as I've shown you before we're going put one more item and

then two more items and so on until we have selected all the items.

Okay.

So in a sense, look at this program here.

This is the program that I'm going to use in the next couple of slides.

The first thing we going to do is oh we going to

look at what you can do with one, with zero item.

Then one item, and then two item, and then three items.

That's what we are trying to do here, okay?

We are going to solve these very simple

sub problems.

They are very simple and then we going to build on top

of them by adding one more item at a time, okay?

And you going to see, it's beautiful.

Okay, so this is, and so, when you

think about dynamic programming, you can, you know, a

lot of people think about tables, and I'm going to

show you the table intuition of dynamic programming, okay?

So you start with zero items.

How much value can you get? If you have 0 item, okay?

The value that you get is 0, right? So, there is nothing to

take, okay?

Now, we are looking at one item and assume that this item

as a value which is 5 and a capacity which is 4.

Until you have a capacity which exceed you know, which exceeds

Three, which exceeds 3, then there is nothing you can get.

You get no value. Right?

And then, essentially, as soon as the capacity is

4, you can get the value of the item.

So this is amazingly simple, right?

So we have one item, okay?

Now let's look at what happens if we have two items.

To get a new item there, its value is 6 and its weight is 5.

Okay?

And once again until you get one item that can fit in the knapsack you get nothing.

So initially you get all these zeroes, and then

you get to the point where the capacity is 4.

When the capacity is four you could get the first item.

So you get a five, okay? When the capacity is 5 what do you get?

Well you can select the second item which is more valuable, okay?

And that's what you get

there, until the point where the two items actually fit

inside your knapsack and you get a value of 11.

Okay, so there's the second column, okay?

So two items.

Now we going to build on this second column to actually build the case

where there are three items, and this

is where things start becoming more interesting.

You can see that the weight of this guy is 2, its value is 3, okay?

So As long as we don't have at least

two units of capacity, there is nothing you can do.

Okay? When we have two

units, we get basically, this item, the, the third item,

3, and this is where things really start getting interesting.

Okay, so in this particular case When you have a capacity of

4, there are two items that are fitting in the knapsack, right?

So this guy fits in the knapsack and you can decide to take it or not to take it.

If you don't take it, what happens?

Well, you get the value that you would have, that,

that you, that you had when you select only the first

two item. Okay?

So, you know that you will at least get value five, okay?

Because if you don't do anything, you don't

select the item 3, you get the value 5.

But now you have also the possibility of selecting this guy.

If you select this guy, you get its value which is 3 in this particular case,

but then you also have a non-empty you

know, capacity for the knapsack in this particular case.