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.