OK, so now we can get on to the coding portion of this knapsack problem.
You can see that I've already included a few function prototypes here.
I just kind of wanted to put this to start out with.
Wasn't trying to write too much without explaining it.
So I just kind of go over that right now.
But these are just some things that we know we're going to need.
So primarily, this is our dynamic programming function right here, and it is going to return our optimal
value.
So the maximum value we can get out of the optimal combination of items for the knapsack.
And so we have some arguments here that'll go to it.
One will be definitely the list of the items, right?
This is not 100 percent necessary because it's just the size of the like, the number of items, basically,
which I could just reference items our size.
But I wanted to explicitly put it in here just so it's more like clear for you guys.
So I added that there, even though it's kind of redundant, you can just do items size if you want.
But this is cap.
This is the capacity of our knapsack.
So maximum capacity.
And then, of course, I have the dynamic programming table passed by reference, which I will be initializing
and sending to the function.
This function down here just returns the list of items that we ended up using for our optimal combination.
So this is that backtracking part they were talking about in the last lecture when we started at the
bottom right of the table and worked our way back to try and figure out what items we actually used.
It takes the same exact parameters, and I'll give it to explain that function more once we implement
it.
This max function, I added right here.
That's just something that we're going to want to use because you know that we have to look at the maximum
between that result of the up and left cell with our value like that, some result and compared to the
value directly above us in the table.
So that's the reason we want this max function just so it can be a little more kind of divvied up between
functions instead of just throwing that logic in here.
So I chose to put that totally up to you.
You can do whatever you want.
So let's go ahead and just kind of get our items situated in our knapsack capacity, all the input and
everything.
I'm going to go ahead and just roll with the greedy method example just so we can kind of contrast how
our dynamic programming actually gets the optimal solution.
So if you remember from the last lecture, if you want to check that out to your memory, I kind of
have it right here.
But you know, some notes from that.
But it was like a capacity of six, and it was that one where greedy method chose the value of 14,
but it was actually supposed to be 18.
So we're going to roll with that so we can show how the dynamic programming actually gets us the correct
answer for that.
So to start off, I'm just going to do an end, which is knapsack capacity, and that'll be equal to
six.
Then I'm going to make a vector actually do this right here.
I'll copy this.
We're going to make our items so I can just put that right here and I'm putting in like, I'm not using
the standard namespace up here.
I normally do.
Some people kind of don't like when I do that, sometimes in videos, just because it's bad.
Programming practice a lot of time.
But I think, you know, if you're just doing like a small little program like this doesn't do any harm.
But I do understand that it's not necessarily the best practice to use that.
So I don't know in today's lecture, I'm just going to not use that, and I'm just going to put in a
line before everything that is from that standard library.
So yeah, you can certainly include the using namespace statement above, if you like.
So we're just going to harkov this.
And since we're using C++ 11 and above, we can do this.
So this was our list of items there, just the 2D vector as pairs.
So the first one and each pair is the weight and the second number, and each pair is the value.
So I'm just referencing a note that I had it told me what?
I had four values in the last lecture.
Here we go.
So then we're also going to want to do a table.
So this table is going to be initialized to item size plus one.
And OK, and this is something that is.
Important so this is the number of rows, and we're doing a plus one because the table we're going to
leave like this.
Right.
This first item in the table.
This is technically indexed zero, right?
So indexed zero index one.
The thing is though, is it in our table?
We're also going to start at index zero like we'll have a row column.
I'm sorry.
We'll have a row zero and a column zero.
Except this first item is going to correspond to row one in our table.
If you remember from the last lecture, I started with the first rule being item one.
But I did mention that when we implement to encode that it might look different, we might have like
a rose zero and we're going to have a real zero and a column zero.
In the last lecture, I had to call them zero, but I didn't have a row zero for the item zero because
we don't really have like a zero item that we care about.
So this first item is going to correspond to row one, and that is just so we can index things properly,
reassess the way I like to do it.
So that is why we're doing an item size plus one for the number of rows here.
And of course, the second argument is going to be the vector of integers.
And it is going to have a knapsack capacity plus one size, that's for the number of columns.
So.
And it's the same thing here.
You know, we're we're doing a plus one just because we're going to start out at zero there.
So that's why I'm adding in there.
So I don't actually need I could put it zero here to initialize to all zeros, but I'm actually going
to omit that because it's just automatically does it by default.
So there we go, initialize the table with all of the rules right now, so we can then later update
it in our function, their dynamic knapsack function that will fill up the table correctly.
It just kind of be modifying the cells.
So the next thing that we'll be doing is something like this ever implemented a functioning, but we're
going to call it a function, of course, and we'll store our result for the number in here.
So it'll be a deep knapsack items.
We'll have a DC knapsack function.
It'll be items and then items that size and then it'll be a knapsack capacity and then table.
So, yeah.
All right, so now that I put that call there, it's probably time to actually implement this function.
So I'm going to copy this
and put that here and are actually seeing and zoom in a little bit, make it a little bigger for you
guys.
Hopefully, you can see, OK.
So let's think back to the last lecture.
What did we have going on here?
You know that what we did was basically we started out at the upper left of the table, right?
And then we filled out our table heading towards the bottom right.
So row by row, column by column hour, rows with the items.
In our columns where the.
Knapsack capacity, so a specific knapsack capacity, and with those two, we were able to represent
some problems.
So.
Since we know that if we think back to the last lecture, we have rows and columns, so we're going
to loop over these rows and columns and we're going to be starting the upper left, so we'll start at
row zero and column zero.
It kind of implies that we're going to launch something like a nested loop.
So we're new for nine equals zero.
And what are we going up to?
We're going up to and including so less than and including our in value, which is our number of items.
So we're actually considering all the items up to the item, and that's kind of why we did that plus
one.
Thing they're so.
Yeah, we're going to want to have the table be corresponding to the actual item number, and I said
we're starting to zero.
And you'll notice how that kind of plays into how we do this.
So we're also going to go for Int J equals zero j less than equal to capacity for capacity.
And then inside here we got to think of like our conditions, right?
So what were we doing when we were filling out the table?
So one of the first things we checked for it was that right off the bat, we know if it was column's
zero, that was like a knapsack of zero and we did not care about that really.
We knew that was always going to be zero, right because you can't fit anything.
If the bag is essentially non-existent, the knapsack is essentially nonexistent.
Can't fit anything.
Is this the same thing for the item zero zero isn't really a thing, so even though we start out with
this like road zero and column zero stuff, they're always going to be zero.
So what we can do is just say that that's going to be a zero no matter what.
So that's an easy one.
So if I is zero or Jay is zero, then what we can do is just set that j value in our table, the cell
apparently on to zero and they're already filled with zero.
So it's kind of like a little bit redundant, you know, you could kind of just do nothing, I guess,
since we thought it was yours.
But it's better to just put this in here just so we're like actually taking some type of action.
So what's the next condition?
So we kind of have two other things, right?
We want to check to see whether the item that we're currently considering.
We want to know if it's weight.
Exceeds the capacity of the current column capacity that we're on, remember the columns are capacity
and we have that issue where like we just put like a bunch of zeros or we brought down the item that
was sorry, we brought down the value that was directly above us in the table.
If we couldn't even fit our item, so remember, like if the current item we're considering, if it
has a weight of three and we're considering the column capacity one or capacity two, we can't fit our
item.
We can not use that item there because it exceeds the capacity, even that one item exceeds the capacity.
So in that case, we know for sure we're just going to bring down the above items.
So.
What we want to do for our actual comparison, when we were using our formula, that was when it wasn't
exceeding the current capacity column, which is J.
So let's check that let's check the weight.
So if we're with check our items and this is where there's a really important thing that we're doing,
so it's not going to be items.
I remember this is because our item starts at zero, but this first item here, it corresponds not to
row zero in the table, but it corresponds to real one.
And so there's going to be like an offset where we're going to want to do a minus one.
Because we wouldn't like if we were on item one, so I was.
One.
You know, if we just used iron items that would get us this, but we don't want that, we want this,
so we're going to do it, I'm minus one.
So two items on minus one.
And remember, our weight is the first thing, so it's this right here, this is our way, it's the
first thing.
So we're going to do is zero because we care about the weight and we want to see if the weight is less
than or equal to.
If we're going to choose the item, we want it to be less than or equal to the current capacity.
And what is the current capacity is represented by J.
We're basically counting from zero up until our capacity.
So think back to our table how the columns looked, the labels for the column.
So we're checking if the weight of our current item is listening equal to J.
If that's the case, we can use our formula, if it's not the case, then we'll have an else down here.
Well, I'm not yet filled out yet, but we'll have an else down there or we'll just bring it straight
down right from the item above us.
Not that I'm about to say the value above us, so let's think about our formula.
Let's do that.
What's our main formula?
So if we could potentially use the item because its weight does not exceed the current capacity, we
then want to see what is the max of us going up one row and going to that selves to the left?
Remember what is the value of that, plus our current value for our item?
We won't take that sum right and compare that to what was directly above us.
So that is what we're doing right now.
We're going to say the table I j, just like above, that's going to be equal to and this is where we
would use our max function.
So I'm gonna go ahead and just type it out now.
Even though we haven't implemented it, it would be a pretty trivial function to make.
So this is going to be our items value, right?
And remember, we want to do a minus one.
So we get the right value.
Because of that offset there.
And it's the second thing in the pair, right?
So this is the second thing, it's not the it's not the zero index, it's the one index in each pair.
So that's why I'm putting a one here.
So we take that value.
We add it to deep table and we're going to go up one row, right?
So I minus one and this is not the same minus one is and decide which one is not the same as like why
we're using this I minus one.
Remember, this is because we want to make sure that the items line up with the indices.
This is literally us going up one row.
That's why we do this in minus one.
So what we want to do is go up one row and then what do we want to do?
We want to go to the left.
How many spaces we want to go to the left, as many spaces as the weight of the current item that we're
on.
So what is that going to be?
Is going to be like this?
So we're going to index it as J.
That's the current capacity.
The current column we're on from the current column moron, we want to go to the left.
So minus subtracting going to the left, how much items I minus one, let's get the weight right.
Let's get the weight from the item.
So items I minus one and this am I minus one is because of this right.
We want to make sure that it aligns correctly with here because this starts to zero, but we're actually
referencing.
Row one for this thing.
So that's why we need to do this minus one to get it correct.
So we're subtracting the weight.
The weight is the second thing, so it's zero one.
So that is the weight or know, so the weight is the first thing.
Apologies, apologies.
The way is the first thing, so it's index zero.
So we will do items in minus one zero.
OK.
So we're basically taking that.
And then we're going up one row and then we're going to the left by that amount at the weight.
So we will add those two, right, that's our first thing to compare from Max.
So we get that some and we want to see if it's greater than what's directly above us was directly above
us.
All we have to do is keep table.
Go up one row right side minus one is just to go up one row.
And then we can reference the same column that we're on, which is just to say, sorry, you can't really
see that there.
So up one row and then the same column as we're currently on, which is just J.
Cool.
So we want the match between those two things.
So and then we'll go ahead and implement this max function in just one moment.
But I don't want to get too sidetracked from what we are doing right here.
I want to go ahead and just do that else.
So else.
If it is not less than or equal to.
J.
That means that we're just going to bring down the I am right, because if our current item, if its
weight just by itself exceeds the capacity of the column that we're on, we're just going to do this.
We're just going to bring the thing right above us down before we use this and compared it to see if
it was greater, if it was, you know, we wanted the max of these two.
But if our item that we're considering, if it's heavier than the current column capacity that we're
on, we we can't consider this formula.
We're just going to do this one.
So let me copy that.
And what I'll say is just deep table I, J equals that sort of thing directly above us.
One up, but in the same column.
So think back to the last election and visualize it.
We're on a current cell right now.
We're considering the thing right above us.
That's what we're going to use.
You can bring it down and put it in the cell.
Copy it down and put it in the cell we're carrying it currently in.
OK, so before we go any further now, I'm going to go ahead and just implement this max function,
and we pretty easy.
We're just I think we've done this before.
We just have two numbers and all we need to do is return.
If a is greater than faith in return, a otherwise which can be.
So just do a little ternary there for that.
So and then the last thing we have to do in here, remember is just basically our our answer.
Was at the bottom right corner, right?
And because of the way that we've set everything up, we did that like plus one and everything.
We are actually.
Going to remember so the size of this stuff.
If we were to just put the.
You know, when you think about the normal size, if you just put the capacity, it would start at zero,
so it would be one off.
So we added those and now we're going to use our actual capacity and our actual number of items to get
our answer.
So we care about the actual indexing at the actual capacity.
Which will correspond to the right spot in the table because it was starting at zero and we don't really
want to consider an item zero or a capacity zero.
We are going to actually index it at that actual capacity and actual light.
Correct.
Item number like the last item?
That's our answer will be.
So because of that, we simply can just return this deep table.
And then we will be doing in.
And then just cap for our capacity that we passed.
So.
Oh, I just realized I did this all in the back check items.
Wow.
My apologies.
You're probably looking at that the whole time, wondering what I'm doing.
So let's replace this.
Um, let's see.
I will put that down here.
And then we'll just replace this with.
This knapsack.
Right here.
Apologies about that.
Yeah, that's probably it was pretty funny.
So that in there and now we can actually return the proper, the proper thing, which is an integer.
This function was all about returning the optimal value that's stored at the bottom right of the table
there.
So as we pass this by reference, we kind of modified it in here.
So that will help us in this next function, go back and do the backtracking through it already when
it's already like filled out with the correct values.
OK, so now that we switch that, we can head over to this backtracking function, so now we have this
or guess our correct value if we did it right, which we did.
And the next part will just be the backtracking.
So if you remember our backtracking.
Was actually us going the opposite direction, right, we started at the bottom right of the table.
And then we went back up to the upper left, kind of.
So we weren't like filling all the cells or modifying all the cells as we went back, we were just trying
to figure out where we came from, pretty much.
We were trying to figure out what items we used.
And that's the point of this function is to go through and like, add all the things that we use to
a factor and then return it.
So let's do that right off the bat and make that vector that we can add stuff to, and it's actually
I'm just going to copy paste this because it's going to be similar to our items vector.
I'm just going to call it used items
and then there's not a hundred percent necessary.
You could use capacity and end.
But I kind of want us to be thinking in terms of I and J just for it to be easier.
Someone makes and local variables here.
I'm going to say A.I. equals in and I'll say in J equals cat.
And then what were we doing when we went back up?
So this thing about this?
First off, we kind of thought about our conditions for the loop in the last functionally made.
So let's think about the conditions for a loop in this function.
How long do we go?
When do we know that we're done going through the backtracking process?
Well, it's pretty much when we got to the top left right, whenever we get to a point where a column
is zero or a row is zero, that's basically saying capacity is zero or its item zero.
At that point, we know that we're pretty much done because we're not going to consider looking for
any other things we use because there's nothing left at that point.
We've gone all the way up.
So I'm going to make a while loop, and I'm just going to say that I'm going to say while I is greater
than zero, we can loop.
So that's the column, right?
That's our item.
And while Jay is greater than zero, so not the column sight row.
I is Ro J is Con.
So as long as our items, which are rows allocated and zero, and as long as our columns which are capacities
are greater than zero, then we can continue living and doing our thing.
What about this, though?
What were we doing so?
We basically looked above us, right, and we said, hmm.
The current cell that we're on is the thing that's right above us greater than us.
So whatever value we have, an occurrence that we're on is a value above us, bigger or not.
If it was bigger then or sorry, if if we were bigger, if they got the thing that we're currently on,
if the cell we're currently on has a value that's bigger than what's above us.
That means that we actually use the item, right, because if it wasn't bigger, then it would have
been the max and what we would have done is we would have just brought down the thing right above us
that we would have the same value of what as what's above us.
So it would be the same thing.
But it's greater.
We know that we actually use the items.
So I'm going to say if the table I, j.
So this is what we're currently on.
If it's greater than the Table I minus one j, then we know that we used the item, right?
So let's do used items that push back and we're going to push back our item and remember that we have
to do this I minus one.
So we get the correct item out of there because the row.
You know, isn't going to correctly correspond to the item unless we subtract one.
So we push back that item.
Then what we do is where we want to go at that point, so if we actually did use that item, then that
means that we considered that value that was up until the left.
So we go up one row and we went to the left as many times as the weight of the current item that we're
on, right?
We ended up using that cell and adding it with the value of our current item to get the MAX.
And since we use that, if you remember back to the last lecture, that's the next place we kind of
had in our backtracking.
So what we're going to do is say I'm minus minus two go up one row.
But then J changes as far as the weight because we're going to we're going to the left.
Remember, if we use that cell, we now need to head over there.
And that was to the left as many times as the current items went.
And we're talking about this item here, right?
So you're going to do is say items no, I minus one to get the correct item and zero because that's
the weight, right?
So we're going to go to the left that many times to get to that.
So else, if it's the least, that means that we didn't use the item and instead we just use that previously
calculated knapsack value right above us in the same column for that capacity.
So all we're going to do is move up one row to the thing that above us, we're not going to move j and
we're not moving to the left for any columns.
We're just going up right above us.
And this will help us move through that table and add back all the things that we actually use.
So that's that backtracking process.
Think back to the last lecture and kind of that visualization.
Once we're done, all we got to do is return this vector.
So we're going to return used items.
OK, so that's actually pretty much most of our work done for us here.
We have a max where her knapsack and we have our back checking items.
So let's go ahead and finish stuff up here in Maine, we're going to want to call this backtracking
function as well.
So I think that what we can do is let's, let's see, we'll make uh, actually.
Can I actually just copy this and I'm just going to call this results like plural, and this was a result
for the actual value, the optimal value.
This is going to be the optimal set of items.
So I'll call the results and we'll call back items.
Specify items just has the same exact parameters as this function.
Some get a copy paste this and then what we can do is we can see out our optimal value for, say, optimal
value.
Yeah, I'll put a space here and it was the result, right?
And then what we want to do now is I'm going to do a loop over the actual item.
So I'm going to say for auto I and results.
And then we're just going to print out.
Let's see.
We'll print out the actual results.
Let's do w w so out w equals and then we'll do it.
Since I was the actual item will do zero for the weight.
So there'll W for the weight and then I'll put some spaces and I'll say V equals and then we'll do the
value, which is the second thing in the pair, right?
So be in x one and the pair.
All right.
And we'll just do an in the line.
Maybe.
I was not doing in line, and I just put some.
Spaces between here, like a comma or something like that, you'll be kind of messy, but whatever.
And.
No, um, yeah, I just.
Um.
Yeah, we'll just do that.
I just felt like another line.
OK, so if everything is good and hopefully it works out, let's go ahead and test it.
All right, so let's actually before I run it, let's let's think back to what these should be.
So if we're thinking back to our greedy example and what was wrong about it?
I believe what happened was it got sorted and we ended up using like, uh, this.
And this which May nine plus five was 14, and then we tried to use this.
And we already had two plus two is for capacity, and then we tried out four and that was eight that
exceeded our capacity of six family of six, so we couldn't do it.
And we said the option that is 14, which was incorrect her for this agreement to got an incorrect and
we realized our optimal solution was actually this and this.
So 18, and then this is to pause for six, so that that's actually the optimal combination of things
and the optimal value should be 18.
So let's see if that's what we end up getting.
OK, so that looks correct, our optimal value is 18 and our optimal list.
You know, that's kind of I don't necessarily like that.
I put this in there and we run that just because I'd like it to be separate on new lines.
OK, yeah, this is better.
So we have our wait for and value nine and weight two and value nine.
Cool.
So is that one and that one?
So it seems like that came out correct?
So hopefully this wasn't too difficult to understand.
Try to break it down.
This is a little bit less straightforward, I think, than some of the other dynamic programming problems
we went over.
At least the table wasn't as straightforward as far as the cells that we're using for our sub problems
to help us reduce, you know, redundancy and use our pretty calculated values and stuff like that.
It was just seemed a little maybe a little bit more complex.
But, you know, definitely go over that visualization.
I think that's huge on it.
And if you would like to look in the into the other knapsack problems, not just the zero one knapsack
and there's some other ones that kind of deal with, like fractional pieces of a knapsack and stuff
like that that might be good to look into as well.
I'm not going to cover that.
I think this is definitely the most common one, and I think it's on a lot of interviews and stuff like
that as well.
So that's a good reason to practice it.
All right.
So with that, this is kind of the end of this subsection of the course.
So I'll be seeing you in the next section.