Okay, guys, welcome back, this is discrete optimization, this is the
knapsack problems. We are getting started.
This is really easy. But we have to start from some place, so
what we're going to do is visibly locate the one dimensional knapsack and that is
going to introduce a bunch of concepts in optimization like you know, decision
variables and things like that. And then, we'll also use dynamic
programming which is a very simple techniques which works great when it
works and, and which may be very complicated in some problems, but in this
particular case you will see it's going to be working beautifully.
this is the one dimensional knapsack problem, okay?.
So, we have a set of item Alright? Okay?
Remember this, all the stuff that, you know, Indiana Jones was trying to pick.
And, for every one of these items, you get only two things here, okay?
So it's not a multidimension knapsack. Only one dimension.
So we get only the weight, okay? Wi, okay?
That's the weight of the item that we're trying to pick.
And then we have a value vi, okay? That's how much the, the item is worth.
And the goal, you know, is going to be, picking up a set of items, okay?
And they have to fit in a knapsack, so we have a capacity K.
Capital K for the knapsack. Okay, that's what you see there.
Okay, and so in a sense what you want to do is select you know, a set of items
such that the weight of, the sum of the weights of these items is Lower than this
k, and then obviously what you want to do is to maximize the value of all the items
that you have selected, okay. So you, think of it, you have two sums
there, the sum of the values, that's what you want to maximize, get the best value
out of these things, and then you want also to make sure that all the items are
fitting in the knapsack. Okay, so we have an objective function
and then we have constraint, okay. Now, so one of the big things that we've
seen discussed is how to model optimization problems.
Okay, That's a key step. So you get typically what you start with
is a informative description of a problem.
And you have to formalize it, okay, so now that happens all the time.
Whatever the problems that you are going to have to solve, people are
going to tell you this is a model alright.
You will have to talk to them and extract a model, okay.
In many of the examples that you will see in this class they are sufficiently
contained that, you know the transition isn't too complicated.
In real life it may be much more complicated.
This first thing you will have to do when you get some kind informative
understanding of your problem is choose the decision variables.
okay. And typically, these decisions, the
choice is not too difficult, because at the end of the day, you are interested in
making some decisions. And this is what the decisions variable
are going to be. Okay?
But sometimes, there are different ways of modeling these, you know, decision
variables. So, you will have different kinds of
encoding, so they may not be the first choice that you think about.
And so there is a set of models that, you know, will be, will be modeling the same
particular application, but may have different set of variables.
Okay? Once you have that, okay?
Once you have these decision variables, the next step will be looking at the
constraints that you have. For instance, in the knapsack, the thing
that all the items have to fit in the knapsack, you cannot exceed the capacity.
And you will have to express these constraints in terms of the decision
variable that you just chose, okay? So, once again, decision variables, then
you model the constraints of the problem in terms of the, the decision variables.
And then, afterwards you do the same thing for the objective functions.
It's not a constraint. But, once again, it's going to be an
expression describing the value of the eventual solutions.
Okay, in a sense the way to think about it is this.
The decision variable are the decision you are interested in, the constraints of
the you know are basically defining what is a feasible solution.
What is a solution and then the objective function telling you how good that
particular solution is, okay. And so the result is an optimization
model. Okay, so basically it's a clarity
formulation of what you want to solve. It tells you what you want, doesn't tell
us how we going to solve the problem and of course.
One of the big goal in this class is actually finding out how we can solve
this model. But another goal is actually how to write
the models. Okay, so these two things are part of
optimization. How do you write a good model and how do
you solve a good model? Okay, and we talk about all these things
all the time. Okay, now one of the things that is very
nice in optimization is that there are many, many, many ways of actually writing
these models. It depends the decision variables that
you take The constraints how you model them and so on and so forth.
Okay, and so we'll see a lot of problems where, oh, there is one modeling like
this, there is another modeling like that, and so on.
Okay. So in the knapsack problem if you go back
to that problem, okay, the decision variables here are going to be very, very
simple, okay. So you have a variable xi and that
variable is going to decide if item i, okay, In the set of items that you can
select, it's selected or not. OK?
So Xi is going to be 1 if you select the item in the solution, or it's going to be
0 if the item is not selected in the solution.
OK? So, it's a, so it's a 0,1 vibor,
sometimes we talk about a binary vibor. See, there's only 2 value 0 and 1.
So these are the decision vibor's that we have.
OK? So once we have you know identify this,
identify these decision very well the next step into model the constraint and
you see the cons, this is knapsack constraints that you see here.
Once again you do this is a big sum for all the potential item that you can
select OK for all the I and capital I OK, that's the set of item you can choose and
what you see there is that you have a product and the product is multiplying
the decision variable Xi. Weight, the weight of that particle right
here so in a sense if you select the particle the element of this some is
going to be Wi if you don't select it its 0.
Essentially what you are doing is summing all the elements that you have selected
and you make sure that they are smaller than k OK, very simple right.
Once you did decision variable expressing this is almost trivial right And then the
objective function is exactly the same. Instead of using the weight, you use the
value. Of course, this is not a constraint, this
is something that you're trying to maximize.
Okay, so basically, once we have done it, we have an optimization model.
Okay, and so this is the model, okay, it's very, very simple, beautiful model,
okay. So we have the objective functions here
that you maximize, okay, you maximize The values of the item that you select and
then what you do is you basically make sure that all these items fit inside the,
the, the knapsack. And then [INAUDIBLE] have to be a value
between zero and [INAUDIBLE]. But they have to be the zero or the value
one. One, you select the item, or you don't
select the item, okay? So that's the [INAUDIBLE], once again,
the clarity that I even told you to to solve it, okay?
But it's the basis, this is vocabulary. We can talk about the problem, that we
have a motive okay, so we know exactly where this problem is, and now we can
discuss various solutions and we'll see that, okay?
you see various technology for accurate sounding the, the various models.
Okay? So one of the things that we mentioned in
the introductory lecture is expontial growth, okay.
When you're looking at the problem like the [INAUDIBLE] problem here you know
they are huge number of configurations if you have many items, okay.
So the configuration that you are looking at is all the possible, you know,
combination of isolate this item or I don't and so on, okay.
And so you have a very large number of all these configurations.
That's essentially your search base, okay?
So you will have to pick the one which satisfies the constraint, the capacity
constraints, and maximize the objective function, okay?
But obviously, you don't want to enumerate all these guys, why?
Because you know they are a huge number of them.
Of course some of them are no feasible so you have to rule them out, they exceed
the capacity at max. But even if you look at those, you may,
even if you look at only those that are feasible you can have a really large
number. So if you take all the possible
configuration the number of configurations that you have to look is 2
to the power of the size of I. Two to the power of the number of item.
Okay? Exponential growth, okay?
So we can't enumerate those for very large number, okay?
So we'll have to find a way to do better than that, okay?
Because if you, if, if, let me just give you an example if you would try to
enumerate them all, okay? So if it takes one millisecond, for
instance, for testing if a configuration is feasible and finding its value, right?
And if the number of items that you are considering is 50.
You will need essentially this large number of centuries.
Okay, so is like a billion centuries. Okay, and this is only 50 items.
Right? A billion centuries that you have to wait
for getting the ultimate solution. That's a long, long time.
Okay, so you have to find a way to actually do this better.
Okay, how are we going to do that today? Okay, so we are going to look at dynamic
programming. It's very, as I said, it's very simple
techniques. When it applies it's amazing good.
Okay? For certain kinds of problems, this is a
technique that you can't beat. Okay?
it's heavily used, for instance, in computational biology, but it's also used
in many, many different contexts, and we'll see many uses of dynamic
programming in this class. But, once again, there are limitation to
the, there are limitations to this technology, as well.
Okay? But what we're going to see today is an
introduction to dynamic programming, okay, in the context of this knapsack.
And it's a particular example which is actually well suited, okay.
And the basic principle is, is very simple, okay.
There are two ideas. The one, the first one is, divide and
conquer, okay. Very general principle in computer
science. And the second one is what I would call
bottom up computation. You're going to start from the bottom and
then you're going to try to reach the goal, okay.
And, so what are we going to do, is introduce divide and conquer, from a top
down standpoint, and then explain why we need to go bottom up in this particular
problem. Okay?
So, once again, we're going to take the model, and we are going to try to solve
it using dynamic programming, so we're going to massage those equations until we
actually can solve this problem. Okay?
So, the basics, we, we're going to take a basics, a set of basic conventions, okay.
So I'm going to assume that the set of items are numbered from 1 to n, okay.
So I is the set of numbers from 1 to n. And then this is the key here, okay.
So, this is really important, okay. So, we're going to introduce the
notation. Which is O k j, okay?
And the key idea there is that O k j, okay, is the value of the optimal
solution. If the capacity of your knapsack is k and
if you can select the j 1st items, the 1st j items, okay?
So, you look at the items from 1 to j. And you look at a knapsack of a capacity
k. And what this value O j k's giving you Is
the best solution that you can get for those configurations, okay.
So configurations which are only looking at item 1 to j, and a capacity of the
knapsack which is k. Okay?
So we're going to assume that we have this, and then we're going to work with
it, okay. And of course, what we are interested in,
in the end is the finally the value of all capital k, which is the size the
wheels, the, the, the full size of the knapsack and then considering all the
item which is n. Okay?
So, and what we're going to do is compute a value of, of, of all these O of k, j's
in terms of other O of k, j's. You know, smaller k's, smaller j's and,
and building these things up. okay?
That's what we'll do at the end. Okay?
So now, this is, this is the one slide which is the basis of everything we do in
the rest of the lecture. And so we are going to assume that we
have a [UNKNOWN]. Okay, which is, tell us how to solve all
k,j minus 1 for all the value of k between 0 and capital K.
Okay? So for all the capacities of the
knapsack. I'm going to assume that I have the value
from all K minus all K, J minus what okay?
So I know that I've all the solution for all the possible of value of my nap sack
and the J minus 1 item. Okay and the only thing that I'm going to
do is to solve all K J assuming that I can't actually look up the value of all
these guys. Okay?
So I'm basically giving you a lot of information, you know.
All the possible value for all the capacity of the knapsack.
And then all the item between 0 and J minus 1.
And I'm only asking you, can you give me the optimal solution if I give one more
item? Okay?
So I'm moving from J minus one item to J, 1 more item.
That's all I need to do. Okay?
So, that's the goal of this slide, okay? So what am I going to do, okay?
There are two cases, okay, two big cases. And then in one of the cases, there are
two other cases, okay? In the first case, is that, the weight of
that item is greater than the capacity K of, that I have in OKJ, okay?
If the item is bigger than the capacity that I'm looking at.
What can I do? Well, essentially, I have to ignore that
item. So the value of O(k, j) is going to be
what? It's going to be simply O(k, j) minus 1
because I can't fit this item inside and outside.
Okay, so that's a very simple case. If I can't fit the item, I can't fit the
item and for the value with that additional item is the same as before,
okay? Now, the other case is when I can
actually fit the item inside the knapsack.
That is more interesting. Now, I have to make a decision.
Do I take that item, or don't I take that item?
OK? So basically I have to choose whether I
take it or not. Now, and, essentially if I don't take it,
that's also easy, right? The value of OKJ would be the value of
OKJ minus one. Right?
But you can actually take the item. When you take the item, once it's, ha-,
what is happening? When you take the item, you're going to
reduce the capacity. Okay?
So the capacity now, is going to be all, it's going to be k minus the weight of
the item. Okay?
So it's going to be k minus wg. Okay?
So has the item that you have, After you selected item j, okay?
But no, no, what can we do? We can use the fact that we know all the
values for the j minus 1 item and all the capacity, okay?
And therefore, the value that's the best value we could get if we take the item.
Is essentially vj, which is the value of that item j.
And then, the best value that we could do with the capacity with, which is k-wj,
and the j-1 [UNKNOWN] okay, the first G minus one [UNKNOWN], okay?
And so essentially you get these two values, either I don't take the [UNKNOWN]
and then I have okay, okay J minus one, okay or I take the [UNKNOWN] and I have
VJ plus OK minus WK which is the weight of the
[UNKNOWN].
And the J minus 1 I items. Okay, so in a sense this is the
recourence relation that I've just, you know, shown you.
I've just shown you. Okay?
So if i can fit the item inside the nap sack.
I have to do the maximum of these 2 values.
Whether I take the item or whether I don't take the item.
And of course, if I can't fit the item, you know, I, I just don't take it.
Right? And so basically you have a recurrence
relations here, which is basically defining the value of okj in terms of all
the values with j minus 1 item. Okay.
So that's the basic idea here of recurrence relationships, which are the
basis of dynamic programming. Okay.
So now we have this beautiful thing, what can we do with it, okay?
So yeah now I have to tell you that of course, if you don't, if you have no, you
know [INAUDIBLE] time the body is zero. Okay so now once I have this recurrence
relationship I can write very, very simple problem which is [INAUDIBLE] okay.
Recurrency problem which is top dog, so I can have you know, this is a C like you
know, functions, we're actually doing that I have O, I have K, and I have J.
And I want to compute the, that particular optimal value.
Okay? And what I do is that if J is equal to
zero, I have zero item, which are zero. Okay?
Now, if the item fits inside the knapsack, I have these two cases that I
have to do. Right?
So I do this maximum and I call the, you know, I call, the, you know I call the
procedure the, the function recursively. In the first case the only thing that I
do is that I assume that I don't take the item, okay.
Which basically means that now I'm coding recursively ok with j, with j minus 1.
Same capacity but fewer items. Or, I take the item, then I have the vj.
And then I call the, the function recursively.
We've a smaller size of the item, and then, we have j minus 1 item, okay?
So, basically, very simple recursive, you know, codes there.
And then, obviously, if the kna-, if, if the, if the particular item doesn't fit
inside the knapsack. I just call the value for you know O of
k, j, which is once again, y minus O of k, j minus 1, which is the same capacity,
but no the j minus 1, j minus 1 items only.
Okay, so essentially every time I have this recursive relationship I can always
write a simple recursive program like that which will actually compute the
optimum volume. Okay?
So very simple, very simple thing. It’s like a one to one matching between
the equations that I’ve shown you and this simple, simple C-like function.
Okay? Now is it, is this any good?
Okay? So the question, the question I'm asking
you here is simple, right? If I write this program, is it going to
be good? Is it going to be exponential time, or is
it going to be low polynomial time? What is it?
Alright? So let me give you an analogy, okay?
So assume that I want to solve a problem which computes all the Fibonacci numbers,
okay? So this is a recursive function, which is
very, very similar to the, to what I just wrote for the knapsack problem, right?
So if I have a fibonaci number and if I want to compute the volume of, the
fibonaci of n. So if N is equal to 0 and 1 I would
return 1. Otherwise I would compute these 2 things.
I would compute fibonaci n mins 1. I would compute fibonaci of N minus 2.
And I would sum these 2 guys. Okay.
And I would return the result. Okay?
Now, is that program any good? Okay, so this program is a little bit
simpler, because we have only, you know, we have only one number here in the
recurrence, in a sense, okay? But, so, so it's easier to find out what
is good or not, okay? So, because if you start with n, okay,
how many subproblems do you have? You have two subproblems to tackle, okay?
So you have Fibonacci of n minus 2, and Fibonacci of n minus 1, okay?
So when you take one of these subproblems, let's say.
fibonacci over minus 2. And you try to solve it.
What are you going to do? You are going to create another 2
problems okay. And then these 2 problems are going to
great another 2 problems okay? And it's the same thing for you know the
left, the right of the recurssion that guy is going to create 2 sub problems.
Which are also going to create you know, every one of them are going to create two
separate problems. So what you see here is what?
It's exponential growth. Okay?
So, you basically see that this very simple program, very naive program is the
syntax, every time you go into one level of the recursion you're doubling the
number of nodes, okay? Now, it's completely unnecessary this
way. Why?
Why is it completely unnecessary to actually double these large number of
nodes? Well, when you try to solve Fibonacci of
n minus 1, what is it that you're going to do?
Well, you're going to solve Fibonacci of n minus 3 and Fibonacci of n minus 2.
But, which you just computed. Fibonacci of N minus two.
So there are plenty of problems that are really the same everywhere.
OK? But the stupid implementation, in a
sense, doesn't see that, and recompute them all over, and you get this
exponential growth. OK?
So the way to think about dynamic programming is that instead of computing
this function top-down, we are going to basically compute it bottom-up.
OK? And that will make sure that we never,
never, never solve a sub-problem twice. Okay, so that's the key idea.
Okay, so it's going to be the same recurrence relationship, the same formula
but instead of computing them top down, we're going to compute them bottom up.
And that's going to basically, you know, handle the fact that, handle this
exponential growth that we get because we recompute many, many, many times the same
things. Okay.
So, so what these equations, you know, so, so the way we're going to look at
these equations bottom up is very simple. All right, so we're going to start with
zero item. What is the best we can do if we have
zero item to work with? Okay.
And that's going to be pretty simple, right?
And then we're going to do the same thing with one item.
And then, what is the best that we can do with two items?
And then, what is the best we can do with three item, and so on and so forth.
Okay? So we are, basically, going to grow,
we're going to do this induction essentially on the number of items, okay,
one at a time. Okay.
So, how are we going to do this induction?
The best way to think about dynamic programming in general is to look at it
as a table. So we're going to build A huge table,
okay, hopefully it's going to be resonably small, but we are looking at a
big table, okay. So, and this table is going to basically
look at the induction step by step. We are going to look at the first column
and that's, that column is going to be, what can I do with zero item, and the
next column is going to be, what can I do with one item, the following column, what
can I do with two items and so on and so forth.
Okay? So, everyone of these columns is
basically going to add one more item. To the, the selection that we can wait.
And, so that's going to be the, that's going to be the x axis.
The y axis is going to be the capacity of that particular knapsack, okay.
So, when I look at the first column, what I'm basically asking is what can I do
with 0 items, okay? And that's easy, right?
So, what can I do, is nothing. So.
So the value that you see there is the best possible thing that I can get.
If I can pay with 0 item and, let's say, my capacity of the knapsack is 7, okay?
So that's the value that you find over there, okay?
So, 0 item, capacity is 7, I get 0, okay? Now, We start getting a little bit more
interesting here. We can select one item, the first item.
And what you see over there is the value of that item, 5; is the weight of that
item, 4, okay? So, what is going to be that column?
That column is going to be very simple, okay?
If I can't fit the item, I get a value 0. If I can fit the item, I get the value
five. And that's what you see in that column,
okay? Zero until the capacity is four.
And when the capacity is four and, and, and above I get the value five, okay?
Two item is, is still interesting but very easy to do right?
So what you're going to do is basically look at You know, what is the first time
we can put one of the items, okay, and then, you know, if the, if, if there is
only one item you're going to take out one, if there are two with the same
value, you're going to choose the one which has the highest value.
And then you're going to continue doing that until you have, you can fit both
items, and you have the sum of the, of the values of these two items.
Okay, so what we see here is that we are considering a new item which has a value
6 And a weight of five. OK?
So the first thing that you're going to see in this column is a bunch of zeros.
OK? Then, when the capacity is full, we know
that we can put the first item, so this is going to be the value five.
When we have value five, six, and so on, until the very last value, we are going
to put the second item, because the second item is more valuable, it is a
high weight But it's, it's more valuable so you see a bunch of six over there and
this last value here is when you can actually put both items because the sum
of these two things is going to be nine and the capacity of the knapsack here is
nine. So, you have a total value here of 11
because you can fit both items, you sum the values.
Okay? So, so far very easy.
You know, we haven't done really anything.
So, the next column is more interesting. That's where we are basically going to
use these recurring relation. And the fact that we can select an item
or not. And, we are also going to use the fact
that wow! At this point, we have already compute
the value of all the possible combinations of the capacity of the
knapsack and 2 items. Right?
So we know, in a sense, what this column is giving you, right?
This beautiful column here is giving you the best you can do if you can have two
items and a particular capacity for the knapsack.
So essentially now, we can, you can view this as a look-up table.
When we compute this column, we are going to ask questions, and we're
going to get the answer, because we have actually computed these values already.
Okay? So let's see what we do.
At the beginning, okay, so we have this new item now.
Okay? That new item is a value three and a
weight of two. Okay?
So what we're going to do is, you know, abuthly as a, you know, as long as we
don't have enough capacity for any one of them we're going to get zeroth.
Okay? When we get a capacity of two, you know,
we know that the new guys, you know, this guy is only a, a weight of two, so we can
put it in. So we get a value of three, for these two
things. And now we come to the point where you
know we are a capacity of four. And now there are at least two items that
we can fit. Okay?
So, what are going to do? So, this is where for the first time you
are going to see the recurrence relationship.
Right? So what you see is that there are always
two possibilities, right? So you can look on your left, okay?
So if you look on your left, it's basically the decision of not taking the,
not taking the knapsack, okay? So when, and so, not taking the, the, the
new item, okay? So, you're basically saying, I'm not
going to take this item. So, the best value that I can do is what?
Well, is looking at the column which, with the value of the cell which is here
which has the same capacity as the capacity we're looking at, okay.
But is using, is not using the just, the item that we're considering now.
It's using all the other ones, okay. And so, in this particular case we can
decide, oh I am not going to select the new item.
And therefore the value is going to be five.
Or I can decide I'm going to select this item.
And then what I'm going to do is look at the table, okay, of what I can do with
all the other items, but now a lower capacity.
Because I took some capacity of the knapsack.
In this particular case, this guy is a weight of two.
So I'm going to look at that particular cell here.
And that cell is a zero, okay? So I'm going to say, I can take the not,
I can take the new item, okay, which is a value 3, okay?
And, and then, with the other items and the capacity that I have, which is 2, I
can't do anything. So the total value's going to be 2.
Or, I can decide not to take the item, and then the total value is 5.
So in this particular case, the best decision is not to take the item.
I get a 5. Okay?
The next, you know, the, the reasoning for the next cell is the same thing,
except that I select another item, which is 6.
But once again. What I did was looking at my left and
take the value of that cell. So, in a sense the cell just next to the
one that you're computing, you have to do at least as good as that.
Okay? So now this item here is very
interesting, 6, okay? So we have a capacity of 6, and we are
wondering if we take this item or not. Obviously, we know that because when we
look at the, the left, we have at least the value of 6 that.
We'll do a [UNKNOWN] six, okay? So but can we do better, okay?
So once again, there are two decisions so you don't take the item, you get a value
of six or you take the item. If you take the item, you take a capacity
of two, now you have to look at what you can do with essentially, all, you know
the first two items and a capacity of four, okay?
So, this is essentially all four, two, right, so that when we were reasoning
about the recurrence relationship. In this particular case, you get the
value five. Okay.
five, five if you basically took this capacity, and now you have a value of the
item that we just selected, which is two. So you get a value here, which is three,
the value three, sorry. So we get the value three plus the value
five, and then we get the value eight there.
Okay? And that's what you see on the sets, and
the last set here, is, is going to be 11. Okay, so, basically, all these sets here
are now taking the item. Okay?
So in a sense what I've shown you here is that you can use this recurrent
relationship by looking at the, at the column which is just on your left.
Okay if you don't think the eye can devalue just on your left otherwise, it's
just a little bit upwards. Okay, by the size of the item and you see
the value which is there and you are value of the item that's what, that's the
column that you see okay. And of course we can continue that You
can continue to do that for all the possible items so in this particular case
we have only three items OK, and so we have done, OK.Now what we know at this
point is that this, if this is the food capacity of knapsack these are all the
items that I can take that the best that I could ever do is over there OK.
Its the value 11. So I know that the optimal value to my
knapsack problem is here. But I don't have the decisions, right?
So this point, the only thing that I have is, I have this beautiful knapsack, okay?
And the n-, well, I have this beautiful objective value; I know I can do 11.
What you're telling Andrew, yes, yes, yes, you can do 11, but he has no clue,
which items he has to pick, right? So the thing that we going to do now, is
essentially finding from that popular value, in the table, which item we have
to pick. And there is a beautiful thing, which is
essentially Tracing back the algorithm, okay.
And so what we do is we look at this value, okay.
If this value, so we look at this value and we look at the value which is on its
left again. Okay, so if these two values are the
same, what does it mean? It means that, well, you know, you don't
take the item. Because essentially, that value was 11.
We bought the item, and you still have a value which is 11 there with the item.
So you can just not take the item, okay? And now, you get back there.
So you know that we don't need to take item number three.
Okay? So we go back to this point here, okay,
and we say, oh, you know, is the value on my left, okay, as the same value as my
south? And it's not the case in this particular
case. Okay.
So you say ooh, but that means that I picked an item.
Okay. So you can, so when you trace back you
look at the capacity of that item. Okay.
Which is item 2. And you trace back.
Okay. So that item took a capacity of 5.
Okay. And you get back to this cell.
And this cell has a value of 5. OK?
So once again, for that cell, you look at that cell on it's left, and you see 0.
Ooh, that means that you pick up that item, you pick up item 1, and then you go
back to the top left most cell. And that's know when, that's essentially
when the algorithm, the tracing back is completed.
So what this means, here, is that you're going to have this kind of jagged line,
in general, in your table. And when you go straight, it basically
means that you don't take the item. When you go up that basically means that
you take the item, okay? And you can alternate, or I take the
item, I don't take the item, I take the item, I take the item, and so on and so
forth. Okay?
And that's so you can, from the table, and the optimal value that you have on
this, you know, bottom corner, you can recompute the value of, you can which
item you have selected or not. Okay.
So, essentially in this particular case we take item 1 and 2 and we have the
optimal solutions. Not only the opt..., you know, in
addition to the optimal values that we had when, when doing the forward phase.
Okay. So, let's look at the bigger example now.
Well, not much bigger, only four items. Okay.
Capacity of the knapsack is 7. These are the value of all the items.
This is the weight of all the items. So, we build this table.
The table is a little bit bigger than before.
We have these 4 items, no, okay? I select item I say 0 item, the 1st, the
2nd, 3rd, the 4th, okay? And the capacity of my knapsack now is
between 0 and 7. Okay, so I'm letting you actually do this
on your own. Okay, so you can compute it.
So, I'm going to freeze For, you know, ten seconds, okay.
So, you can freeze the screen. You know, you can freeze the video your,
yourself and then you can fill this table.
Okay, not right on your screen, right. But you can do that.
Okay, so I'm assuming that you've done it, okay.
So this is the result that you should get, okay.
So, when we fill the table using this recurrent relationship, and the optimal
value is there. It's 44, okay.
So, how do we trace back in this particular case?
We're going to do exactly the thing that we have done before, we look at the cell
just next to it. Ooh, it's 42, it's not 44, okay?
So, therefore, we know that we took item 4, okay?
So item 4 has a value of 028 and a weight of 5, okay.
So we decrease the capacity of the knapsack by 5, okay, and we look at that
set over there, of loosely 28 and 16 should be 44, that's what you, we are
reassured, okay, we computed right. And the capacity of the knapsack is 2
now, okay? So you gotta look at that [INAUDIBLE].
Look at the, you look at this left, it's 16.
So we know that we've haven't taken item 3.
It's 16 again. We haven't taken item 2.
[INAUDIBLE], in this particular case is zero.
So you go up, okay? Which basically means you take item one.
And know we are at the bottom left or the top left hand corner.
And we know we are done, okay? So in this particular case, we took item
4 and we took item 1, okay? And this is the ultimate solution.
you know, 44. We can fit inside the knapsack, and we
have the best optimal value. Okay?
Now you have seen how dynamic programming is working, okay?
So one of things that we have seen is that if you compute this thing top down
you're going to repeat, repeat, repeat again, solving the same problems over and
over again. Okay?
So, by doing this table computation, this basically dynamic program, we avoid doing
that. We will never recompute the same thing
twice, okay? But are we polynomial?
What is the complexity of the algorithm that I've shown you?
Okay? Well, it's basically the time to fill
this table, okay? So we have two axes, x and y.
You know, on the x [INAUDIBLE] axis, you know?
What we have is the number of an item, okay?
So on the y axis, what we have is the capacity of the knapsack, okay?
So it's basically an algorithm which we'll take, you know?
The capacity of the knapsack times the number of item, okay?
Wow. This is an MP hard problem.
An MP complete, well, MP hard problem in this case, because we are optimizing.
And we are solving it in that time? Does that mean that this is polynomial?
In which case, we would have solved the most, you know, interesting problems in
computer science. Well, the question that you have to ask
you is how can you represent K, the value K, the capacity of the knapsack on a
computer, okay? So if you try to represent K on a
computer, you know, the way the computers are representing this.
Is by using this memory words and this bits representation, okay?
And, essentially, to represent K on a computer, okay, using, you know, two's
complement notation for instance, you would l-, you would need, essentially,
log(K) bits. So, in a sense, when you look at log(K)
bit, that's the size of your input for K, okay?
And you look at the complexity of the algorithm, this is obviously exponential
in the size of the input, okay? So what, what we have seen here is that
if K is small essentially, This is going to be a very efficient algorithm.
So, and that's what we call, essentially, pseudo polynomial algorithm.
They are going to be very well if k is small.
If k is large, essentially the algorithm is going to take, the table is going to
get big, and essentially, it's going to take a long time to compute.
Okay, so essentially, a polynomial algorithm is not a polynomial algorithm,
but it behave like a polynomial algorithm when the numbers are small Okay?
And so we haven't, you know, we haven't solved the most open problem in computer
science, unfortunately. Okay?
But what we've seen today is that we've seen dynamic programming, basically
bottom of computational, these [INAUDIBLE] relationship.
It's one way of solving you know NP hard problems, okay?
And when it works, it works very nicely, and it's typically, the not, if you think
about these numbers and see if they are small, this is or even if n is large and
K is reasonably small, this is going to be a fast algorithm.
Okay? Well, this is, you know, this is the
first class, this is first lecture of this class, okay?
So next time we'll come back to the, to the knapsack problem, and look at branch
and bound algorithm.