Hi, everyone, welcome to this new video.
So in this video, we are going to discuss the most important question of dynamic programming, which
is 01 knapsack.
So let me try to explain.
What is the question?
So there is one thing I've learned over and the thief wants to steal the item.
So Thief has of it has a knapsack and the weight of the knapsack is engaging.
And these are the food items that is present.
Right.
So a number of items are food.
And this is the weight of each item.
So this is one weights.
So these are bits of each item and these are the prices of the item.
Right.
So this is price.
So our aim is to do what he wants to do.
He wants to maximize profit.
Right.
He wants to maximize profit given he has a knapsack with ten kids only.
So what we need to do, we need to help Steve here and we need to maximize the profit of Steve.
So I hope you have understood this discussion.
And these are items to focus on his ball, second on his apple, third on his banana, and the fourth
one is, let's say, orange.
So how are we going to solve this question?
So it's very simple.
We're told we will use recursion.
So how it will help us here.
So let's talk about this item first.
Let's talk about this item.
Let's try to see how we can solve this.
So the weight of this item is 15 gidgee.
The weight of knapsack is 10 gidgee.
So we cannot pick this item rate.
The item weight is greater than the knapsack weight.
So you cannot pick this item.
So we are discussing one very important condition here, that if the weight of the item.
So we have so this is four and the index is three.
So we are discussing one important condition of the weight of the item is then the knapsack with.
Then you cannot pick this item, right, in that case, it will do we will call the question on the
rest of the items and the question will give us the maximum profit.
So our answer will be our answer will be called recursion.
So let's say the name of the function is knapsack.
So you need to call the rest of the items basically three items, so called the recursion on the rest
of the items.
Fine.
Now let's change the weight.
So let's say instead of 15 gidgee, if the weight of the item is, let's say, six gidgee light, the
weight of item is six gidgee.
Now let's discuss about this item.
So what will happen now?
This item has a very thick skin and the weight of the knapsack is engaging, so I can pick this item
right.
So I have two options here.
Pick this item and try to maximize your profit.
Do not pick this item and try to maximize your profit.
So this is the condition we are, including the item we are picking the item and we are not picking
the item, we are excluding the item, right.
So we are excluding the item and everything myself.
See, the weight of this item is sketchy and the weight of knapsack is engaging.
So I can pick this item, but it is not necessary that I will pick this item.
Right.
It's my choice.
But I can pick this item or do not pick this item right?
Our ultimate goal is to maximize the profit.
So what I'm going to do is I will consider both the cases.
I will consider both cases the case when I am, including the item when I'm picking the item, the case
when I am not, including the item.
Right.
And we will see which case gives us the maximum profit.
So in case, if I am including this item, what will be my answer?
My answer will be I'm including this item.
So the price that I will give, the money that I will gain my profit will be rupees sixty dollars 60
plus.
After picking this item, after you have picked this item, what you need to do, you need to call recursion
on the rest of the items.
Right.
To find out the maximum profit for the rest of the items.
So we need to call recursion.
On the rest of the items, but one more thing now, the weight of your knapsack has become full because
you are including this item and the weight of this item is cagy.
So 10 minus six, that will become four.
So what you need to do so here, in this case, the weight will not change because you cannot pick this
item.
Weight of your knapsack will change.
This is very different.
So in this case, the weight of knapsack will not change, but in this case, the weight of knapsack
will change.
So weird.
Minus six right now.
Your knapsack has a very tough for now in the case.
When I'm excluding this item, when I do not when I'm not picking this item and I'm trying to maximize
the profit.
So in that case, what you will do, what will be your answer?
Your answer will be zero, because you are not picking this item and you will call Dacogen on these
items.
Right.
You will collect on these items rest of the items.
So knapsack, which is our recursive function, the number of items get reduced by one because you are
not picking this item and the weight of knapsack will remain same.
Right.
So what we will do after finding the value for these two, including and excluding what we will do,
we need to take the maximum out of them.
We will take the maximum of include and exclude.
Right will take the maximum because our ultimate goal is to maximize the profit.
So I am calculating the profit when I am including this item, I am calculating the profit when I am
excluding this item.
So that's why I will take the maximum of them.
And that will be my final answer.
Right, so we know all the records.
This is the first recorded evolution when the item where is good and upset with this is the second recorded
revelation when you can pick this item and you are picking the item.
This is the third quarter when you can pick the item, but you are not picking this item.
Right.
And finally, that makes some of these to include gays and exclude a case.
That will be your final answer.
Right, working with a biscuit's.
Let's talk about this case.
So in this case, if the number of items is zero, base case number of items is zero.
We do not have any item.
What would be your profit?
Your profit will be zero if you do not have items to pick.
Then how we can pick the item.
Item does not exist.
So your answer will be zero.
Your profit will be zero.
Similarly, if the weight of the knapsack is zero, the weight of knapsack is zero, you cannot pick
any item.
So in that case, also your profit will be zero.
So these two are the best cases.
Simple, right?
So we now have base case.
We now have recursive case.
Let's start writing the code.
So this problem is basically present on a bit rate zero one knapsack.
Oh.
So one thing that I forgot to explain is what do we mean by zero and one so.
Zero one means here we have written, so zero one means you cannot break diatom, either you will pick
the complete item or you will not pick the item, right.
So it will not happen.
Like you have an apple.
And the cost of Apple is basically, let's say price of item is twenty two hundred dollars and it is
five Gadge.
So and the knapsack rate is two point five Kaju.
So it cannot happen.
Like you will break the apple into half and you take half of it.
No that is not allowed.
So either you pick the complete item or do not pick the item, but you cannot break the items.
Right.
So that is the meaning of a zero one here.
So let's see, let's try to ride the recursive call for this problem.
So these are a few examples given at a ribbon, so the naming is difficult, so is the weight of the
knapsack.
This is the weight of each of the item and this is the price of each of the item.
So the first thing is, let's rename the vector is nothing.
But this is your price at the price of each item.
What is vector be your vector B's veered off each item, right, and what is in Jersey?
So this is the total weight of the knapsack.
Right.
So, as discussed, what we are going to do is we are going to write one knapsack function, so knapsack
function.
This network function, what it will take, it will take how many number of items out there?
That is price, not size or village, not size.
So that will be same.
That is the number of items.
Second is it will take what is the weight of the knapsack?
It will take your place area and it will take your word said.
Fine, so let's write.
Their definition of the function knapsack, this function will return as the maximum profit rate, the
maximum profit.
So how many items are there?
Second, what is the weight of the knapsack?
That is, what is the price of each item?
What is the price of each item?
So vector and price price.
And what is the weight of each item?
So we're adding.
Fine, best case, so the best case that we discussed was if the number of items is zero.
Number of items is zero, Battalia, maximum profit, if you do not have item to pick, then you cannot
pick anything.
So in that case, your profit will be zero simple and other businesses can be if the weight of knapsack
is zero, if the weight of knapsack is zero, you cannot pick any item.
So your profit will be zero.
Simple.
Well, what we can do, we can grab these two conditions here.
So if the number of items is zero or the weight of knapsack is zero, then your profit will be zero.
Now, let's talk about the recursive case, so the first case is basically if the weight of item is
the weight of item is greater than the weight of knapsack, then you cannot pick this item.
So in that case, where you going to do is we will simply call the recursion on the rest of the items.
We are simply calling recursion on the rest of the items.
So a number of items will reduce by one because we cannot pick this item right.
So the knapsack will remain same then the price area, then the witchetty.
So what is this condition?
So if you see here I am talking about this condition, if the weight of the item is lower than the knapsack
weight, for example, if let's say this is 20, so if the weight of the item 20 is greater than the
weight of knapsack, then you cannot pick this item and you will collocation on this part.
So call the equation on a number of items will get reduced by one because you cannot pick this item
and the weight of the knapsack will remain the same.
So that is what I am doing here.
Right.
So if the weight of item is lower than the weight of knapsack, then call that equation on the rest
of the items.
So number of items will get reduced by one.
And this is your price area and you're very steady.
Now, if this is not the condition in the part.
In the early part, you see we have two options here.
If the word is, let's say, six kids, so I have two options here, I can include this item and try
to maximize my profit, exclude this item, and I will try to maximize my profit.
So after including and excluding the maximum profit that I will get will be the maximum of both of them.
So what we need to do, I have option here that I did include this item and find out the maximum profit,
I did include this item and find out the maximum profit or exclude this item and find out your maximum
profit.
So exclude the item and find out the maximum profit, right, and what will be your answer, your answer
will be make them off the maximum profit that you can get by, including the item or by excluding the
item.
Now, what we need to do, we need to find out the value of include and exclude.
So what will be the value of include?
Let's first talk about include, right, including the item.
See if you include the item, for example, I am including this item, so 60, my profit will be 60.
I am taking this item so I will get a profit of 60.
So what is this, 60?
This is your price at.
Right.
So the price of the item, the price of the item, plus the collocation on the rest of the items.
Right.
So.
Place of and minus one, great plus, we need to call the on a list of the items so knapsack number
of items will get reduced by one because you have picked this item also since you have picked this item,
since we are picking this item, the weight of this item was six CGY and the weight of knapsack was
langauges or 10 minus six for the weight of a knapsack will decrease, the weight of your knapsack will
decrease.
So the weight of knapsack will become the total weight minus the weight of this item find.
But said will remain same, where today will remain same.
So this is the record for including item.
Let's talk about excluding the item when you are not picking this item.
So when you are not picking this item, you will get zero profit because you are not picking item.
Plus, you are calling the equation on the rest of the items, the rest of the three items.
Right.
Calling the equation on just of the three items and your knapsack rate will remain same because you
are not picking the element or picking the item.
So simply you are calling the recursion.
So a number of items will get reduced by one because you are not picking this item, the knapsack which
will remain same because you are not picking the item and that is your price area and that is your way.
It's very simple, right?
That is the complete code.
So let's test our code and then we will submit.
So our goal is passing basic test cases.
Now let's try to submit our code so most really what will happen, our code will encounter random sorry,
not runtime error.
The time limit exceeded because our solution is recursive and right.
So we are getting time limit to delay.
Right.
So and that was pretty obvious.
So this is recursive solution.
So that's why we are getting excited.
Now, what do you want to do is in the next video we will convert this recursive solution into a solution,
right?
It will, right.
The Dynamic Programming Board will convert this recursive coding to binding programming code.
So one more thing that I want to discuss before ending this video is basically so here.
What I'm assuming we are assuming that we have only one Apple, we have only one banana, we have only
one orange.
We have only one bowl.
And if I'm picking the apple, then I cannot pick Apple again later.
So here our inception in this question is we have one copy of each item made, one copy of each item.
Now let's see if we have infinite apple, we have infinite orange.
We have infinite bananas and we have infinite balls.
So what will happen, let's say, if your TV is basically going into an Apple store?
So there will be many laptops of exact same configurations.
So basically in this question that I want to say, it is let's say I am modifying this question, do
we have infinite we have infinite copies of each item, right?
We have infinite apples.
We have infinite range between finite bananas.
We have infinite balls.
So what I want to say here is if I am picking the item once, then here I am doing I cannot pick the
item twice the rate.
I can pick the item only once, but since now we have infinite copy of each item so I can pick one item
more than one time.
Right.
So how we are going to modify this code for solving this problem when we have infinite copy.
So it's pretty simple.
What we are going to do is this is basically when you cannot pick this item, this is basically when
you are not picking this item and this is the only recursive relation where you are picking the item.
So what you are doing after picking the item, you're calling it because the rest of the items we are
calling recursion on the rest of the item, and that is wrong.
This condition has to be changed when we have infinite copy.
So what do we do?
We will not call the question on rest of the items.
We will call recursion on all of the items.
So for infinite copy, if you encounter one question and the question mentioned that you have infinite
copy of each item, you can pick one item more than one times, basically infinite number of times.
So the only change that you need to do in this code is basically, instead of calling that equation
and minus one, you will call recursion on.
And that is the only change that you need to do in this question for basically this infinite copy.
Right.
So, yeah, that's the last thing that I want to discuss about this question, the recursive code.
So in the next three days or we will try to write the dining programming code for this problem.
So this is all about this video.
I will see you in the next one.
Thank you.