The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Loading...

From the course by Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

438 ratings

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

From the lesson

Week 4

Advanced dynamic programming: the knapsack problem, sequence alignment, and optimal binary search trees.

- Tim RoughgardenProfessor

Computer Science

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.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.