0:00

Discrete Optimization. Welcome back.

Â This is dynamic programming, okay?

Â So this is the first lecture where we're

Â really going to go into some technical details.

Â So what we're going to do is basically show you how you can get the best possible

Â solution to the knapsack problem and we're going

Â to use this first technique which is Dynamic programming.

Â So in this class, what we are doing is giving you a lot of hats, okay?

Â Optimization hats.

Â And these are different techniques that you

Â can use for solving optimization problems.

Â And we will tell you, really, which one is good and which one is not good.

Â Actually, we don't really know.

Â But they will give you tools to actually look at these problems and try to

Â solve them, and the first one that i'm

Â going to talk about today is dynamic programming.

Â And dynamic programming is a very widely used technique, okay.

Â So when it works, it works really well and

Â for various classes of problems it works very well.

Â Particular example is computation on biology, a lot

Â of the sequencing problems can be

Â solved using dynamic programming, but sometimes it

Â doesn't work at all and we'll try to give you intuition why okay?

Â And, and, but this is a very useful technique when it works as I said, okay?

Â So the basic principle is, is very simple. It's a divide and conquer approach, okay?

Â You know, you're going to split the problems in different parts.

Â But the really important thing is

Â that it's a bottom-up computation technique, okay?

Â So if you can do

Â that in a top-down divide and conquer, in a top-down or bottom-up technique.

Â Okay, and dynamic programming is about bottom-up.

Â We'll see a top-down technique later on, also on the knapsack problem, okay?

Â So, let's talk about dynamic programming, and

Â once again I'm going to assume that the

Â same conventions that we use when we talked about the modeling of the knapsack.

Â So, we have a set of item capital I and

Â these items are going to be denoted from 1 to n, okay?

Â So, these are the various

Â item that I can pick up. They have a name which is 1 to n.

Â And then I'm going to make another convention which is this O(k,j), okay?

Â And O(k,j) is essentially The value of the optimal

Â knapsack, if the capacity of the knapsack is k.

Â And you can select item from one to j. Okay?

Â So this is kind of a set problem and we're going to build from it, okay?

Â The way you can formalize it is exactly the way I formalized the knapsack, right?

Â But at this time only we look at the j Under the first j item.

Â Okay?

Â So, in the sense, you know, look at the problem here.

Â You know, you see, you see that, you, you see that

Â I'm only, I'm not using n there, I'm basically using j.

Â Okay?

Â And obviously what we are interested in is solving the

Â problem where we use the full capacity of the knapsack, capital

Â K, and where we use all the item, but we

Â will be basically using this problem as, as a building block.

Â 2:32

So, what I'm going to do is basically com, be completely outrageous.

Â I'm going to assume that I can solve all the sub problems

Â for a capacity k, any capacity k and j minus one item.

Â So, I have this oracle, okay?

Â Delphi oracle that's going to tell me the optimal value

Â for these two, fo, for all these things, okay?

Â I'm assume that I'm basically given this, okay?

Â So that's the oracle that I have.

Â And then I can query. I can always ask: Ooo,

Â what is the value for the j minus one item for this particular capacity.

Â And I can query this oracle and get this value.

Â Okay?

Â So the next, usually what I want to do now is add one tiny little item, okay?

Â O(k,j).

Â So I know how to compute O O(k,j-1) for any value of

Â k, and what I want to do now is compute O(k,j) for all

Â the values of k as well, okay?

Â I'm just considering one item, and you're going to see

Â it's pretty simple what you have to do, okay?

Â So the first thing you have to do Is to find out if that particular

Â item, if you have a capacity k, if

Â that particular item can fit inside and outside.

Â If it's weight is lower down than the capacity k.

Â If this is the case, then there are two

Â other, there are two cases that you need to consider.

Â The first one is, whether you are right to be selecting the item or not.

Â Okay. If whether you are selecting the item.

Â If you don't select the item, the value that you get is simply

Â the value of the item with the same capacity and j minus 1 item.

Â Okay? And we have the O record to compute that.

Â That's the value that you see there.

Â Okay?

Â So if the item fits and we decide not to select

Â it, what you get is Is basically O(k,j) minus 1, okay?

Â Now, you can select the item.

Â Okay?

Â Because we know that it fits and in that particular case,

Â what is the value that you get? Okay?

Â You get obviously the value of the item because you put

Â it inside the knapsack and then you get the value, the optimal

Â value that you can get by using the g minus 1 item

Â and the capacity which is obtained by removing the weight from k.

Â Okay the weight of the item you just selected and

Â as this expression that you say, that you see here.

Â Is v j plus the value of a k w,

Â you know, let me, let me start out again.

Â It's the value of vj which is the value of

Â the item, and then o, you know, call this orecorsursivly

Â with the value of the capacity k minus the weight

Â of the item, wj, and then obviously j minus one item.

Â And so these are the two things that you can do if the item fits in the knapsack.

Â If the item doesn't fit in the knapsack, what do you have?

Â Well, you are, you are only left with the value

Â of the j minus one item and the same capacity k.

Â Okay?

Â So we can build this beautiful recurrence relationship here, okay?

Â Which consider the capacity k and j item and you

Â basically re-express it as a maximum between these two value.

Â If the act, if the item can fit inside

Â the knapsack, and otherwise it's simply the same val,

Â the, the same the, the, is basically the same

Â value as you would get If you use only j

Â minus 1 item, okay?

Â So you have this beautiful recurrence relationship, finding the best case when

Â the item can fit whether you select or you don't select the item.

Â Or if the item doesn't fit you just, you know, end the

Â value that you could do with the j minus 1 item, okay?

Â And of course you have to start from where, if the

Â capacity is zero There is no item that you can put

Â in the [UNKNOWN] and what I am basically climbing is that

Â if you have these swings okay, you can compute the optimal value

Â of the [UNKNOWN] and which item you need to select okay.

Â How do you do that?

Â Well let me show you.

Â This is a very simple c program or Python

Â program, you can derive the same thing in Python to

Â do actually that because you know where computer science

Â is just computing this Oracle for you for free okay?

Â So you see basically O(k,j), okay and that's the function that we're defining

Â here obviously if j is equal to zero there are no item okay?

Â There is nothing you can do, therefore the value is zero.

Â Otherwise you look at the item j and whether it fits or not

Â in, in the knapsack, okay so you have the capacity k, you have w

Â j, if it fits in the knapsack what you have to do the

Â optimum value of the knapsack is going to be the max of this expression.

Â Okay?

Â And once again this consider the two cases that I have discussed before, and

Â otherwise if it doesn't fit you simply

Â come, you know, call the function recursively.

Â That's the oracle, right?

Â With one fewer item in the same capacity, okay?

Â That program is actually computing the optimal value for the knapsack, okay?

Â Now one question that I have for you is that, is this actually efficient?

Â Okay?

Â Can you tell me how efficient this algorithm is?

Â Okay?

Â And let me use an analogy here.

Â This is, what I am going to show you here

Â is a program for computing Fibonacci numbers and it's basically

Â the same structure, a little bit simpler, than

Â what I've shown you for the knapsack problem, okay?

Â If you want to compute a value of the fibona, the fibonacci number of n, Okay?

Â if n is equal to one Okay, the value is

Â one, and otherwise if the value that you obtain by computing

Â the Fibonacci of n minus one, then minus two and

Â then adding that to the Fibonacci of n minus one Okay.

Â That's how you can compute Fibonacci number, and

Â I have the same question for you right,

Â is this efficient or not Okay, and what you can see here

Â is that okay, so if you want to compute when you look at

Â this one, the value of Fibonacci n minus one What will you have,

Â what, what do you have to do to actually compute that value, right?

Â So you're going to compute this function and you're going to compute Fibonacci

Â of n minus 2 and n minus 3, but you just

Â have computed Fibonacci n minus 2 and for computing that you

Â have computed the Fibonacci of n minus 3 and n minus 4.

Â So yeah,

Â basically, we are computing many, many, many times the same values, okay?

Â So this program is actually very, very, very inefficient, okay?

Â You never want to use anything like that, okay?

Â And why?

Â Because in this particular case, it's top-down

Â and we are not doing anything fancy.

Â Okay?

Â So what I'm going to do is take the exactly the

Â opposite approach and we're going to do a bottom up computation.

Â Okay.

Â So we're going to start with zero item.

Â And that's what dynamic programming does. Right?

Â We start with zero item.

Â And then, as I've shown you before we're going put one more item and

Â then two more items and so on until we have selected all the items.

Â Okay.

Â So in a sense, look at this program here.

Â This is the program that I'm going to use in the next couple of slides.

Â The first thing we going to do is oh we going to

Â look at what you can do with one, with zero item.

Â Then one item, and then two item, and then three items.

Â That's what we are trying to do here, okay?

Â We are going to solve these very simple

Â sub problems.

Â They are very simple and then we going to build on top

Â of them by adding one more item at a time, okay?

Â And you going to see, it's beautiful.

Â Okay, so this is, and so, when you

Â think about dynamic programming, you can, you know, a

Â lot of people think about tables, and I'm going to

Â show you the table intuition of dynamic programming, okay?

Â So you start with zero items.

Â How much value can you get? If you have 0 item, okay?

Â The value that you get is 0, right? So, there is nothing to

Â take, okay?

Â Now, we are looking at one item and assume that this item

Â as a value which is 5 and a capacity which is 4.

Â Until you have a capacity which exceed you know, which exceeds

Â Three, which exceeds 3, then there is nothing you can get.

Â You get no value. Right?

Â And then, essentially, as soon as the capacity is

Â 4, you can get the value of the item.

Â So this is amazingly simple, right?

Â So we have one item, okay?

Â Now let's look at what happens if we have two items.

Â To get a new item there, its value is 6 and its weight is 5.

Â Okay?

Â And once again until you get one item that can fit in the knapsack you get nothing.

Â So initially you get all these zeroes, and then

Â you get to the point where the capacity is 4.

Â When the capacity is four you could get the first item.

Â So you get a five, okay? When the capacity is 5 what do you get?

Â Well you can select the second item which is more valuable, okay?

Â And that's what you get

Â there, until the point where the two items actually fit

Â inside your knapsack and you get a value of 11.

Â Okay, so there's the second column, okay?

Â So two items.

Â Now we going to build on this second column to actually build the case

Â where there are three items, and this

Â is where things start becoming more interesting.

Â You can see that the weight of this guy is 2, its value is 3, okay?

Â So As long as we don't have at least

Â two units of capacity, there is nothing you can do.

Â Okay? When we have two

Â units, we get basically, this item, the, the third item,

Â 3, and this is where things really start getting interesting.

Â Okay, so in this particular case When you have a capacity of

Â 4, there are two items that are fitting in the knapsack, right?

Â So this guy fits in the knapsack and you can decide to take it or not to take it.

Â If you don't take it, what happens?

Â Well, you get the value that you would have, that,

Â that you, that you had when you select only the first

Â two item. Okay?

Â So, you know that you will at least get value five, okay?

Â Because if you don't do anything, you don't

Â select the item 3, you get the value 5.

Â But now you have also the possibility of selecting this guy.

Â If you select this guy, you get its value which is 3 in this particular case,

Â but then you also have a non-empty you

Â know, capacity for the knapsack in this particular case.

Â 11:15

What do we get? We get 1, okay?

Â 2, 2.

Â We get 2. But the value

Â there, the value there for 2 is 0. Okay?

Â So basically you get the value 3 plus 0 which is there are 3 and therefore,

Â it's better not to select the item and that's what you get at that point okay?

Â And this is the same for the next column. You get 6.

Â Okay?

Â This is another case which is very interesting okay?

Â So you're looking at the capacity of the knapsack which is six.

Â Okay?

Â And you can decide if you select the item or not.

Â If you don't select the item You get the value which is on the left, which is 6,

Â okay, but if you decide to select the item, okay.

Â So you get the value of the item which is 3 and then what

Â you have is you still have a capacity of the knapsack which, which is

Â you know 4, and you can fid the first item, which basically means in

Â this particular case you have a value of 8 for the particle of knapsack, okay.

Â So this is really, really interesting though so essentially what

Â you do is you have to look at two values.

Â The value just on your left,

Â and that's the value where you decide not to take

Â the item, or the value which is in the previous column,

Â but where you have removed the capacity of the items that

Â you, the, the, the weight of the item that you get.

Â You, you get another capacity for your knapsack.

Â And now you know that you have solved that

Â particular problem, and you can use the value, right?

Â So this is what dynamic programming does.

Â You recompute this new column, okay, based only on the previous column and

Â two values in that column. Isn't that beautiful?

Â Very, very simple, okay?

Â Now, you can wonder, but, but where is the optimal value

Â of the knapsack and this is their, this is my precious, right?

Â 11 is the optimal size of the knapsack.

Â I know that this value here at the bottom right corner is what I want.

Â Okay?

Â You're going to say, yeah, yeah, yeah, but that's the value of the optimal knapsack.

Â What is the optimal solution? And I'm going to show you now how

Â you can actually get that value of the optimal solution.

Â The only thing you've to do is trace back for my

Â precious until you get to the beginning of the table, right.

Â So what do you do with the following?

Â You look at the value of the way you are and

Â then you look at the previous column just on your left.

Â Okay?

Â If the values are the same what do you know?

Â You know that you haven't select the item, okay?

Â Because the value with one fewer

Â item is the same, okay?

Â So you know that the decision variable for

Â that particular, the, for that particular item is zero.

Â You haven't selected that item, okay?

Â Now you look at this value and you do the same thing.

Â Okay, so is this the same as that?

Â No it's not.

Â That basically mean that you selected item two.

Â You remove the weight of that item, you get another capacity

Â that you can use for the, you know, the remaining items, okay?

Â And you do the same here. 5, is it,

Â is it the same as 0? No.

Â That basically means that you selected that item.

Â And so basically, at this point, you know that you're selecting item one.

Â In item two, okay, so that's the optimal solution.

Â And once again the only thing that you have to do is take the bottom

Â right corner and trace back inside your

Â table and you have the optimal solution, okay?

Â That's the beauty of dynamic programming, your computer is stable

Â and then you trace back and you get the optimum

Â value, okay?

Â Now let me show you a more complex example, okay?

Â This is a more complex example, okay?

Â It has four variables and the numbers are a little bit bigger.

Â We want to make your life little bit more miserable.

Â Okay?

Â That's what we do in this class.

Â And so what you see is you see the table now.

Â It has four entries.

Â It has a bunch of capacity as well.

Â Okay? And now what you can do, okay?

Â You just stop this video and then you start filling this beautiful table on

Â your screen. Actually don't do that, right?

Â So, don't do that.

Â Okay, just you know, just print the lecture.

Â Okay? So, I'm going to do the work for you.

Â Okay?

Â This is the complete You know, the, the complete

Â values for all these tables and they are entirely correct.

Â Okay?

Â You can trust us on that.

Â And then you see this bottom right corner, right?

Â That's my precious.

Â That's what the val, the optimum value of the knapsack and then

Â that's what I can use to trace back the value of the optimal solution.

Â Look at this guy.

Â Okay? It has value of 44.

Â Is it equal to 42? No?

Â So you know that you selected item four. Okay?

Â So you decrease the capacity by the weight of that particular item.

Â You get to this position.

Â You see, oh, is it the same. yes, it's the same.

Â yes, it's the same. Oh, it's not the same.

Â So you know that you selected item one.

Â So the optimal solution here is selecting item one and item four.

Â Okay?

Â So, and, the value of your decision variables are exactly that, right?

Â So you see that x1 is equal one, the next two

Â are equal to zero, and x4 is equal to one, okay?

Â So this dynamic programming algorithm here is basically computing All the value okay?

Â Of your decision variables and satisfying the capacity constraint .Okay?

Â Now an, an interesting question for you is how long does this algorithm take?

Â Well, it's pretty easy, right? So the only thing

Â that we are really doing is filling this table.

Â Okay?

Â And to fill any one of the entries in this table, the only

Â thing that you do is looking at two values On the prior column, okay?

Â So it's basically an algorithm which takes the time

Â that it takes is you know, as scientifically, k times,

Â the k times n, where k, capital K is size

Â of knapsack and n is the number of items, okay.

Â Now you're going to see wow, this is really interesting,

Â we just saw p equals lp, this algorithm is polynomial, right?

Â Right?

Â So are we going to get a Nobel prize? No, not really, right.

Â So why?

Â Because on a computer this capital K there, okay, can be

Â uncoded using binary notation by log of K, capital K bit.

Â Okay?

Â And because of that when you look at this complexity it's actually exponential in

Â the size.

Â Of, of the input because I can co, encode this in, input with log k bits.

Â Okay?

Â So this is of use the exponential in that number.

Â Okay?

Â So, so what do we have here?

Â Well, we have an algorithm which is called pseudo-polynomial.

Â That basically means that if these numbers are small this algorithm is polynomial.

Â It works very well when the numbers are small, okay?

Â So every time you know you've, you've essentially an knapsack whose capacity

Â is reasonably small this is a very very efficient algorithm.

Â If the capacity starts getting huge and huge and huge and you have a

Â lot of items, you know, you're are going to get into some, some issues.

Â And can you guess what the issues are? Okay?

Â Remember, what we are computing was, is this table okay?

Â This capital K is huge.

Â This table is going to get bigger and bigger and bigger and bigger,

Â okay, and that's one of the problems that you have with dynamic programming.

Â Okay guys, so this is the first hat, okay?

Â Now I wanted to present to you, this is dynamic programming, okay?

Â So you saw we can compute oh, you know,

Â of human solutions to doing abstract problem with dynamic programming.

Â In the next lecture, we'll see another technique which is essentially solving.

Â This, this, you know, recursive equation using a top down approach.

Â Okay?

Â See you next time, guys, thank you.

Â