Hi, everyone, welcome to this new video.
So in this video, what we are going to do is we are going to convert our recursive code into a dynamic
programming code.
So, first of all, let us first figure out whether our dynamic programming will be upgraded, appear
to be.
So here we can see a number of items changing in the current call and the way it is also changing in
direction.
So two things are changing in the casting call.
So that's why this is basically to really be so to Redzepi.
I mean, we need to create metrics to solve this problem, right.
So that is the meaning of the GDP.
So it's very simple to figure out whether a given problem will be solved by one dimensionality, one
or two dimensional debris.
You just need to figure out how many things are changing in your current goal.
So here two things are changing.
Number of items is changing and the weight of your knapsack is changing.
So that's why this is two dimensional dippie.
Right.
So we have figured out this is a two dimensional leap.
Now in this two dimensional leap.
Since a number of items is changing and we're talking about is changing, so at one side we will have
a number of items changing and here we will have the weight of your knapsack changing.
Right.
So we start from zero, so will start from zero.
So what deep of AIJA represent so what DPI, Gippsland, DPI represent the maximum profit that you can
earn by taking items.
And when the weight of your knapsack is the weight of your bag, is J.A.G., right?
So according to this definition, what will be our answer?
Our answer will be deep of any number of items and the total weight.
So what will be the value of this, the maximum profit that you can earn by considering any items?
That is the total number of items and considering the weight of your bag to be WTG.
Right.
And that is we need to figure out.
That will be our answer.
So our answer will be the value that we present at the last at this basically at this box, right in
this box.
Now, let's talk about biscuits.
So if the number of items is zero, so if the number of items is basically zero, then the profit will
be zero.
Similarly, if the weight of your bag, if the weight of your knapsack back is zero, then your profit
will be zero.
Right.
And for this, we have recursive relations so we can convert them easily into the code.
So now we have everything.
Let's start writing the code.
So first of all, let us figure out the number of items.
So a number of items is price, not size.
Right.
And let's command this line.
So we know the number of items and now we need to create one deepti of size and plus one and the blue
plus one word of an harpsichords W..
So this will be our two time period because things are changing.
And as discussed, my answer will be the payoff and the maximum profit that I can by considering a number
of items when the weight of my bag is W.
Now we need to fill this deep area.
So let's start iterating over this deputy to fill this area.
So let's do that.
Glastonbury, close to the weight of the is W and J plus plus.
So if the number of items is zero.
Or the weight of your bag is zero in that case, what will be your profit?
Your profit will be zero.
This is the best case.
Your profit is going to be zero, right?
In the elusive part.
Let's talk about the second condition, right.
This one, if the weight of the item is greater than the weight of the knapsack.
So if the weight of the item, if the weight of item is greater than the weight of knapsack, in that
case, you cannot pick this item.
So what will be your answer?
Your answer will be, since we cannot pick this item so DPF reduce the number of items and your knapsack
rate will remain same.
Right?
So one thing to notice here is here you need to write a minus one because when the value of five will
become ln, this value will become weight off and right.
And which is wrong because the last index will be in minus one.
So when I'm saying weight of item, the weight of a little item.
So that means you need to write a minus one here because indexing starts some zero weight.
So what I've done here is.
I have written this line.
Here right now, we need to convert this party into binding programming code, so in the Elzbieta in
the LS part, I can pick this item right?
I can pick this item.
So I have two option.
Either pick this item and find out the maximum profit.
Second option is do not pick this item, exclude this item and try to find out the maximum profit.
And what will be your answer.
Your answer will be the maximum of when you pick this item, the maximum profit, and similarly exclude
when you exclude this item, when you do not pick the current item so far, including what I will do,
I will get the price of the item.
What is this?
So I am including this item.
So how much money I will get.
I will get the price of any item and the price of eight items.
Prizefighting minus one.
Similarly, what will happen since I have picked this item.
So the number of items will reduce by one.
And since I have this item, so the weight of my knapsack, the weight of my knapsack will decrease.
So the weight of my knapsack was G.
So and the weight of eight items is very toffy, minus one.
Right.
So what I am doing here is no, since I am picking this item.
So the number of items will reduce by one, and since I am picking these items at the weight of my knapsack
will decrease.
So currently the weight of knapsack was G and the weight of eight items is very tough.
I minus one.
So that will be, this will be my new weight of knapsack and excluding.
So if I exclude this then the money that I will get will be zero because I am not picking this item.
So zero plus DPF, I am not picking these items for the number of items reduced by one, and since I
am not picking the item.
So no change on the capacity of your bag.
Right.
So yes, that is the complete code you need to write that.
Is it very, very simple.
Right.
So let's see how we are able to convert everything else according to the code.
So it's very simple.
What I'm thinking here is if the weight of the eight item is greater than the knapsack weight, then
you cannot pick this item.
So the number of items reduced by one and the knapsack, which will remain same when you can pick this
item, you have to option either include this item or exclude this item.
So when I am including the item, the money that I will get is the price of item.
So price of item then the number of items reduced by one because you have to one item and the weight
of a knapsack will decrease.
The capacity of a knapsack will decrease because you have picked eight items.
So the current capacity minus the weight of the eight item and when you are excluding so when we are
excluding, we just are reducing the number of items.
So we are reducing the number of items to be a minus one.
And finally, what we need to do, we need to take the maximum of include and exclude.
And that will be our answer.
And finally, we are returning our answer.
So let's see whether this will work or not.
Let's try to test our code and then we will submit.
Sara Gold is working fine now.
Let's amitava our gold.
So, yeah, our goal is working fine, and now let's discuss time and space complexity for this solution.
So it's very obvious what is the time, complexity, so the time complexity is basically what you are
doing, you are trading time.
Complexity is number of items multiplied by the weight of your knapsack.
Similarly, what is your space complexity?
You are creating this two dimensional area to solve your problems.
The number of items multiplied by the weight of your knapsack back.
Right.
So this is the time and the space complexity.
Now, understanding this problem is very, very important because many problems in dining programming
can be solved with the help of the approach that we have used here.
Right.
So many problems in dining programming can be solved with the help of this problem.
If you know the approach for solving you know what knapsack, then many problems are there that are
directly just the variation of an abstract problem.
You just need to identify that.
Yeah, this is simply the variation.
So one more thing.
As I discussed in the previous video, if we have a finite number of items, then what we need to do.
So I told you, instead of reducing the number of items you will take and here similarly, if you have
infinite number of items in the programming code, instead of reducing the number of items you will
write DPF, I hear.
So that is the only thing that will change if you have infinite copies of each item.
So this is it that I want to cover in this video dynamic programming code for zero, you don't want
an abstract problem, right?
So if you have any doubt in this video, in this problem, do reach out to me.
I will be more than happy to help you out.
So this is all about this video.
I will see you in the next one.
Thank you.