We've now got two dynamic programming algorithms under our belt.
We know how to compute weighted independence sets in path graphs.
We also know a dynamic programming solution to the famous knapsack problem.
But before I proceed to still more useful and
famous dynamic programming algorithms Let's pause for a sanity check.
Let's go through a worked example
for that, dynamic programming algorithm for Knapsack.
Just to make sure that everything is crystal clear.
So, for reference, let me just,
rewrite the key point to the Knapsack algorithm.
So first, we have a 2D, 2D array A.
And for initialization, just whenever I equals 0.
That is, you.
You can't use any items at all.
Of course the optimal solution value is 0, and then I'm just going
to rewrite the same occurrence that we had in the previous couple of videos.
So
you'll recall that in the main loop, when you're considering a given item a,
and a residual cap-, nap sack capacity x, you take the better of two solutions.
Either you inherit the solution With i minus one and
the residual capacity x that corresponds to not taking item
i, or if you do take item i you get
a credit of Visa Buy the value for that item.
But the residual capacity drops from x to x minus the weight of item i and
you look up the optimal solution for that smaller sub problem.
So, for our concrete example, let's just look at a case with 4 items.
An initial nap sack capacity capital W equal to 6,
and the values and weights of the 4 items as follows.
So, I'm going to describe the most straightforward
implementation of the dynamic programming algorithm for knapsack.
We're literally just going to explicitly form the 2D
array A.
One index for i will range between 0 and n, the other
index for x will range between 0 and capital W, the original capacity.
There certainly a lot of optimizations you can apply when filling in these tables.
In fact, the future programming assignment will ask you to consider some.
But just to make sure the basic algorithm is totally
clear, let's just stick with that naive implementation for now.
So we begin with the initialization and setting A0X
to be equal to 0 for all x, just
means we take the leftmost column corresponding to i
equals 0 and we fill that in entirely with 0's.
Now in a real implementation there's no reason
to explicitly store these 0's, you know they are
there, but again to keep the picture clear let's
just fill in the 0's in the left column.
Now we proceed to the main while loop and
recall the outer for loop just increments the index i
for the item that we're considering so the outer for loop
is considering each of the columns in turn from left to right.
Now for a fixed value of i for a fixed column, in the
inner for loop we consider all values of x from 0 to capital W.
So that just corresponds in a given column we're
going to fill in the entries from bottom to top.
So we begin this double for loop with the second
column i equal 1 and at the bottom x equals 0.
Now in general when we fill in one of these
table entries, we're going to take the better of two solutions.
Either we just inherit the solution from the column to the left in the same row.
This corresponds to skipping item i.
Or we add the value of the current item.
to the opitimal solution that we extract from
the column one to the left, but also W
[UNKNOWN]
rows down.
So, that corresponds to reducing the residual capacity of W sub i.
Now, for the early subproblems in a column, where
you have essentially 0 residual capacity, it's kind of degenerate.
Right so, if your residual capacity x is
actually less than the weight of the current
item you're considering, w sub i, you have
no choice but to inherit the previous solution.
You're actually not allowed to pack the current item i.
So concretely in this example,
in the first column, notice the weight of the first item is 4.
So that means if x equals 0 or 1 or 2 or 3.
We're actually not permitted to choose item
one, we're going to run out of residual capacity.
So in the first, bottommost four rows
[INAUDIBLE],
we're forced to inherit the solution from the column to the left.
So it is the first four 0's from the left column get copied over to column with i
equals 1.
Now, in this outer iteration of the, in the first outer iteration of
the for-loop, once x reaches 4, now
there's actually an interesting decision to make.
We have the option of inheriting the 0,
immediately to the left.
Or, we can take item 1, therefore getting a value of 3.
And then we inherit the solution from a 0, 0.
And now A000 has a 0, but were obviously happy to get this value of three.
So that's going to determine the max we're going to except V sub i , plus a of 0, 0.
And that gives us a three in this next table entry.
By the same reasoning, we're going to fill in
the uppermost rows of column one with these threes.
We're, we certainly would prefer just taking the
item one which we're now allowed to do.
We have enough residual capacity.
As opposed to just inheriting the 0 from the column one to the left.
So that's how we fill in the column of i equal one.
Moving on to i equal two.
Again, so here notice that item two has a weight of three.
So again, the bottommost three rows when x equals 0, or one, or two.
There's nothing we can do.
We don't have the option of picking item number two.
We don't have enough digital capacity.
So we just copy the values from column i equal 1 over.
Those happen to be 0's, so that gives us three 0's to start column two.
Now when i equals 2 and x equals 3, now
we're, we have enough residual capacity to take item two.
And we're certainly, much happier to take the value of 2.
Which is the value of item number two, as
opposed to inheriting the 0, 1 column on the left.
So that gives us a two in the column i
equals 2, with a residual capacity x equal to 3.
So perhaps the first truly interesting table entry to fill in is when i
equals 2 and x equals 4, because in this case, we
actually have two different non trivial solutions we have to pick from.
So one solution, as usual, we can just copy over the number, which
is one column to the left, but actually in this case, there's a 3.
There's no longer a 0 to the To the left there's a 3 to the left Right?
A 1,4 is equal to 3.
Our other option is to take the second item getting us a value
of 2 and add that to whatever is in the leftmost column but shifted
down by 3, because 3 is the weight of the second item.
And you'll note that A of 1,1 is 0.
So, picking the current item would just give us 2 plus 0 equals 0.
We'd prefer to just inherit the 3, from the column one to the left.
That is, we prefer to skip item two, so
that we get the value from item one instead.
The upper two rows of the second, the column with i
equal 2 are filled in with 3s for exactly the same reason.
So for example
in the top row, what are our options?
Well we can inherit the three that's one to the left.
If we actually use item number two, that
knocks a residual capacity down to three and
then you have 1,3 equals 0, so again, you'd rather have the three than the two.
Moving on to the penultimate column, 1i equals 3, for the
usual reasons, we have to fill in the two bottommost rows.
with a 0.
Notice that the weight of the third item equals 2.
So we need a residual capacity x equal to 2 before we can actually use it.
Now, when x equals 2, we'd much rather have the value
of 4 for the current item than to copy the 0 over.
So we're going to fill in the entry A of 3,2 of 4, the value of the third item.
Similar reasons apply when x equals three or four.
So here the alternative starts looking better, right, so in the row where x
equals three the value that we'd inherit would be two.
In the row where x equals four, the value we'd inherit would be three.
But in both of these cases we'd prefer to have the
immediate gratification of the value of four from the third item.
And just inherit the empty solution with the residual capacity.
So when X equals 3 and X equals 4, we're just
going to take the third item and get a value of 4.
Now good things really start happening once X equals
5, because at that point we can both grab the third item and gets it's value of 4.
But now, we knocked down the residual capacity only
to 5 minus 2 which equals 3, and when you
have i equal 2, and x equal 3, you
actually get to, a value of 2, in that case.
So, we're going to fill in the entry for i equals 3 and
x equal 5 with 4, the value of the current item, plus 2,
the optimal solution to the corresponding sub-problem.
It gets even better when x equals 6.
We're again going to take the third item, get its value of 4.
But now, in the smaller subproblem, when i equals 3 and x equals 4, we actually
get a value of 3, so the value here's going to be 4 plus 3, or 7.
Moving to the last column when i equals 4, so here the fourth item has weight 3, so
that means when x equals 0, or 1, or 2, we don't even have the option of picking it.
We have no choice but to copy over the
number from the column to the left, so that's going to
give us a 0, and a 0, and a 4, for the first three rows of the final column.
So now in column 3, we do have the option of picking the fourth item.
That'll give us a value of 4.
You also have the option of just copying over
the value in the column to the left. That will also give us a 4.
So, we have a tie.
And in some sense it doesn't matter.
So we're going to fill in the entry of 4, when i equals 4, and x equals 3.
The exact same reasoning applies when x equals 4.
We're making the comparison between two thing, two
things of equal value, both equal to 4.
Now, when x equals 5, we let the good times roll.
We both can take the fourth item, and we get a value of 4 for the the fourth item.
But now, when we subtract out its weight, we get a residual capacity of 2,
and when x equals 2 and i equals 3, we also get a value of 4.
So in this entry, we can write 4 plus 4, or 8.
And that's superior to the alternative, which is just
inheriting the six from the column to the left.
Same story holds when x equals to six we can take the fourth
item, get the immediate gratification of
four, get four from the smaller subproblem.
When i equals 3 and x equals 3, and that eight beats
out the alternative, inheriting the seven from the column to the left.
So that completes the forward pass of the dynamic
programming algorithm, filling in the table systematically using our recurrence.
When it completes, of course, the optimal
solution value is in the upper right corner.
It's the value of the biggest sub-problem.
So we know, at this point, that the max value
of any feasible solution to this knapsack instance is 8.
And as as we've discussed after you've filled in
the table in the forward pass, if you want
to get your grubby little hands on the optimal
solution itself, you can do that with a reverse pass.
There's a reconstruction post-processing step.
How does that work?
Well you start with the biggest subproblems, in this
case when i equals 4 and x equals 6.
And then you ask, by which branch of
the recurrence did we fill in this table entry.
And that gives
us guidance over whether to pick this item or not.
So, how did we get this 8?
Did we inherit it from the column one
to the left, corresponding to not taking item 4?
Or, did we get it from the column to the left, in
the sub-problem with decrease, with residual
capacity decreased by the weight of item.
Four. Corresponding to taking item four.
Well, if you look at it, we didn't just inherit the solution
in the column to the left which does indeed correspond to taking
item four.
That was the better of the two options we used to fill in this table entry.
So, that means that in the optimal solution, item four will be there.
So, having figured that out, we trace back through
the table, we say, okay, well, let's look then
at the table entry that we used to build
up to this optimal solution to the big problem.
So, that corresponds to going one column to the left, and a number of
columns down equal to the weight of this fourth item, that is three rows down.
Now we ask exactly the same question.
Did we inherit the solution from the previous
column, corresponding to picking this item, or did we
use this item, and build from a solution
to a smaller sit problem from the previous column.
Well, again, you know, where did this 4 come from?
It didn't come from immediately to the left.
It came from the value of item 3
plus the optimal solution with a decreased residual capacity.
So that means that the optimal solution.
Also includes item number three.
So, what do we do then?
We trace back, we go one column to the left, and we have to go now two rows down.
Two rows because the weight of the third item is two.
So, that leads us to A(2,1) and at this point, the
residual capacity is so small that we have no choice but to
inherit the numbers from the left, so we're not going to be able
to pack either item one or item two into the optimal solution.
So at this point, we just go left during our traceback,
and then when we get to i equals 0, we're done.
We know we've constructed the optimal solution, which in
this case is item number 3 and item number 4.
That's how
you get an optimal value of 8 in this particular knapsack instance.