Here is the analysis. 
Step 1 of our algorithm sorts the items 
in non-increasing order of value per 
size. 
Step 2 of our greedy heuristic picks the 
maximum prefix of items who fit into the 
kapsack. 
Let's say that maximum prefix comprises 
the first k items. 
The k plus first item is the first one 
that does not fit in the knapsack given 
the previous selections. 
So here is the cool part. 
Remember we added this step 3 to our 
greedy algorithm so that it considered 
two different candidate solutions and 
picked the better of them. 
The first candidate solution was just the 
outcome of step two. 
So therefore, we can definitely say the 
output of our three-step greedy algorithm 
is at least as good as the total value of 
these first k items chosen in step 2. 
The second candidate considered in step 
three of our greedy algorithm is the 
maximum value item all by itself. 
So one such item all by itself that would 
be considered by the greedy algorithm was 
this k plus first item, the item on which 
we got stuck in step 2. 
So therefore, whatever the value of our 
output of our three-step greedy algorithm 
is, it's definitely at least the value of 
item k plus one in isolation. 
So let's add these two inequalities 
together. 
On the left hand side, what do we get? We 
get double the value of our three-step 
greedy algorithm. 
On the right hand side, we get the first 
k items and also the item k plus one. 
That is, we get the total value of the 
first k plus one items. 
So now, we're in a position to connect 
this inequality to the fractional greedy 
solution. 
So remember, what is the greedy 
fractional solution, well, it packs the 
first k items, and then the item in which 
it gets stuck, namely, item k plus one, 
it fills up the knapsack fully with a 
suitable fraction of item k plus one, and 
the value that the algorithm gets is 
prorated according to the fraction that 
it fits in. 
But what we have here on the right-hand 
side in green is even better than the 
greedy fractional solution. 
This is the first k plus one items, 100% 
of them. 
The greedy fractional solution has the 
first k times, 100%, and some fraction of 
item k plus one. 
So, the value of the fractional greedy 
solution is even worse than the 
right-hand side here. 
And the whole point of our thought 
experiment was to argue that the greedy 
fractional solution is even better than 
optimal, 
that has value at least as much as every 
feasible knapsack solution. 
Divide both sides by two and you'll see 
that we proved the theorem. 
The output of the three-step greedy 
algorithm is guaranteed to be at least 
50% that of an optimal solution. 
That's cool. 
We have a non-trivial worst-case 
performance guarantee for our simple and 
blazingly fast three-step greedy 
heuristic for the knapsack problem. 
But, maybe you were hoping to do a little 
bit better than within 50% of an optimal 
solution. 
Maybe in the back of your mind, you were 
really rooting for something like 90% or 
even better. 
There's a few roads we can take that 
might lead to better performance 
guarantees. 
The best case scenario is if we could 
just sharpen our analysis of this greedy 
heuristic, that is, don't change the 
algorithm, don't make any new 
assumptions, just have a better proof and 
maybe the 50% one prove to some other 
number. 
That would be the best case. 
The second thing we could do is if we 
really love this algorithm, for example, 
it being so fast, we could try to 
identify additional assumptions on 
instances that allow us to prove better 
performance guarantees than this 50% 
guarantee which holds for all instances. 
The third thing we're going to try to do 
is just come up with a better algorithm, 
that in fact, has better performance 
guarantees, so what I want to show you on 
this slide is that the first case, the 
best case scenario of just sharpening the 
analysis of this greedy algorithm, is not 
feasible The analysis cannot be 
sharpened. 
[INAUDIBLE] the 50% can be realized for 
certain instances. 
Then, we'll tackle the other 2 
approaches, and we will in fact get 
better performance guarantees, either 
under extra assumptions about the 
instances, or alternatively, using a more 
sophisticated algorithm. 
So here's an example that shows that 
there really are knapsack instances on 
which this 3 step greedy algorithm might 
obtain merely 50% of the value of an 
optimal solution. 
In this example, we're going to set the 
knapsack capacity, capital W, to be 1000. 
There's going to be three items. 
Item one will have a value of 502 and a 
size of 501. 
The second and third items are going to 
be identical, 
both are going to have value 500, 
both are going to have size 500. 
So what is the greedy algorithm going to 
do? Well, in step 1, it sorts the items 
according to the value for, per size 
ratio, and you'll notice that the first 
item has a ratio slightly bigger than 
one, 
so it's going to be considered first 
before items two or three. 
In step 2 of the greedy algorithm, it 
packs item one in the knapsack, that 
leaves only 499 units of residual 
capacity, not enough room for either item 
two or item three. 
So step 2 of the greedy algorithm just 
outputs the first item by itself. 
Step three of the algorithm considers the 
max value item in isolation, 
that again is item one. 
For this reason, the greedy algorithm 
will output the solution which is just 
item one for a value of 502. 
And I'm sure you've noticed that there's 
a better solution if you [INAUDIBLE] item 
one and instead choose items two and 
three. 
They both fit in a knapsack, 
they fill it fully, 
for a combined value of 1000, which is 
essentially twice as big as the value of 
the greedy solution. 
So what does this example teach us? Well, 
it argues that if we want perfomance 
guarantees better than 50%, we have one 
of two options. 
First, if we really want to keep 
analyzing our three-step greedy 
algorithm, we're going to have to make 
extra assumptions about the instances. 
In order to prove performance guarantee 
is better than 50%. 
There are some instances out there where 
the performance is bad as 50% of optimal. 
The second approach we can take is to 
look at better algorithms which might 
have better guarantees on worst case 
instances. 
So in the next slide, I'll show you a 
refined analysis of the three-step greedy 
algorithm, conditions under which it 
performs much better than 50%. 
In a separate sequence of videos, we'll 
develop a dynamic programming base 
heuristic, 
which is guaranteed to have much better 
performance, on all instances. 
So there's a few different assumptions 
you can impose on knapsack instances that 
will enable you to prove better 
performace gurantees for greedy 
heuristics. 
Let me just show you one, that's both 
simple and also it's a condition that's 
met in many knapsack instances that arise 
in practice. 
So let's focus on knapsack instances 
where no item is especially big compared 
to the knapsack capacity. 
For concreteness, let's say that the size 
of every item is at most 10% of the 
knapsack capacity, capital W. 
As you'll see, there's nothing special 
about the number 10%. 
I'm just using that to keep the 
discussion concrete. 
So I claim that without changing our 
algorithm at all using exactly the same 
three-step greedy algorithm. 
Actually, here, we can even get away with 
the original two-step greedy algorithm. 
We can prove performance guarantee is 
much better than 50% as long as the 
instance satisfies this property. 
Why is this assumption useful? Well, lets 
think about step 2 of our greedy 
algorithm. 
So we've sorted the items in 
non-increasing order, of value per size. 
We're packing the items one at time. 
Now, at some point we get stuck, there's 
some item k plus one where if we tried to 
put it in the knapsack, we would overflow 
the capacity. 
Well, by assumption, this k plus one'th 
item, its size is at most 10% of the 
original knapsack capacity. 
So if sticking in item k plus one would 
cause it to overflow, that means there's 
less than 10% of the knapsack capacity 
currently available. 
That is, the knapsack is currently 90% 
full, or more with the items that we've 
already packed in so far. 
So this is sounding pretty good. 
Our greedy criterion ensures that 
whatever fraction of knapsack we wind up 
using, we're using in the most valuable 
possible way and we just noticed that 
this assumption on the instance, implies 
that we use almost all of the knapsack. 
To make this intutition precise, we 
comapre the output of our greedy 
algorith, even just step two, to our 
favorite hypothetical benchmark, 
mainly, the greedy fractional solution. 
What's the difference between these two 
solutions? Well, they're almost the same, 
the only difference is that the greedy 
fractional solution gets to pack that 
last bit of the knapsack, which we know 
is at least 10%, with a suitable fraction 
of item k plus one. 
So, the value that we're missing in our 
solution is that final 10% at most of the 
greedy fractional solution. 
Now in the greedy fractional solution, 
the items are packed in decreasing order 
of bag per buck and a value per size. 
So, this last 10% of the greedy 
fractional solution is also the least 
important. It's making the least valuable 
use of capacity. 
So this final at most 10% of the greedy 
fractional solution can account for, at 
most, 10% of its overall value. 
So whatever we're missing in our solution 
for our greedy algorithm, it's at most 
10% of the overall value of the greedy 
fractional solution. 
That is, we're getting at least 90% of 
the value of the greedy fractional 
solution. And we know from our thought 
experiment that the greedy fractional 
solution is even better than optimal, is 
at least as good as any feasible knapsack 
solution, therefore, the output of our 
greedy algorithm, even if we don't use 
the third step, is 90% as good as the 
value of an optimal solution. 
All of this reasoning holds equally well 
with a number different than 10%, 
so for example if you only knew that 
every size was at most 20% of the 
knapsack, then you'd get that the greedy 
solution would be at least 80% of 
optimal. 
On the other hand if you knew that every 
item had size at the most 1% of the 
knapsack capacity then just the two-step 
greedy algorithm would get you within 
99%.