OK.
Welcome to this final slide show lecture for this optimization subsection of the course, we're going
to be talking about one last problem and this is the oh one knapsack problem you might have heard of
it before might have not, which is totally fine if you haven't.
And there will be one lecture after this which will be about the code for this.
But we're going to go over the theoretical part of this problem in this lecture.
So this will be a little bit trickier than the other problems is kind of why I am finishing on this
for this sub topic, but I will go into as much detail as I can explaining it, and it's very interesting
problem.
So let's look into it.
Oh, one really just ends for zero one.
True and false?
Kind of.
There are other knapsack problems that are a little bit different.
So pretty much the same overall idea, but they're a little bit different.
So if you'd like to look that up and check into those, I'm not going to be going those, but it might
be good to look into those, too.
This is definitely the most common one, though out of all the SEC problems, so most common one to
be asked in interviews and things like that too, I think.
OK, so let's get started.
So what is the one knapsack problem?
Well, it's basically something like where a thief could enter a home with the goal of stealing as many
things of the most valuable items as he can.
So he's carrying a knapsack with him that has a specific weight capacity.
So if he wants to put too much in this knapsack, it would tear if there was too much weight.
So the problem is, if the thief needs to figure out is what is the best combinations, best combination
of items to maximize the value that he can take from the house.
So he wants the best combinations.
The combination of items that wouldn't exceed the weight and would give him the best value, kind of
the best bang for his bike to get out of the house with.
So just a little bit about what this might look like in code.
The representation of the knapsack would be maybe like a two dimensional array or an array of tuples.
It's just pairs where this is an item right here.
Each item has a weight in a value.
So here's an item, here's an item and so on.
Here's a more concrete example.
So like this will have a weight of three and a value of seven.
So this would be like the first item.
Second item would have a weight of six and a value of five and so on and so forth.
The other thing we need to define is a maximum capacity of our knapsack.
So example would be like seven or something.
So what would a naive solution look like?
So if you just had to think of this off the top of your head and figure out a way that didn't necessarily
have to be the most efficient or anything like that, but you just had to solve the problem.
You just had to make sure that you came up with the optimal combination of items or just.
The best value you could get from the items for putting things in your knapsack with a given of the
given input to the problem, like the given weight capacity, the knapsack and the given set of items.
So what would be the most basic implementation, so it's actually you can do it in like a brute force
manner and get the optimal combination, you just have to iterate over all possible combinations, basically.
So that would look something like this, this is a recursive solution.
I'm not going to go into great detail about this because I think that you could come up with some of
your own ways of doing this, but I just wanted to mention it.
The least just mentioned a brute force solution, because I feel like it was important to the overall
problem, you know, comparing the different ways of solving this and which ways of solving this could
be more efficient and as far as time and stuff like that.
So we have this function here, it is recursive, it has a base case up here in is representative of
the number of items items is a to do list, which is just a list of pairs.
It's actually like a list that has other tiny lists that are just the weight and the value.
So you see of this thing right here, like the second index here of items, this zero would be the weight
one would be the value just like up here.
You notice like this is index zero.
This is you could see this instead of a tuple.
Just to have brackets.
And this would be a list within a list and it just has zero is the weight.
One is the value.
So you will be the given capacity and a certain, you know, of course, the recursion is changing this.
So it's whatever stack, frame or whatever function call recursive call we're in, it's the given the
given max capacity at that point of the or not the max.
But just like the given capacity that's being considered at this point, but we do have a max capacity
of our knapsack that's represented by W.
So of course, if in a zero w zero, we return to zero, that's our overall base case.
Then here we're checking to see that when we look at the minus one item, the weight of that, if it's
greater than the overall capacity, then we return recursive call and we just go kind of.
To that next items, so be considering like the next one will do it in minus one.
So the next part here is just doing a first in a second, which these two things are basically just
us considering using an item in us considering not using an item.
So you notice that this is like a value of an item being added to a recursive call where we then basically
call it with that item.
So.
That's why we have the max capacity minus the items wait right here.
So this is like adding that item to the value, adding the value of the item to our overall value because
you know that that's what we're returning, it's like our overall value, we're trying to find the optimal
value.
So this is like the items value, and we're adding it to the recursive call, since we're returning
the value and in the recursive call here, since we're considering that item, we're going to basically
now consider a different state of our knapsack that now has that item in it.
So right here, we need to subtract that from the overall weight, say the overall capacity, because
of course, if we add a new item to our knapsack, we've got to adjust the capacity like if it had a
way to for that item, had a way to for now, our capacity and our capacity is for less than it was
previously, right.
So that's what we're doing right here or passing that for a W..
And then, of course, we just pass our container of items and then we use the N minus one, which is
current item we're considering.
So the second thing that was like, if we consider the item for first, the second is if we don't consider
when we just move on to the next item.
So here we have a check.
This is kind of where it happens.
It's like post condition after recursion is saying, Well, if considering the item is greater than
not considered an item, then we'll return considering the item.
Otherwise, we'll return, not considering the item.
So that's just like the part that figures out what the better option is, whether to put an item in
the knapsack or not put an item in the knapsack if it yields a better value or not.
So we're just using recursion to iterate over all the possible combinations that can ever be in the
knapsack to find the best solution and return the value.
You know, how much do all those items values add up to for the best knapsack?
OK, so that's just the basic explanation.
If you want to go in and like, draw a recursive tree for this, you could definitely do that and see
how it's working out.
But like I said, I'm not going to go into great detail about this because we have some other solutions
that can consider that are going to be better than this.
And why are they going to be better than this?
Well, let's check that out in the next slide.
So this is pretty slow.
So since we're iterating over all the subsets of all the items and we can choose or not choose one.
This gives us actually two to the N combinations that we have to explore.
We're in the number of items, and so it also ends up being bigger of two to the N, that's exponential
time complexity and that is a very, very poor time complexity in terms of efficiency.
So there's got to be some other solutions that are better, right?
Some faster solutions.
So what if we were to go with a greedy method?
How do we do that?
So if we care about looking at the best items in terms of the value to weight ratio and then just starting
at the best and moving towards the worst and just stopping once our knapsack is for that would kind
of be the greedy way of going about it.
So how would we do that?
Well, first we have to sort the knapsack based on value to weight ratio, right?
So we can just sort it.
And then what we'll do is we'll move linearly through that sorted list of the items.
And once we can't add any more to our knapsack, we'll just stop.
So that seems logical, right?
So in terms of speed, two of the fastest growing algorithms are more short and quick sort, and those
are both in log in time complexity.
So we could implement it with either one of those and then we could just use our greedy method as we
move through it.
In a linear fashion, I say linear.
So that is going to be in big of in time complexity since in log in is of a higher magnitude than that,
our time complexity would be capped it in log in for this greedy method we're talking about.
So whether you use a sort of quick sort.
OK, so.
If we do the screamer, so let's see how this will work out.
So here I have my items and I have a max capacity of six in this example.
And hopefully this is correct.
I sorted them based on the value to weight ratio.
So we're going to go ahead and start off on this first item and just move left to right and add things
to our knapsack, so we'll be adding to current weight and adding to best value, and then we'll just
stop once it's about to exceed the knapsack.
So we add two to the weight, nine to the best value for this first item gives us to a nine.
We go to the next one, we add two to our current weight and five to our best value, and that gives
us four and 14 and we move to the next item and Oatway.
If we add four weight to this, our current weight becomes eight.
But we said our knapsack can only hold six, so we actually can't add this item.
So we're not going to consider adding the value either.
So we got to stop at this point.
So we say, Hey, best value is 14, so that's our optimal knapsack value.
But is it our optimal next to grab you when you positivity and take a look and see if this is actually
the best value we could get with these items?
So if you took a look and figured out you wanted to notice that we actually have a better option, if
we did consider that item that we just kind of discarded and stopped at and instead didn't use this
and use the first one and that one.
We noticed that four plus two is six that's still face in our knapsack, but we have nine plus nine
now for our value, which gives us 18.
So 18, obviously greater than 14.
So this greedy method actually did not find this the optimal value for our knapsack.
So what to do now?
This is kind of annoying, right?
Ah, brute force does find the optimal solution because it iterate over all possible combinations,
but it's very slow and our greedy one is pretty fast, you know, rather than having to to the end.
Time complexity, which is exponential ahead in log in, which is based on like merge sort or something
like that.
So it was much faster, but it wasn't optimal.
It didn't give us an optimal answer.
So what else we could do?
And you might already have an answer to this based on what we've done so far.
That would be dynamic programming.
Yes, we'll continue on with dynamic programming.
It is possible to use it to solve this problem in a better way.
So that's cool, but how do we use it for this problem, so.
Yeah, let's remember the ingredients required to use in our program, and so it kind of has two things
that really would make us want to use dynamic programming, right?
Some problems that can be combined to answer an overarching problem and then getting rid of repetition
and redundancy.
So we're not calculating the same problem, same answers over and over again.
So although these may not seem immediately applicable to the problem, they're both present in this
old knapsack.
And let's see why.
So the main concern for any given some problem in this is with a certain amount of space left in a knapsack
in a certain collections of items left to use.
What is the best combo of items to use at any given point in time?
So if we break the problem down for each item in each potential amount of space left, it can exist.
We noticed that there are some answers that can help us, some answers to some problems that can help
us to other problems solve other problems.
So an example is if I had three different items, I was told that a knapsack has capacity to an optimal
solution of for profit when using item number one.
I know that if I was to use a different item, so not item number one, but same capacity, same current
capacity, I could use this answer of, hey, they said four was the best and I could compare it to
what that would look like if I use the new item instead.
So if I got a better profit from using item, let's say two instead of item one, then I could just
add it to the knapsack and move on, and I could use that as my solution to this new sub problem.
Otherwise, what I could do is, I could say.
Hey, it's not better, so what I'm going to do is just use that answer that I already had like it already
said for profit is the best.
If I was to not use, I one use item two for the same capacity.
And it wasn't as good.
Then I'm going to say, you know what?
Let's just go with what was already said then, because this is the best with like.
You know, so far to what we figured out so far is that Max profit is for so let's just roll with that
and then go try another item.
So I use that solution to help me.
It's already been calculated so I can grab that and kind of roll with it so we can kind of see how the
optimal sub problem property is present, because that's a problem was already useful to us the answer
of for maximum profit when we consider that item one.
But what about repetition?
Honestly, it's kind of the same thing what we've already described.
So we're repeating the question of what is the most profit for X amount of space left in the knapsack?
We're doing that over and over again.
So the item that we're referring to for its problem is not what makes it a unique said problem.
It's really the question of how much profit given remaining space, that is the same problem.
So that's what's getting repeated over and over again.
And it would be nice if we already had an answer that we could just go look up if we didn't find something.
Let's say we add a new item to our knapsack.
And for a given capacity and.
It gives us a value, right?
It gives us this maximum value now when we add it, and what we could do is kind of compare it to something
that's already been calculated for that amount of space.
And if it's not as good as what was already calculated, then let's just take that thing that was already
calculated and move on to the next thing.
Or if it's better, then hey, let's updated to now this is the best amount, and then let's move on
to the next thing.
So that's kind of what we're talking about here.
And we choose not to use an item.
We grab the already calculated max profit from X amount of space left some problem.
And then we go on to concerning the next item, otherwise we update.
So this is a little confusing with words, especially if you're a visual learner.
So of course, we're going to visualize this now, right?
And we're going to do it with a table because most dynamic programming problems are using a table.
So I haven't used the same exact example, but I kind of simplified it to just make the explanation
a little more succinct and more simple here.
So what we have is columns are representing a current capacity of the knapsack.
And this would be like the overall capacity that we started out with.
For our question, like so when the problem started out, if someone told us knapsack is capacity for.
That's this number here, and we're going from zero up to that number four columns in our table and
the rows are the items that we're considering.
So the sub problems we're solving here are like given a specific capacity, current capacity.
You know, what is the best value we can get using a given item?
And you notice as we work down or like to these other items, we could have already has some like items
in here.
So this grid helps us consider things that have already been calculated for specific items to know if
we were to add a new item.
Would it really give us a better answer or not?
So that's kind of how we're going to move through this and fill these cells out and where you go from
upper left to bottom right.
So let's start out right now with item one.
We noticed that item one has a weight of three and a value of three.
So how what would we get, what's the max value we could get using it with a knapsack of capacity?
Zero using this item, one with the capacity zero, what capacity is zero?
That's kind of weird, right?
Because.
Honestly, it's like not even having a knapsack at all.
You can't put anything if you don't have a knapsack or there's no knapsack to put anything in his capacity,
zero is basically like an empty net or not empty.
It's just like a non-existent knapsack.
So we're going to say that we can't get anything out of that.
So value is zero.
It's actually same thing for this to capacity is one.
But we cannot fit this item.
We only have one item right now to consider.
We're just starting out on this first row.
The weight of this first item is three, if we have a knapsack that only fits weight one.
We cannot add this item, and so we're going to have to leave with an empty knapsack.
Same thing for capacity.
Two It still is in three now, though.
Capacity three, we can fit our item in there, but since we're only considering one item, it's pretty
easy.
It's just going to be the value of that item, right?
Same thing for a capacity for even though we have one extra space or weight, you know, left since
we only have a weight three for this item, it doesn't really matter because we're only considering
this item.
So we just throw that one item in there, even though it has extra space and we leave with that and
we only get three for our value.
So let's go to the next row.
Capacity zero, this is always going to be zero.
Honestly, this whole column, because we can't fit anything in a capacity zero knapsack, so you can
just always mark this as zero.
So if this weight of item to is one, then if we go to one, we know we can add four.
But here's the point in which we need to consider what we've calculated up to this point.
So we're going to start using a formula and what we're going to do is say, OK, if I am to add this
item.
I want to see basically what?
I like what my previous best capacity was.
And I want to see what it would be like to add this new item in.
And so what I want to do is look up here.
In this same column for capacity is one.
This cell right above me is going to have the answer of when I am not considering this item.
This was the best value I could get.
If I am going to consider this adding this item, what I need to do.
It's not just look at the items of value.
I actually need to think of what it would be like to.
Have this item in my knapsack.
And have it fit based on its weight, so what I need to do is actually since the weight is one I go
back up to when I just had item one.
And I need to go over one because I need to get rid of some of the capacity.
So.
And basically what you're doing is you're subtracting the weight from the certain from the specific
capacity here.
So it's kind of like, you know, freeing up the space or whatever, so what we would do is go up one
and over one to basically look for what's here.
And that would be the value in which we would add our new items value to in the some of that, we would
then compare to what the best was previously without considering this item.
So that's what we're going to do.
So this is there's some problem here.
If Rosie and columnist Jay.
Then the sub problem that we have to look at to be able to use to calculate our new answer is.
At the position.
Table I.
Minus one, which is the item minus one.
So we're going to go up one by arrow and then it's going to be J, which is columns which are columns
J.
J minus II's weight.
I remember I as rose, so I weight is one.
So we're going to go over one column.
So up to the previous row, to the left by whatever the weight is.
And columns.
So we take this zero.
We add this four to it, zero plus four.
And then we compare it to this value right here.
And four is greater than this zero right here.
So therefore, the thing we're going to put here is for.
And we're going to keep going through our table and updating it in this fashion.
If it's not greater than or if the item cannot fit at all, then we'll just bring this value that was
previously the best down into our new sale.
So for example, if the weight was exceeding this, then we would just bring zero down if the weight
was too big.
We can't even fit it whatsoever just because by default, the item is just too big to fit in the knapsack.
We would just bring this down.
Same thing if we calculated by adding this to our value and we realize that this number was better,
it was bigger than we would also just bring that down.
But since that wasn't the case, are some from this number, and this number is what we ended up putting
here.
I just want to make sure everyone's on the same page before we move forward.
So so we're going to keep using this formula for all the cells in the table if the item can be used.
We will use what we did right there with the addition of these two and put it down.
So let's check this one out.
So we look above, we got zero here.
And what we're going to do is actually, since the wait is one, we go up and over one and we add four
to zero, that's four, right?
That's a greater than zero.
So we add four here.
It's greater than this zero.
Same thing here.
When you're up and over one, this is zero plus four is four.
Four is bigger than three.
So we put a four there.
And then this last one's going to be the same thing.
But what we will do is I get a different number because we're going to add four to three.
So same thing the weights one, we go up to our last row, we go over one to the left.
We have four plus three.
That's seven seven is bigger than three.
So we put a seven here, OK?
And we said we're always going for zero in this column, right?
Because we can't say anything in a knapsack of capacity zero.
And capacity one, we're just going to bring down because you notice that the wait is too, so we cannot
consider putting this item in just whatsoever since the wait is bigger than this capacity column.
So we'll just bring the last best value down to here.
So for goes down to here.
But now, since capacity is too in our ways, too, we can now consider this item.
So what we will do is since the weight is to wear after we go up, we're going to go over to this time
and we're going to add our value to this.
So that's five zero five.
That's better than four, right?
So we'll put five there.
Same thing here will go up and over to five plus four is nine nine is better than four.
So we and that there.
Five plus four is nine, that's better than seven, so we had a nine there, and now I'm just going
to fill out for this next item.
We noticed we have capacity.
Sorry.
We have our weight is four, so we know we're not going to be able to use any of the.
We're not going to be able to like, consider adding this item for any of these because the knapsack
capacity is of all these columns is less than our weight of the item.
So we're just going to bring all these values down because this is going to be the same optimal value
at this point since we can consider the item.
So that will lead us to figure out this one right here.
So we have value of six and a weight of four.
So we would go up and then over four one two three four.
So six plus zero six is six better than nine.
It's not better than nine.
So we're just going to bring the nine down.
And this actually gives us our final answer the the final answer to the best value you can get.
In your knapsack, given all of this input, it's going to be in the bottom right hand corner of the
table.
Another interesting thing is that we can answer the other part of the question that we want to know.
Well, we just calculated all this stuff, but we didn't necessarily like keep track of the items we
were using.
We might know what we really use just by memory of us thinking.
About, you know, the fact that we didn't use this.
You know, and instead use like we did use this one right, and we did use this one, but we can actually
back trace to be able to figure out exactly what we used just by figuring out where we came from in
the grid, like which cell did we end up using when we had the question mark here?
So let's do that.
So first of all, we do is look right above.
Is this value above us less?
If it's not less, then we didn't use it.
So that means that we just brought this nine down and that's what we did, right?
So we can just go back, we can go right back up to where we came from, which was we brought this nine
down.
So we're going to go up to it.
Is this less?
Yeah, this is less so.
That means that we since the weight is too, we went up and looked over too, and we ended up using
this and adding five to it to get our nine.
So we were using this cell, so we'll now go over there.
And since we used this item three, we would add that to like a list or something so we could keep track
of the items we use.
You know, since this was less and we realized that we used this and had five plus four is nine.
Then we would add, we say, Hey, we did use item three.
So we'll add that to some sort of container to keep track as we backtrace.
So now we're here.
Let's look one above.
Is this less?
Yes, it is less so if we were to go up and one over.
That's what we ended up using.
Was this cell right here?
So we had four plus zero give gave us four.
So we go here.
And then at this point, I don't really have item zero represented on here because there is no real
item to you.
But in the actual implementation, you will probably have an item zero, just like you have a capacity
zero, just because you'll use like a standard matrix or something to represent this.
And that'll just be all zeroed out since you have an item zero.
But once we hit that zero like items zero zero zero or column zero, we can just stop the bacteria.
So at this point, we're pretty much done.
We know that we used Item two and we use Item three because we kept track of this.
So that's pretty much it.
Now it's time to write some code, which I will do in the next lecture.
And I also kind of point out the specific like mathematical representation of when we're choosing a
max value because you can kind of right that in mathematical terms here.
I just tried to explain it in some layman's terms, but I might write that as well.
In addition to the code in the next lecture, some of you like to see that.
OK, so with that, I will see you in the next lecture, which we will try and implement this dynamic
programming algorithm.