First, we have a certain number of items.

Let's say we have n items or five.

In this case.

Five items on each atom has an associated weight on value with it.

So the first item Ways Mont program on is $5 on the second night in ways to co grams on its worth.

$3.

And the problem is, we're trying to decide which items to put in our knapsack, which can only carry a certain amount of weight.

Let's say 10 kilograms, we can only carry tank your grams, and we're trying to maximize the total the total amount of value that we carry with those items.

So for each item, we're gonna decide, Do we put it in the knapsack or outside the knapsack?

So let's just say yes or no, or we could write it as one if it's in knapsack or no, If it's not in the knapsack on a first class, he looks very hard because if we make this decision for every item, the total number of solutions the total number of potential solutions is gonna be to do the part friend or two to the par off five in this case.

But actually we can do much better than that with dynamic programming on you.

See how you can do it in a second.

Here's a common procedure in dynamic programming.

We first come out with a recursive solution, and then we memorized or store some of the intermediate results to make you run faster.

The third optional step is coming up with a bottom up approach.

But I'm not gonna do that.

Just forcing police.

It is sick for this particular case.

So here's our naive recursive solution.

The idea is we're going to start with the last item.

We're gonna move down the list and we ask ourselves for where the pointers are we gonna put this item in the knapsack or not?

So for the first gentleman, of course, that's yes and no.

And we'll also keep track of how many items we have left to consider.

Or you can see as the position of the pointer as well.

So it starts with wife on.

We'll keep track off the amount of capacity we have left that starts with 10 in our example, 10 kilograms on the value we have so far that starts with zero on.

If he said no for the first item or the last item, this item then and becomes four.

We're essentially moving this pointer to the left, so that becomes four and see capacity doesn't change.

So that's 10 and the value doesn't change, so that's still zero.

And if he said yes and becomes four way have four items left to consider, the capacity becomes 10 minus five.

Eco's five.

We can still carry Thio five kilograms on the value becomes they're plus two egos, too.

And for each decision, we are sick ourselves for the fourth item.

Are we going to put this in the knapsack or not?

So that's yes, I know again.

So would keep repeating this process until we get to the last item.

This one.

So that's the idea behind our recursive solution, but it works slightly differently in the code, so let's see how that works.

So here's how a recursive solution works In our code.

We define dysfunction, chaos, knapsack that takes two variables.

The first viable is the position of the pointer that we're looking at or the number of items we have left to consider.

And the second variable is the amount of capacity we have.

Let's so the first call for this example is going to be kiss off five because we have five items left to consider and 10 because we have 10 kilograms in our capacity.

And here's our base case, if any, co zero.

That means we have no items left to consider and IFC called zero.

We don't have any capacity, so we just return zero.

And from this function we're returning the optimal value that we can achieve with this pair of variables instead off the list of items itself.

So if you want to do that, you'll need to change the code a little bit.

Now, if the current items Wade is larger than our current capacity, then we can't put it there.

So we just moved there, pointer to the let and we call this function again.

And if that's not the case, will try both put in the item in the knapsack.

I'm not putting it there, so if we don't put the item in the knapsack than we just called the same function with the same variables again with the pointer moved to the left.

And if we put it, there, will count in the current item's value, and we'll add it to this recursive call.

Where the pointer is moved to the left on the capacity left is reduced by the current items.

Wait, and we'll just take the maximum one of those to get the optimal value.

By the way, our values are stored in this array that starts with a dummy viable on our actual values.

So that's 53 532 And the reason is because when we have say the second element weekend, just call V of two on, we get the right element, the right value on it, the same thing with the weights.

So it also starts with dummy viable and then actual waits.

So this is how our solution works.

But it's very, very slow on.

Let's see why that is, if you think about the worst case scenario would try, for the last seven would try yes or no, and then for the second last sermon will try.

But in that item in there, I'm not putting in there and sewn.

So we're basically trying every possible case.

So the time complexity for this are gonna them will be exponential, which is very bad, dynamic program, he says.

We can do better than that by memorizing or storing some intermediate results or by noticing that there are some duplicates in our competition.

So here's how we can do it.

We have here a function that's almost exactly the same as what we had earlier, except for these three lines on the first thing to notice here with the previous function we had is that they're on Lee n times see possible variable pairs that we could have.

So in the example we had earlier, this would be just 10 times five times 10 which is 50 possible viable pears.

And what we're doing here is we're storing the results of this function in a two dimensional ray with the height and and with C on dhe re initialize it too undefined the outside function.

And then when we call this function, if the result is already stored for the particular viable pair, then we just returned that instead of going through the whole thing.

And if that's not the case will go through the whole thing on before we return.

The result will store it in the array so we can reuse it later.

So what's the wrong time for this function?

The first thing to notice to find that is that we reached this line on Lee.

Most end time see times.

So we go through this whole thing a most and time see times and every time we go through this function, the maximum number of recursive calls we make is just twice in this case, this one and this one.

So the maximum number of times we call this function itself is about two times and see, or just on order off N.

C on the time it takes to execute each call or time per call is just a constant time.

So the total amount of time it takes to execute this whole thing is just an order off N.

C, which is much, much better than the exponential time of complexity we had earlier.

All right, hopefully you like the video.

You might also like my other video about dynamic programming with maximums of sequence as our example on.